On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic

Abstract

In this paper we characterize the polynomials $f$ over a finite field $F$ satisfying the following property: there exists an extension field $L$ of $F$ such that for any positive integer $\ell$ less than or equal to the degree of $f$, there exists $t_0$ in $L$ with the property that the polynomial $f-t_0$ has an irreducible factor in $L[x]$ of degree $\ell$. This result is then used to progress to the last step which is needed to remove the heuristic from one of the quasi-polynomial time algorithms for discrete logarithm problems (DLPs) in small characteristic. Our method is general and can be used to tackle similar problems which involve factorization patterns of polynomials over finite fields.