You are looking at a specific version 20160421:124116 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
sha2nk singh @ gmail com
History
2016-04-21: last of 4 revisions
2015-09-28: received
See all versions
Short URL
https://ia.cr/2015/944
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.