References: [ Home | Author index | Key index | Search ]

Bernstein2001

D. Bernstein, "Circuits for integer factorization: a proposal," (2001) Available from http://cr.yp.to/factorization.html.

Abstract: The number field sieve takes time L^{1.901...+o(1)} on a general purpose computer with L^{0:950...+o(1)} bits of memory; here L is a particular subexponential function of the input size. It takes the same time on a parallel trial-division machine, such as Cracker or TWINKLE, of size L^{0.950...+o(1)}. It takes time only L^{1.185...+o(1)} on a machine of size L^{0.790...+o(1)} explained in this paper. This reduction of total cost from L^{2.852...+o(1)} to L^{1.976...+o(1)} means that a ((3:009^... +o(1))d)-digit factorization with the new machine has the same cost as a d-digit factorization with previous machines.