🚀 go-pugleaf

In article <9208220157.AA02629@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
> More to the point it is only about 10
> times better than simply trying a few million values of m.

10 times better means about 40% reduction in run time.

We are talking about *years* on a supercomputer---and don't think that
RSA-129 is the only number that anyone wants to factor! I often spend
time optimizing a section of code responsible for less than one percent
of the run time of a program---and then another section, another
section, another section, and all of a sudden I try the program and it's
five or ten percent faster than before. This is a good thing.

James, if you don't appreciate the value of a 40% speedup, don't
participate in the contest.

> Since the density of good representations for k*n goes as
> k**(-9/4) considering multiples of n is unlikely to give a significant
> improvement.

I don't know what grounds you're arguing from. Nor do I particularly
care. You were worrying about running out of good polynomials. The fact
is that multiples of n give polynomials nearly as good as polynomials
for n itself.

> I must disagree, extensive searches without an accurate figure
> of merit are basically a waste of time.

If you feel that way, don't participate. Other people have submitted
good polynomials and I'm sure the current record won't last long. Nobody
knows an ``accurate figure of merit'' for GNFS polynomials: nobody has
ever exhibited an accurate method of estimating how much time GNFS will
use with various parameters, though GNFS detractors always seem to
pretend otherwise.

The point of this contest is not to find the minimum value of the
total-coefficients-times-m measure, although that measure isn't bad; the
reason that I specified an upper limit for that measure was to weed out
contest entrants who weren't serious. The point of this contest (at
least as I see it---I can't speak for Arjen Lenstra) is to find a
reasonable number of reasonably good polynomials in the hope of
minimizing the time needed for GNFS to factor RSA-129.

>          Dan Berstein also posts:

Bernstein. Sure you didn't drop any digits in those polynomials? :-)

---Dan