🚀 go-pugleaf

In article <9208202353.AA21728@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  [ Bob Silverman writes: ]
> > 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.
> Well, let us estimate how many numbers between 10**128 and
> 10**129 can be so represented.

Keep in mind that---even if Bob's pessimistic estimate of 14 digits is
close to reality, which I very much doubt---f(m) can be any multiple of
n, and two-variable polynomials f(m_1,m_2) also work for GNFS. If we
were to allow 10^5 multiples of n, 10^24 choices of m_1, 10^24 choices
of m_2, and 10^14 choices of each c_i, then there would be roughly 10^9
sufficiently small polynomials for RSA-129. So from a theoretical point
of view there's no problem.

In practice, of course, finding a good polynomial takes a lot of work,
which is why we're running this contest. Obviously it doesn't make sense
to spend more time searching for good polynomials than it would take to
actually run GNFS, but the latter will take months or years on high-end
hardware; we certainly haven't reached the break-even point.

Anyone who missed the original contest announcement two weeks ago can
send mail to factor@src.dec.com with the two lines

  path#yourname@your.host
  rsastatus#

---Dan