Batch NFS

Daniel J.  Bernstein; Tanja Lange

Paper 2014/921

Batch NFS

Daniel J. Bernstein and Tanja Lange

Abstract

This paper shows, assuming standard heuristics regarding the number-field sieve, that a "batch NFS" circuit of area L^{1.181...+o(1)} factors L^{0.5+o(1)} separate B-bit RSA keys in time L^{1.022...+o(1)}. Here L=exp((log 2^B)^{1/3}(log log 2^B)^{2/3}). The circuit's area-time product (price-performance ratio) is just L^{1.704...+o(1)} per key. For comparison, the best area-time product known for a single key is L^{1.976...+o(1)}. This paper also introduces new "early-abort" heuristics implying that "early-abort ECM" improves the performance of batch NFS by a superpolynomial factor, specifically exp((c+o(1))(log 2^B)^{1/6}(log log 2^B)^{5/6}) where c is a positive constant.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. SAC 2014
Keywords: integer factorization number-field sieve price-performance ratio batching smooth numbers elliptic curves early aborts
Contact author(s): authorcontact-batchnfs @ box cr yp to
History: 2014-11-10: received
Short URL: https://ia.cr/2014/921
License: CC BY

BibTeX

@misc{cryptoeprint:2014/921,
      author = {Daniel J.  Bernstein and Tanja Lange},
      title = {Batch {NFS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/921},
      year = {2014},
      url = {https://eprint.iacr.org/2014/921}
}