International Association
for Cryptologic Research

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}_{p^n}$, with $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, for $p=L_Q(2/3,c_p)$, as $c_p$ grows the complexity of the new method is lower than that of the GJL method and hence becomes the new state of the art.