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

In article <9208200145.AA29470@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
> What is the point of this contest?

To find a good polynomial for RSA-129.

To factor RSA-129 with GNFS would take many hundreds or thousands of
MIPS-years with a random polynomial. In the two weeks since the contest
was announced, quite a few people have submitted polynomials, and the
best so far---yours---is roughly 1000 times better than random.

That means *three times less work* for GNFS. That is a huge difference.

Polynomials another 10 or 20 times better could well be good enough for
GNFS to complete in a reasonable time. There are also algebraic criteria
which give some polynomials a significant ``boost.'' For instance, a
polynomial which has many roots modulo 3, 5, and 7 is nearly 100 times
better than a polynomial which has no roots modulo 3, 5, or 7, all else
being equal. (Most polynomials are somewhere in the middle.)

Keep in mind that f(m) doesn't have to equal n---it be any positive
multiple. So there are a huge number of polynomials to search through.
Someone who uses clever techniques to search through selected m's may
have a better chance of finding a good polynomial than someone who runs
through billions of m's by brute force (though brute force never
hurts!). It may also be possible to use the extra structure of
two-variable polynomials f(m_1,m_2) to obtain better results there---
certainly the optimal two-variable polynomials have much smaller
coefficients than the optimal one-variable polynomials. These are open
problems. Nobody knows what the best way to search for polynomials is.

In any case, the polynomial-searching contest has produced spectacular
results so far. Keep those submissions coming in! I'm sorry I don't yet
have precise estimates of exactly how much RSA-129 GNFS time is saved by
any particular polynomial, but I can assure you that a few weeks of
polynomial searching will be time very, very well spent.

---Dan