Batch NFS

D.J. Bernstein, T. Lange

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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. Keywords: integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts
Original languageEnglish
Title of host publicationSelected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers
EditorsA. Joux, A. Youssef
PublisherSpringer
Pages38-58
ISBN (Print)978-3-319-13050-7
DOIs
Publication statusPublished - 2014
Event21st International Conference on Selected Areas in Cryptography (SAC 2014) - Sackville, Canada
Duration: 14 Aug 201415 Aug 2014
Conference number: 21

Publication series

NameLecture Notes in Computer Science
Volume8781
ISSN (Print)0302-9743

Conference

Conference21st International Conference on Selected Areas in Cryptography (SAC 2014)
Abbreviated titleSAC 2014
CountryCanada
CitySackville
Period14/08/1415/08/14

Fingerprint

Dive into the research topics of 'Batch NFS'. Together they form a unique fingerprint.

Cite this