**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.

**Category / Keywords: **public-key cryptography / integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts

**Original Publication**** (with minor differences): **SAC 2014

**Date: **received 9 Nov 2014

**Contact author: **authorcontact-batchnfs at box cr yp to

**Available format(s): **PDF | BibTeX Citation

**Version: **20141110:070532 (All versions of this report)

**Short URL: **ia.cr/2014/921

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]