🚀 go-pugleaf

In article <9208260234.AA05450@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
>          Well if you actually had a complete GFNS implementation for
> general numbers I believe you would obtain more reliable estimates by
> performing a whole bunch of "wimpy" factorizations as opposed to a
> single factorization of RSA-129.

Unfortunately not. Example: Arjen Lenstra and I tried our MasPar GNFS
implementation on a 66-digit general number. We used the smallest
sensible factor bases for that architecture---namely 16384 primes on
each side of the sieve---and without any tuning found that we had more
than enough relations *from ff's alone*. No partials were necessary.

When you want to make predictions, the statistics from such a tiny
factorization are worse than useless. One can safely predict how long
GNFS will need to factor a 130-digit number---within an order of
magnitude.

>          You might also have a reliable figure of merit for what con-
> stitutes a good polynomial representation.

This is, unfortunately, an open research problem. The best procedure I
know is to generate many polynomials with relatively small coefficients,
then look for polynomials with ``many'' small algebraic primes in a
certain sense. This is exactly what the RSA-129 contest is meant to
achieve.

(For those who missed the start of the discussion: If your mail address
is joe@foo.bar and you want to see the contest announcement, send mail
to factor@src.dec.com with the two lines

path#joe@foo.bar
rsastatus#

and wait a few minutes.)

---Dan