🚀 go-pugleaf

In article <1992Oct29.222711.26229@netcom.com> strnlght@netcom.com (David Sternlight) writes:
>
>Arjen Lenstra posts a 3-week factorization of a 158 digit number which
>is the product of a 69 and 90 digit prime. Please help a layman
>understand the significance of this.
>
>What does this mean, if anything, for the "cracking" of an RSA 1024 bit
>key? for DES?
>


It means nothing.

The only reason we (factoring researchers) can do integers of this size
is that they have a very special form that allows the number to be
written as a polynomial with VERY (in this case single digit) coefficients.

i.e. let N = 2^523 - 1. Then 4N = 2^525 - 4. Let M = 2^(525/5) = 2^105.

Then 4N = M^5 - 4.   It is only because this polynomial in M has small
coefficients that the number can be factored.

If you should try to represent an arbitrary number of this size as a
5th degree (not necessarily monic) polynomial, the coefficients will
generally be 'about' 24 or 25 digits. A big difference.

Nevertheless, it was a nice piece of work by Arjen and Dan. 

Bob
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"