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

Internet Message Format | 1992-08-26 | 3.4 KB

Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!virtualnews.nyu.edu!brnstnd
From: [e-mail] (D. J. Bernstein)
Newsgroups: sci.crypt
Subject: Re: RSA-129 contest
Message-ID: <[e-mail]>
Date: 27 Aug 92 00:12:01 GMT
References: <[e-mail]> <[e-mail]>
Organization: IR
Lines: 59

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