NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/sci/crypt/3011

Text File | 1992-08-26 | 6.2 KB | 127 lines

Newsgroups: sci.crypt
Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!slc3.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
From: [e-mail] (Robert D. Silverman)
Subject: Re: RSA-129 contest
Message-ID: <[e-mail]>
Sender: [e-mail] (News Service)
Nntp-Posting-Host: gauss.mitre.org
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
References: <[e-mail]>
Date: Wed, 26 Aug 1992 13:20:03 GMT
Lines: 114

In article <[e-mail]> [e-mail] 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"