🚀 go-pugleaf

In article <9208260234.AA05450@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
>
>         Dan Bernstein posts:
>:Instead he challenges me, saying, ``Dan, why don't you say what your
>:estimates are?'' The answer is obvious: *I don't know*. I don't yet have
>:reliable estimates, and until somebody factors a 130-digit general
>:number, *nobody* will have reliable estimates.
>         and also:
>:> Define 'wimpy' please for the rest of the audience.
>:
>:Under 100 digits.
>
>         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.
>         You might also have a reliable figure of merit for what con-
>stitutes a good polynomial representation.  Extensive searches for
>polynomials using different criteria than the ones you will eventually
>use to select a polynomial (which you are encouraging people to per-
>form) are a waste of computer time (since such searches are inherant-
>ly inefficient).
 
Actually, estimating how long the general number field sieve
will take with respect to the quadratic sieve CAN be done without factoring
any numbers with GNFS.
 
What really matters is not the actual coefficients, but the size of the 
norms of the elements on both sides of the congruence. Based upon
work with the special number field sieve, I can estimate that if one
uses the same polymonial, but increases the integer side (the value of M)
by about 6-7 digits then one roughly doubles the run time for numbers 
near 130 digits. Similarly, if one holds the left size the same, but increases
the coefficients on the right by 6-7 digits one also roughly doubles the
run time. 

For RSA-129 'random' coefficients have about 20-21 digits. If one
reduces these to 14 digits, one will roughly cut the run time in half.

The problem I have is that one must add the time you spent looking for
good polynomials to the total run time. However, looking for good
polynomials is non-deterministic. We do not know of a deterministic
method which, if you spend time t, you will succeed in reducing the
coefficients by size F(t). Thus, you cannot predict AT all how long
a factorization will take. On the other hand, using the base M method,
while sub-optimal, is deterministic.

If you estimate sieve time is T, and you spend (say) .2T looking 
for a better polynomial, there is no guarantee of finding one, and
you will have increased total time by 20% for no good reason. Nor do
you have assurances that spending the extra time will reduce the sieve time
by more than the time you spent searching.


Another problem is that if many small primes split completely in
the extension field, this is beneficial to factoring the algebraic
side. It may be that a polynomial with slightly larger coefficients
is in fact BETTER than one with slightly smaller, if the extension
field it generates has more small primes that split.

Until MANY numbers near 130-140 digits have actually been factored
we will not have accurate estimates if one allows a random search
for optimal polynomials. However, if one sticks to the base-M method,
one can get fairly accurate estimates of run-time simply by looking
at the size of the norms and extrapolating from other factorizations.
The run-time is very predictable from these norms.

One thing that helps estimating the run time of a QS factorization
is the Knuth-Schroeppel function. It would be nice to have a similar
function for the algebraic side of NFS. [finding one for the integer
side is easy].

I have done the sieving for quite a few numbers with GNFS in the 30-90
digit range, selecting polynomials by the base-M method. I did 10
numbers each at 30,35,40,45,50,60,70,80, and 90 digits. The variance
was rather high, but the average gave a fairly smooth curve for
the run time. I have factored over 500 numbers with QS between 30
and 105 digits and this data gives a *very* smooth curve when averaged.
It is quite easy to get the o(1) term from these curves and use them
to estimate where they intersect. From this, I get a crossover of
about 135 digits.
 
The thing I am most uncertain about is whether I used an optimal
factor base size for this GNFS work. I suspect I may have used
factor bases that were too small. This would have the effect of
slightly increasing the run time and thereby raise the estimate of
the crossover point. 

Doing RSA-129 alone will not do anything towards verifying this
estimate, because of the fairly high variance. We need to do perhaps
a couple of dozen numbers at 120, 125, 130, 135, and 140 digits each
before we can really determine the crossover point. The amount of
CPU cycles required for doing this work is currently unavailable.

Finally, to answer one of Dan's other questions:

I estimate that GNFS, with a 5th degree polynomial and random 21 digit
coefficients will take twice [say between 1.8 and 2.2] times as long to
factor RSA-129 as PPMPQS will. Reducing coefficients to 14 [or maybe 15]
digits will equalize the run times. This assumes that RSA-129 behaves like
an 'average' 129 digit number, and that the chosen number field does not 
have a particularly high density of small primes that split completely.
I do not know of any way to determine whether RSA-129 is an 'average' 129
digit number short of factoring quite a few numbers of this size. Note that
the variance in combining cycles also plays a role. I suspect that to
fully analyze how many cycles one should expect from a given number of
factored relations we would need an effective version of the Chebotarev
Density Theorem, and such a theorem does not yet exist.

--
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 <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

In article <1992Aug26.132003.5928@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
> Actually, estimating how long the general number field sieve
> will take with respect to the quadratic sieve CAN be done without factoring
> any numbers with GNFS.

Of course---that's exactly what you and Adleman have been doing. The
problem is that you haven't been doing it *accurately*. Here, for the
benefit of sci.crypt readers, I'll run through the inaccuracies in the
above article.

Your general statement about 6-7 digits corresponding to a 2x speedup
for 130-digit numbers is not accurate; even a casual analysis of
Dickman's rho function (why do you call that ``the Knuth-Schroeppel
function''? Dickman is the one who defined it) would show that the
speedup is more than 5. Why are you trying to discourage people from
entering the RSA-129 contest, Bob?

You say that ``if many small primes split completely in the extension
field, this is beneficial to factoring the algebraic side''---but the
truth is that *any* small prime splitting *at all* in the extension
field provides a noticeable speedup. *Complete* splitting is rare.

You say that ``looking for good polynomials is non-deterministic'' and
neglect to analyze the run time. In fact, as far as anyone knows, all
the coefficients past the first three behave randomly, and it's easy to
estimate the expected time to find a good polynomial. It's far more
difficult to pin down the GNFS run time. Why are you trying to
discourage people from entering the RSA-129 contest, Bob?

You chat about ``an optimal factor base size for this GNFS work.'' It is
clear to me that the algebraic factor base should be much larger than
the rational factor base for well-tuned general NFS factorizations; you
should be talking about the *two* sizes, not one.

> Finally, to answer one of Dan's other questions:
> I estimate that GNFS, with a 5th degree polynomial and random 21 digit
> coefficients will take twice [say between 1.8 and 2.2] times as long to
> factor RSA-129 as PPMPQS will. Reducing coefficients to 14 [or maybe 15]
> digits will equalize the run times.

You *still* haven't answered the question; you still hedge by failing to
analyze the small algebraic primes. Look, Bob, if you can't justify your
GNFS run time estimates without all these caveats, then you should
retract all the estimates you've made which *don't* come with the
caveats.

> Note that
> the variance in combining cycles also plays a role. I suspect that to
> fully analyze how many cycles one should expect from a given number of
> factored relations we would need an effective version of the Chebotarev
> Density Theorem, and such a theorem does not yet exist.

I, on the other hand, suspect that a proper analysis---one which gives
usable estimates of the mean and variance of the number of cycles, where
we can take ``within a few percent'' as defining ``usable''---depends on
nothing more than chopping up the large prime interval and applying the
prime number theorem (or maybe just Mertens's theorem).

---Dan

In article <19122.Aug2700.12.0192@virtualnews.nyu.edu> brnstnd@nyu.edu (D. J. Bernstein) writes:
:In article <1992Aug26.132003.5928@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
:> Actually, estimating how long the general number field sieve
:> will take with respect to the quadratic sieve CAN be done without factoring
:> any numbers with GNFS.
:
:Of course---that's exactly what you and Adleman have been doing. The
:problem is that you haven't been doing it *accurately*. Here, for the
:benefit of sci.crypt readers, I'll run through the inaccuracies in the
:above article.
 
All you are doing is gainsaying my data without posting data of your own.

:Your general statement about 6-7 digits corresponding to a 2x speedup
:for 130-digit numbers is not accurate; even a casual analysis of
:Dickman's rho function (why do you call that ``the Knuth-Schroeppel
:function''? Dickman is the one who defined it) would show that the
 
you are confusing the two functions. go ask Arjen about the 
Knuth-Schroeppel function.

:speedup is more than 5. 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.

:You say that ``if many small primes split completely in the extension
:field, this is beneficial to factoring the algebraic side''---but the
:truth is that *any* small prime splitting *at all* in the extension
:field provides a noticeable speedup. *Complete* splitting is rare.

Not that rare. the frequency is 1 over the degree of the Galois closure
of the field.
 
So, Dan, if you can do better, why don't you display your obviously
superior knowledge of such things by giving us your data and estimates.
--
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"