[24645] in Cypherpunks
New GNFS Factoring Record
daemon@ATHENA.MIT.EDU (Mike Duvos)
Fri Dec 30 21:44:34 1994
From: mpd@netcom.com (Mike Duvos)
To: cypherpunks@toad.com
Date: Fri, 30 Dec 1994 18:34:00 -0800 (PST)
Arjen Lenstra posted an article in sci.crypt earlier today
reporting on the factorization of a 119 digit number using the
General Number Field Sieve.
This is a new record factorization for the algorithm, surpassing
the 116 digit number factored in July of this year.
I would encourage anyone interested in factoring to read the
article, which I will not waste bandwidth by quoting here. A few
of the more interesting points follow.
Lenstra estimates that GNFS would have factored RSA-129 in
approximately one-quarter of the time employed by the QS
algorithm used for that task a while back.
100,001 primes were used for the rational factor base. 360,001
were used for the algebraic factor base. Sieving took
aproximately 250 MIPS years. Selection of the polynomial
took three days on a DEC 3000. The factorization was found on
the third dependency.
--
Mike Duvos $ PGP 2.6 Public Key available $
mpd@netcom.com $ via Finger. $
