🚀 go-pugleaf

In article <18112.Aug3004.30.1292@virtualnews.nyu.edu> brnstnd@nyu.edu (D. J. Bernstein) writes:
:In article <1992Aug27.111639.16325@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
:> :Why are you trying to discourage people from
:> :entering the RSA-129 contest, Bob?
:> Now this last accusation really is obnoxious, because it puts words
:> in my mouth that I have never said.
:
:Bob, you stated that a 6-7 digit improvement in GNFS polynomials in this
:range would result in only a 2x speedup. If this were true, it would put
:a rather small cap on the possible benefits of the RSA-129 contest.
:
:It is not, in fact, true. It is wildly inaccurate: as I pointed out
:before, such an improvement could easily gain an order of magnitude in
 
Having done quite a few numbers with the special number field sieve,
I have observed that adding between 25 and 30 decimal digits to the
size of the number I am factoring [using a 5th degree polynomial]
roughly doubles the run time. Adding 30 digits increases the norm
on the integer side by about 6 digits, and does not change the algebraic
side. (that is, as long as the polynomial degree stays the same and the 
coefficients are single digit. [true for the special NFS].)
 If the factor base sizes are well chosen, it therefore seems that
a 6 decimal digit increase on either side of the congruence [but not both]
roughly doubles the run time.

:achieving the effect of lying to the public, even if you don't mean to
:do so. I don't care whether it's obnoxious of me to point this out---I
:can't sit by and watch you corrupt the views of people who haven't
:learned about GNFS and can only go by what they hear from others.
:
:> All you are doing is gainsaying my data without posting data of your own.
:
:That's right. The bulk of data which I have is part of an article I'm
:writing with Arjen Lenstra on our GNFS implementation. That data, like
:your data, is not sufficient to conclude that GNFS will probably be
:slower than MPQS at 129 digits. Yet you keep stating this conclusion.
:
 
I'll let others judge your reply for themselves.

My data supports a crossover point of 135 digits. It might very well
be conservative by 10 or so digits. However, I have never represented
otherwise than that it is an estimate based upon extrapolations of other data.

If you have data that proves me wrong, I would be interested in hearing
about it.

However your continued personal attacks upon me because you don't agree
with my estimates are totally uncalled for.

:My apologies. I mistakenly thought that you were talking about Dickman's
:rho function, which (I can say with some assurance now that I've checked
:my references) a few people attribute to Knuth and Trabb Pardo (because
:Knuth and Trabb Pardo did publish some things about it).
:
:I guess you are referring to the logarithmic sum that Schroeppel
:originally suggested for choosing multiples for the continued fraction
 
Yes. A variation of this function can also be applied to NFS. As with
QS its value can vary quite a bit for numbers of a fixed size, and it
seems as with QS that the higher the value, the easier it is to factor
a number with NFS. The variation can be substantial.  [I'm sure you know
all this; I'm not trying to be patronizing]

:method. If so, I am astounded at your statement that it would be nice to
:have such a function for the algebraic side of GNFS---everyone knows
:what it is, namely the sum of log p times the (easily computable)
:probability that a coprime pair a,b has N(a,b) divisible by p^d, over
:all p and d.
 
Sorry for my lack of precision. I should have said one that can
be computed from the polynomial coefficients directly. Of course if
you know which primes split, which ramify, which are inert, and which
ones split completely, one can compute this. But this means computing
the factor base for every potential polynomial. [which really isn't
that big a deal, I agree, but it is more expensive than changing multipliers
for QS]
--
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"