• PDF
• Cite
• Share
Article Contents  Article Contents

# A unified polynomial selection method for the (tower) number field sieve algorithm

• * Corresponding author: Shashank Singh
• At Eurocrypt 2015, Barbulescu et al. introduced two new methods of polynomial selection, namely the Conjugation and the Generalised Joux-Lercier methods, for the number field sieve (NFS) algorithm as applied to the discrete logarithm problem over finite fields. A sequence of subsequent works have developed and applied these methods to the multiple and the (extended) tower number field sieve algorithms. This line of work has led to new asymptotic complexities for various cases of the discrete logarithm problem over finite fields. The current work presents a unified polynomial selection method which we call Algorithm $\mathcal{D}$. Starting from the Barbulescu et al. paper, all the subsequent polynomial selection methods can be seen as special cases of Algorithm $\mathcal{D}$. Moreover, for the extended tower number field sieve (exTNFS) and the multiple extended TNFS (MexTNFS), there are finite fields for which using the polynomials selected by Algorithm $\mathcal{D}$ provides the best asymptotic complexity. Suppose $Q = p^n$ for a prime $p$ and further suppose that $n = \eta\kappa$ such that there is a $c_{\theta}>0$ for which $p^{\eta} = L_Q(2/3, c_{\theta})$. For $c_{\theta}>3.39$, the complexity of exTNFS-$\mathcal{D}$ is lower than the complexities of all previous algorithms; for $c_{\theta}\notin (0, 1.12)\cup[1.45, 3.15]$, the complexity of MexTNFS-$\mathcal{D}$ is lower than that of all previous methods.

Mathematics Subject Classification: Primary: 11Y16; Secondary: 94A60.

 Citation: • • Figure 1.  Tower of Number Fields

Figure 2.  Commutative diagram for TNFS

Figure 3.  Product of norms for various polynomial selection methods

Figure 4.  Complexity plot for medium characteristic finite fields

Figure 5.  Complexity plot for medium characteristic finite fields

Table 1.  Parameterised efficiency estimates for NFS obtained from the different polynomial selection methods

 Method Norms Product Conditions NFS-JLSV1 $E^{\frac{4n}{t}}Q^{\frac{t-1}{n}}$ NFS-GJL $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $r\geq n$ NFS-Conj $E^{\frac{6n}{t}}Q^{\frac{t-1}{2n}}$ NFS-$\mathcal{A}$ $E^{\frac{2d(2r+1)}{t}}Q^{\frac{t-1}{d(r+1)}}$ $d|n$, $r\geq n/d$ exTNFS-JLSV1 $E^{\frac{4\kappa}{t}}Q^{\frac{t-1}{\kappa}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$ exTNFS-GJL $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$, $r\geq\kappa$ exTNFS-$\mathcal{C}$ $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)(r(\lambda-1)+k)}{\kappa(r\lambda+1)}}$ $n=\eta\kappa$, $k=\kappa/d$, $r\geq k$, $\lambda\in\{1, \eta\}$ exTNFS-gConj  $E^{\frac{6\kappa}{t}}Q^{\frac{t-1}{2\kappa}}$ $n=\eta\kappa$ exTNFS-$\mathcal{D}$ $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)}{d(r+1)}}$ $n=\eta\kappa$, $d|\kappa$, $\gcd(\eta, \kappa/d)=1$, $r\geq \kappa/d$ NFS-GJL:$\eta=d=1$NFS-Conj:$\eta=1$, $d=\kappa=n$, $r=1$NFS-$\mathcal{A}$:$\eta=1$, $\kappa=n$, $d|n$, $r\geq n/d$exTNFS-GJL:$d=1$exTNFS-gConj:$d=\kappa$, $r=1$
• Figures(5)

Tables(1)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint