Paper 2016/401

Tower Number Field Sieve Variant of a Recent Polynomial Selection Method

Palash Sarkar and Shashank Singh

Abstract

At Asiacrypt 2015, Barbulescu et al. performed a thorough analysis of the tower number field sieve (TNFS) variant of the number field sieve algorithm. More recently, Kim and Barbulescu combined the TNFS variant with several polynomial selection methods including the Generalised Joux-Lercier method and the Conjugation method proposed by Barbulescu et al. at Eurocrypt 2015. Sarkar and Singh (Eurocrypt 2016) proposed a polynomial selection method which subsumes both the GJL and the Conjugation methods. This study was done in the context of the NFS and the multiple NFS (MNFS). The purpose of the present note is to show that the polynomial selection method of Sarkar and Singh subsumes the GJL and the Conjugation methods also in the context of the TNFS and the multiple TNFS variants. This was not clear from the recent work by Kim and Barbulescu. Applying the new polynomial selection method to the TNFS variants results in new asymptotic complexities for certain ranges of primes.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
sha2nk singh @ gmail com
History
2016-04-26: last of 2 revisions
2016-04-22: received
See all versions
Short URL
https://ia.cr/2016/401
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/401,
      author = {Palash Sarkar and Shashank Singh},
      title = {Tower Number Field Sieve Variant of a Recent Polynomial Selection Method},
      howpublished = {Cryptology ePrint Archive, Paper 2016/401},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/401}},
      url = {https://eprint.iacr.org/2016/401}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.