On 15 Oct 99, at 18:25, Chris Jefferson wrote:
> Just something I was pondering a couple of days ago...
>
> Consider a general number (odd) number c which can be factored into ab=c
>
> W.L.O.G. assume b is greater than a
>
> then let x=(a+b)/2 , y=(b-a)/2
>
> then (x+y)(x-y)=c
>
> x^2 - y^2 = c
>
> x^2 = c + y^2
>
> So if we can find if this equation has any integer solutions, we've found
> our factors...
>
> Ways of doing this:
>
> The difference of two squares is always an arthimetic progression of odd
> numbers. Here is an example..
>
> 2^2 - 1^2 = 3
> 3^2 - 2^2 = 5
> 4^2 - 3^2 = 7
>
> and so on... So look at general sum of an arthimetic series
>
> S(n) = (n/2)(2a + (n-1)d) In this case d=2 and a is odd, so need to try to
> solve c = na + n(n-1)/2 for integers n,a
>
> Also, try to solve x^2 - y^2 = 0 mod c
Are we not back to Fermat's Method for factorization (again)?
If we're dead lucky and pick a value c such that a and b are very
similar in magnitude, this method works a treat (hence it's very
unwise to pick a public key which factorizes into two nearly equal
numbers. You make the job of cracking your key a lot harder if you
pick the product of two numbers which differ in length by a couple of
bits.)
There is still a gap between the largest factors which can be found
(practically, not theoretically) by techniques suited to "small"
factors, like trial factoring, P-1 and even ECM, and Fermat's Method
which is practical only for "small" values of b-a. (Fermat is just
plain _awful_ at factorizing 3*p for large prime p!) Probably the
continued fractions method is the best line of attack on numbers
which resist "reasonable" efforts with other methods.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
