**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 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.

**Category / Keywords: **

**Date: **received 28 Sep 2015, last revised 21 Apr 2016

**Contact author: **sha2nk singh at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20160421:124116 (All versions of this report)

**Short URL: **ia.cr/2015/944

[ Cryptology ePrint archive ]