Bernstein's NFS machine

[Wei Dai]

I haven't checked all of the numbers, but I think Frog3's analysis is
largely correct. However, the two O(1)'s below should be replaced with
o(1)'s.

Very informally, think of O(1) as some constant, and o(1) as converging to
0. One possibly confusing thing about Berstein's paper is that in the
sentence "for a given cost, the number of digits of n has grown by a
factor of 3.0090581972... + o(1)", the o(1) is most likely negative for
practical key lengths.

On Tue, Feb 26, 2002 at 02:04:16AM -0000, Frog3 wrote:
> 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

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