Paper 2006/109

A Simpler Sieving Device: Combining ECM and TWIRL

Willi Geiselmann, Fabian Januszewski, Hubert Koepfer, Jan Pelzl, and Rainer Steinwandt

Abstract

A main obstacle in manufacturing the TWIRL device for realizing the sieving step of the Number Field Sieve is the sophisticated chip layout. Especially the logic for logging and recovering large prime factors found during sieving adds significantly to the layout complexity. We describe a device building on the Elliptic Curve Method (ECM) that for parameters of interest enables the replacement of the complete logging part in TWIRL by an off-wafer postprocessing. The postprocessing is done in real time, leaving the total sieving time basically unchanged. The proposed device is an optimized ECM implementation building on curves chosen to cope with factor sizes as expected in the output of TWIRL. According to our preliminary analysis, for the relation collection step expected for a 1024-bit factorization our design is realizable with current fab technology at very moderate cost. The proposed ECM engine also finds the vast majority of the needed cofactor factorizations. In summary, we think the proposed device to enable a significant decrease of TWIRL's layout complexity and therewith its cost.

Note: corrected complexity estimate

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. accepted at ICISC 2006
Keywords
RSANFSECMcryptanalytic hardware
Contact author(s)
rsteinwa @ fau edu
History
2006-08-26: last of 2 revisions
2006-03-22: received
See all versions
Short URL
https://ia.cr/2006/109
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/109,
      author = {Willi Geiselmann and Fabian Januszewski and Hubert Koepfer and Jan Pelzl and Rainer Steinwandt},
      title = {A Simpler Sieving Device: Combining ECM and TWIRL},
      howpublished = {Cryptology ePrint Archive, Paper 2006/109},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/109}},
      url = {https://eprint.iacr.org/2006/109}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.