🚀 go-pugleaf

In article <9208200145.AA29470@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
>
>         D. J. Berstein wrote:
>:To factor RSA-129 with the general number field sieve (GNFS) requires a
>:fifth-degree polynomial
>:
>:  f(x) = c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0,
>:
>:with integer coefficients c_i, and a positive integer m such that f(m)
>:is a small positive integer multiple of RSA-129. Given any random choice
>:of m you can easily expand RSA-129 in base m and find the coefficients
>:c_i. However, for GNFS to finish in a reasonable time, the coefficients
>:must be significantly smaller than random.
>
>         How small do the coefficients have to be?  I have been led to
>believe that the speed of the GNFS overall does not depend much on the
>efficiency of the search for a good polynomial.  If this is the case it
>would seem to be unwise to devote a lot of effort to finding a good poly-
>nomial.  What is the point of this contest?
>                           James B. Shearer
 
This is NOT the case. The performance is VERY sensitive to the size
of the coefficients and it is worthwhile spending a significant amount
of time trying to find small coefficients.

For a 5th degree polynomial, 'random' coefficients will be about 21 or 22
digits. One needs to factor two sides of a congruence, one in Z, the other
in Q(alpha). The norms on the integer side will be about 10^32.
[M ~ 10^(130/5) and the average b will be about 10^6]. On the algebraic
side they will be about (10^6)^5 * poly coef or about 10^52.
Of course many will be smaller, [for small b]

I estimate that to be competitive with the Quadratic sieve they need
to find coefficients of 'about' 14 digits.  I am not sure it is
possible.

Their estimates may, of course, differ depending on their assumptions.

I have already done about 1% of the work to factor the RSA-129 with
the two-large-prime variation of the Quadratic Sieve.  I was going
to do it completely, but a deal with Sun to use their internal net
[3000 workstations!] fell through due to management difficulties.
I estimate it was going to take between 5000 and 6000 MIPS-YEARS
to do the computation.


Now if I could just scrape together 3000 Sparcs for 2-3 months, I
could finish the factorization.

--
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"