On 14 Jul 99, at 1:26, Paul Leyland wrote:
> Fermat observed that if one could represent an integer as the difference of
> two squares, its factorization would be at hand; he then gave an efficient
> (for the 17th Century!) algorithm for finding the squares.
>
> More recently, algorithms such Continued Fraction, Quadratic Sieve and
> Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a
> small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The
> algorithms differ in how they construct the x and y and are *much* more
> efficient than Fermat's algorithm, but the underlying idea is the same.
>
Actually Fermat's Method is extraordinarily efficient at finding a
factorization n = a * b when (a - b) is small. It's also easy to
code, needs very little storage and (once initialized) requires only
relatively low-precision arithmetic, therefore making the attempt
fast (per iteration).
This is one reason why it's a Very Bad Idea to use the product of a
pair of primes of similar size as a public key. In fact, Fermat's
Method will factorize the product of a pair of twin primes almost
instantaneously, irrespective of their size!
Just out of interest, did anyone ever try Fermat's Method on some of
the "tougher" numbers in the Cunningham tables ... Fermat's Method
can be speeded up by a large factor since we _know_ the form of the
factors - of course, it's still going to fail to find factors in a
reasonable time unless a pair of factors of very similar size do, in
fact, exist. Also, any factors found would not neccessarily be prime,
though cracking the two "halves" ought to be easier than tackling the
whole.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
