Cryptology ePrint Archive: Report 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.

Category / Keywords:

Date: received 22 Apr 2016, last revised 26 Apr 2016

Contact author: sha2nk singh at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160426:101810 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]