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

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 begin{document}$ mathcal{D} $end{document} . Starting from the Barbulescu et al. paper, all the subsequent polynomial selection methods can be seen as special cases of Algorithm begin{document}$ mathcal{D} $end{document} . 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 begin{document}$ mathcal{D} $end{document} provides the best asymptotic complexity. Suppose begin{document}$ Q = p^n $end{document} for a prime begin{document}$ p $end{document} and further suppose that begin{document}$ n = etakappa $end{document} such that there is a begin{document}$ c_{theta}u003e0 $end{document} for which begin{document}$ p^{eta} = L_Q(2/3, c_{theta}) $end{document} . For begin{document}$ c_{theta}u003e3.39 $end{document} , the complexity of exTNFS- begin{document}$ mathcal{D} $end{document} is lower than the complexities of all previous algorithms; for begin{document}$ c_{theta}notin (0, 1.12)cup[1.45, 3.15] $end{document} , the complexity of MexTNFS- begin{document}$ mathcal{D} $end{document} is lower than that of all previous methods.