Cryptology ePrint Archive: Report 2014/641

The Multiple Number Field Sieve with Conjugation Method

CÚcile Pierrot

Abstract: In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields. We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

Category / Keywords: public-key cryptography / Discrete Logarithm. Finite Field. Medium Characteristic. NFS

Date: received 19 Aug 2014, last revised 20 Aug 2014

Contact author: Cecile Pierrot at lip6 fr

Available format(s): PDF | BibTeX Citation

Version: 20140827:072122 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]