🚀 go-pugleaf

         Dan Berstein posts:
: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.
:being equal. (Most polynomials are somewhere in the middle.)
         Actually it is about 100 times better than random using
your stated figure of merit.  More to the point it is only about 10
times better than simply trying a few million values of m.
         Dan Berstein also posts:
: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.
         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.
         Dan Berstein also posts:
: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.
         I must disagree, extensive searches without an accurate figure
of merit are basically a waste of time.  I have little enthusiasm for
burning weeks of computer time searching for good fifth degree poly-
nomials only to learn that a more complete figure of merit shows that
I should have been searching for sixth degree polynomials.
         Dan Berstein also posts:
: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.
         As I point out above, considering all multiples of n increases
the density of representations (of the form f(m), f degree 5) by, sum
over k of k**(-9/4), which is less than 2 (not 10**5).  I can't comment
on searching for two-variable polynomials without knowing the figure
of merit.
                       James B. Shearer