Cryptology ePrint Archive: Report 2015/944

New Complexity Trade-Offs for the (Multiple) Number Field Sieve Algorithm in Non-Prime Fields

Palash Sarkar and Shashank Singh

Abstract: The selection of polynomials to represent number fields crucially determines the efficiency of the Number Field Sieve (NFS) algorithm for solving the discrete log problem in a finite field. An important recent work due to Barbulescu et al builds upon existing works to propose two new methods for polynomial selection when the target field has a composite order. These methods are called the generalised Joux-Lercier (GJL) and the Conjugation methods. In this work, we propose a new method for polynomial selection for the NFS algorithm in fields $\mathbb{F}_{Q}$, with $Q=p^n$ and $n>1$. The new method both subsumes and generalises the GJL and the Conjugation methods. Asymptotic analysis for the new polynomial selection method is performed for both the classical NFS and the multiple NFS (MNFS) algorithms. %For medium and large prime characteristic, the new method does not provide any new asymptotic result. For the boundary case, the complexity of the new method interpolates between that of the Conjugation and the GJL methods for both classical and multiple NFS algorithms. In particular, when $p=L_Q(2/3,c_p)$, for $c_p\in [3.39,20.91]$, the complexity of NFS-New is better than the complexities of all previous algorithms whether classical or MNFS. The MNFS-New algorithm provides lower complexity compared to NFS-New algorithm; for $c_p\in (0, 1.12] \cup [1.45,3.15]$, the complexity of MNFS-New is the same as that of the MNFS variant of the Conjugation method and for $c_p\notin (0, 1.12] \cup [1.45,3.15]$, the complexity of the new method is lower than that of all previous methods and hence becomes the current state-of-the-art.

Category / Keywords:

Date: received 28 Sep 2015, last revised 5 Oct 2015

Contact author: sha2nk singh at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151005:065324 (All versions of this report)

Short URL: ia.cr/2015/944

Discussion forum: Show discussion | Start new discussion