What's going on with factorization

R. A. Hettinga rah at shipwright.com
Wed Feb 27 20:49:32 EST 2002


--- begin forwarded text


Status:  U
Date: 28 Feb 2002 01:33:48 -0000
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
From: "D. J. Bernstein" <djb at cr.yp.to>
To: fork at xent.com
Subject: What's going on with factorization
Sender: fork-admin at xent.com
List-Id: Friends of Rohit Khare <fork.xent.com>

1. It has been widely known since the 1970s that special-purpose
hardware has a smaller cost _exponent_ than traditional architectures
for many interesting computations. (Certainly not for all computations:
consider, for example, computing the nth iterate of a secure hash, for
large n.)

Improvements in _exponent_ go far beyond saying ``Of course you can get
an improvement from special-purpose hardware.'' The speedup grows with
the problem size.

2. It has been widely known since 1994 (van Oorschot and Wiener) how to
build fast parallel special-purpose hardware for generic, and nearly
generic, discrete-log computations. Current elliptic-curve discrete-log
computations are nearly generic discrete-log computations.

My paper doesn't have any effect on the cost of elliptic-curve
discrete-log computations.

3. What my paper shows is that the number field sieve can be done with
very little memory per processor and a surprisingly small (though still
quite noticeable) amount of work per processor, including communication
costs. Consequently special-purpose hardware for the number field sieve
has a smaller cost exponent than traditional architectures. The new cost
exponent is within 4% of the obvious lower bound.

The conventional wisdom was that the number field sieve required a large
chunk of memory per processor (many megabytes for recent factorizations,
much more for future factorizations), and that communication with memory
was a bottleneck, so special-purpose hardware wouldn't help much. The
Georgia Cracker and TWINKLE designs didn't change the cost exponent.

4. At this point, nobody knows what the cost of this computation will be
for 1024-bit or 1536-bit or 2048-bit factorizations. All that is known
is the cost exponent.

Let's say the new machine handles f(b)-bit keys in the same time that
previous machines handled b-bit keys. It is known that f(b) is slightly
larger than 3b for _very large_ values of b. It is, however, not known
how close f(512) is to 1536. It is not even known whether f(512) is
larger than 512.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago


http://xent.com/mailman/listinfo/fork

--- end forwarded text


-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list