On the selection of polynomials for the DLP algorithm
Giacomo Micheli · arXiv (Cornell University) · 2017
In this paper we characterize the set of polynomials $f\in\mathbb F_q[X]$ satisfying the following property: there exists a positive integer $d$ such that for any positive integer $\ell$ less or equal than the degree of $f$, there exists $t_0$ in $\mathbb F_{q^d}$ such that the polynomial $f-t_0$ has an irreducible factor of degree $\ell$ over $\mathbb F_{q^d}[X]$. This result is then used to progress in the last step which is needed to remove the heuristic from one of the quasi-polynomial time algorithms for discrete logarithm problems (DLP) in small characteristic. Our characterization allows a construction of polynomials satisfying the wanted property.