> From: Brian J. Beesley [mailto:[EMAIL PROTECTED]]
> 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).
All of this is completely true, as long as the concept "small" is well
understood.
Fermat's method is excellent if (a-b) is about sqrt(a) or
sqrt(sqrt(N)). If it is much larger than this, Fermat's method is
hopelessly slow. In a "typical case", Fermat's method is slower than
trial division! "Typical" needs careful definition, of course. I
won't go into the assumptions and derivations, but in a "typical"
integer, successive factors (in numerical order) are about twice the
length of their predecessors. This means that (a-b) is far from
"small". A more rigorous formulation of this behaviour can be found
in standard texts, such as Knuth's Art of Computer Programming, Vol II.
> 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!
Indeed, if "similar" is interpreted as is "small" above. In a typical
case, a 512-bit key, the two primes will have about 78 digits each.
They have to be identical to the first 35-ish digits to be "similar".
If the primes are chosen randomly, the random number generator has to
be truly dreadful for that to happen by chance.
> 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.
Not as far as I know, though some "similar" factors are known from
algebraic considerations. These are known as Aurifeuillean
factorizations. A simple example is
2^{2h} + 1 = (2^h-2^k+1) * (2^h+2^k+1) where h = 2k-1.
Paul
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
