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

The selection of polynomials to represent number fields crucially determines the efficiency of the Number Field Sieve (NFS) algorithm for solving the discrete logarithm 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 is a non-prime field. These methods are called the generalised Joux-Lercier (GJL) and the Conjugation methods. In this work, we propose a new method (which we denote as \(\mathcal {A}\)) 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 and provides new trade-offs for both n composite and n prime. Let us denote the variant of the (multiple) NFS algorithm using the polynomial selection method “X” by (M)NFS-X. Asymptotic analysis is performed for both the NFS-\(\mathcal {A}\) and the MNFS-\(\mathcal {A}\) algorithms. In particular, when \(p=L_Q(2/3,c_p)\), for \(c_p\in [3.39,20.91]\), the complexity of NFS-\(\mathcal {A}\) is better than the complexities of all previous algorithms whether classical or MNFS. The MNFS-\(\mathcal {A}\) algorithm provides lower complexity compared to NFS-\(\mathcal {A}\) algorithm; for \(c_p\in (0, 1.12] \cup [1.45,3.15]\), the complexity of MNFS-\(\mathcal {A}\) is the same as that of the MNFS-Conjugation and for \(c_p\notin (0, 1.12] \cup [1.45,3.15]\), the complexity of MNFS-\(\mathcal {A}\) is lower than that of all previous methods.