🚀 go-pugleaf

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