Tower Number Field Sieve Variant of a Recent Polynomial Selection Method

Palash Sarkar; Shashank Singh

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: 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},
      url = {https://eprint.iacr.org/2016/401}
}