D. J. Bernstein
Integer factorization
Circuits for integer factorization

The cost of NFS for very large integers

I realized in September 2000 that special-purpose circuits have smaller cost exponents than conventional computers for NFS factorizations. Consequently circuits are vastly more cost-effective than conventional computers for NFS factorizations of very large integers.

You should understand what o(1) means before you read this page.

What are the exponents?

In the following description, L is exp((log n)^(1/3) (log log n)^(2/3)), where n is the number being factored.

Conventional NFS implementations (and Shamir's ``TWINKLE''), as described in (for example) Silverman's cost-analysis paper or the Lenstra-Shamir TWINKLE paper, take time L^(1.901...+o(1)) on a machine of size L^(0.950...+o(1)).

Conventional NFS is perfectly parallelizable: one can trade time for hardware cost, as shown in the following table.
Machine Computation time Machine size (hardware cost)
Conventional NFS, literature L^(1.901...+o(1)) L^(0.950...+o(1))
Conventional NFS, literature L^(1.891...+o(1)) L^(0.960...+o(1))
Conventional NFS, literature L^(1.881...+o(1)) L^(0.970...+o(1))
Conventional NFS, literature L^(1.871...+o(1)) L^(0.980...+o(1))
Conventional NFS, literature L^(1.861...+o(1)) L^(0.990...+o(1))
Conventional NFS, literature L^(1.851...+o(1)) L^(1.000...+o(1))
Conventional NFS, literature L^(1.841...+o(1)) L^(1.010...+o(1))
Conventional NFS, literature L^(1.831...+o(1)) L^(1.020...+o(1))
etc.

In email to me in April 2002, Carl Pomerance pointed out that there is a more cost-effective way to do the NFS calculations on conventional computers:
Machine Computation time Machine size (hardware cost)
Conventional NFS, optimized L^(1.754...+o(1)) L^(1.006...+o(1))
Conventional NFS, optimized L^(1.744...+o(1)) L^(1.016...+o(1))
Conventional NFS, optimized L^(1.734...+o(1)) L^(1.026...+o(1))
etc.

My October 2001 grant proposal explains how to reduce both the time exponent and the hardware cost exponent:
Machine Computation time Machine size (hardware cost)
Circuit NFS L^(1.185...+o(1)) L^(0.790...+o(1))
Circuit NFS L^(1.175...+o(1)) L^(0.800...+o(1))
Circuit NFS L^(1.165...+o(1)) L^(0.810...+o(1))
etc.
These circuits are, for large input sizes, vastly more cost-effective than the best known way to carry out NFS on conventional computers.

Key size expansion

The cost improvement from conventional NFS to circuit NFS means that circuit NFS can factor larger numbers than conventional NFS.

Consider, for example, circuit NFS applied to keys with twice as many bits. Multiplying log n by 2 means multiplying log L by 1.2599...+o(1), and therefore multiplying the time and cost exponents by 1.2599...+o(1):
Machine Computation time Machine size (hardware cost)
Circuit NFS on 2x larger keys L^(1.493...+o(1)) L^(0.995...+o(1))
Circuit NFS on 2x larger keys L^(1.483...+o(1)) L^(1.005...+o(1))
Circuit NFS on 2x larger keys L^(1.473...+o(1)) L^(1.015...+o(1))
etc.
The computation time and hardware cost for circuit NFS on keys double the size are substantially smaller than the computation time and hardware cost for conventional NFS on keys of the original length.

When circuit NFS is applied to keys approximately triple the size, its computation time and hardware cost (at various parallelizations) become identical to the computation time and hardware cost (at various parallelizations) of conventional NFS as described in the literature. The exact ratio is 3.009...+o(1), the cube of the quotient of 1.185...+o(1)+0.790...+o(1) and 1.901...+o(1)+0.950...+o(1).

In other words: Compared to conventional NFS as described in the literature, circuit NFS can factor numbers with 3.009...+o(1) times as many digits. Similarly: Compared to conventional NFS as optimized by Pomerance, circuit NFS can factor numbers with 2.72...+o(1) times as many digits.