No subject

[Frog3]

x8MjcT6TNxhcVyLEUs7Ljax3sqXTDPdZfpPCNTzO

k
	 <root at hackserv.saiknes.lv>.
Subject: Bernstein's NFS machine
Message-ID: <6a8f1c4391892fa485ed43c718c7377c at disastry.dhs.org>

Analysis of Bernstein's NFS machine when applied to a 1024 bit RSA key
See http://cr.yp.to/papers.html#nfscircuit.

We will ignore O(1) terms to get some ballpark concrete results.

The main parameter for a 1024 bit modulus size:
L = 2^45.  (All powers of 2 are rounded to integers.)

The normal NFS would take time 2^86 and space 2^43 for this size.

Bernstein's NFS takes time 2^53 and space 2^36.

The speedup is (in part) by using ECM in parallel to find smooth numbers.
Also the matrix reduction is done in parallel as well.

For the optimal design balancing these two parts, the numbers we are
checking are of size 2^46.  We are checking for smoothness against a
bound of 2^36.  We need to do two smoothness checks per element.

The parallel ECM machine has 2^36 simultaneous units each checking
smoothness against a bound of 2^36.  Each will do 2^36 tests in time 2^36,
for a total throughput of 2^71 in time 2^36.  Actually this is wrong;
each test will take 2^18, which is counted as negligible, but in fact
it makes the time be 2^54.  This part is hidden in an O(1) but it is a
significant slowdown.

We need to do 2^89 tests at an estimated rate of 2^72 tests per 2^36
time for an estimate of 2^53 time.  Applying the correction that ECM
test time is not negligible gives us an estimate of 2^71 time.

The cost is the need to build a machine that can do 53 billion
simultaneous, independent ECM factorizations for smoothness testing.
It's not clear how amenable this would be to hardware implementation.

A time of 2^71 is considerably less threatening than 2^53.


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