Welcome to the resource topic for 2015/944
Title:
New Complexity Trade-Offs for the (Multiple) Number Field Sieve Algorithm in Non-Prime Fields
Authors: Palash Sarkar, 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.
ePrint: https://eprint.iacr.org/2015/944
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .