Paper 2014/653

Mersenne factorization factory

Thorsten Kleinjung, Joppe W. Bos, and Arjen K. Lenstra

Abstract

We present work in progress to fully factor seventeen Mersenne numbers using a variant of the special number field sieve where sieving on the algebraic side is shared among the numbers. It is expected that it reduces the overall factoring effort by more than 50\%. As far as we know this is the first practical application of Coppersmith's ``factorization factory'' idea. Most factorizations used a new double-product approach that led to additional savings in the matrix step.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in ASIACRYPT 2014
Keywords
Mersenne numbersfactorization factoryspecial number field sieveblock Wiedemann algorithm
Contact author(s)
akl @ epfl ch
History
2015-01-12: last of 25 revisions
2014-08-27: received
See all versions
Short URL
https://ia.cr/2014/653
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/653,
      author = {Thorsten Kleinjung and Joppe W.  Bos and Arjen K.  Lenstra},
      title = {Mersenne factorization factory},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/653},
      year = {2014},
      url = {https://eprint.iacr.org/2014/653}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.