🚀 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

In article <8146.Aug2205.17.2492@virtualnews.nyu.edu> brnstnd@nyu.edu (D. J. Bernstein) writes:
 
stuff deleted...

>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.
 
Too bad you were not at the public-key crypto conference in Oberwolfach
last year. I presented the results of quite a few benchmarks for the
sieving phase of GNFS on general numbers ranging from 30 to 90 digits.
I would characterize this as an accurate way of estimating how much
time GNFS will take, wouldn't you? I also have at least an order of
magnitude more data than anyone else on the performance of the quadratic
sieve. From this data it is not difficult to project a crossover point
of around 135 digits. The data I have also shows how much speedup is
obtained by reducing the size of the coefficients. My data says that
you will need to find 14 digit coefficients for GNFS to compete with
PPMPQS in doing RSA-129.
 
But Dan says he does not believe this 'pessimistic estimate'.

I am not 'pretending' anything, despite Dan's insults. I have real
data.   Dan's labelling of detractors as 'pretending' is both insulting
and unprofessional.
 
Of course he can't back up this belief, because he doesn't have
enough data on the performance of both methods. Of course he is
now obtaining data on the sieving part of GNFS now that he has
it coded. But he still lacks data on QS. Lenstra and Manasse have
done a few dozen numbers with QS. I've done in excess of 500.

I am also curious as to whether his comparison with QS also considers
the time to do the final square root along with the sieve time? He
reported that for 2,488+, the final square root took about 15% of the
total sieve time. [1 day vs. 6 days]
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

In article <1992Aug22.113206.4385@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
> I presented the results of quite a few benchmarks for the
> sieving phase of GNFS on general numbers ranging from 30 to 90 digits.

And you try to extrapolate by 45 digits from your highly suboptimal
polynomial choices. You didn't even take Pollard's lattice sieve into
account.

I defy you to make a statement of the form ``GNFS will use more than G
MIPS-years to factor RSA-129, while MPQS will take under M MIPS-years to
factor RSA-129, and G > M,'' rather than hiding behind loose comparisons
such as ``I estimate the crossover point to be around 135 digits.''
Either make a definite statement so that I can demonstrate by actual
experiments that you're wrong, or admit that you can't accurately
estimate the time taken by GNFS.

> Dan's labelling of detractors as 'pretending' is both insulting
> and unprofessional.

I don't think so. Your estimates of GNFS's speed have no more validity
than Adleman's ridiculous estimates a year ago. They are based on
wishful thinking (such as your incorrect estimate of coefficient digits
for a 145-digit number on sci.crypt a few weeks ago) as well as neglect
of existing algorithmic improvements (such as the special-q method).

It was irresponsible of Adleman to state that it wasn't clear whether
GNFS would be faster than MPQS for 330-digit numbers. It is just as
irresponsible of you to claim a 135-digit crossover point. It is neither
insulting nor unprofessional for me to demand that you make your
estimates of GNFS speed sufficiently detailed that I can prove them
false.

> But he still lacks data on QS. Lenstra and Manasse have
> done a few dozen numbers with QS. I've done in excess of 500.

I can't speak for either Arjen Lenstra or Mark Manasse, but it seems to
me that a few dozen numbers ranging up to 116 digits have far more
relevance to 129-digit factorizations than several hundred wimpy
numbers.

---Dan