IACR News item: 22 April 2016
Palash Sarkar, Shashank Singh
ePrint Report
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.
Additional news items may be found on the IACR news page.