On the selection of polynomials for the DLP quasi-polynomial time algorithm in small characteristic
This addresses a theoretical bottleneck in cryptography for improving the efficiency of solving discrete logarithm problems in small characteristic fields, though it is incremental as it focuses on a specific step.
The paper characterizes polynomials over finite fields that have irreducible factors of all degrees up to their own degree, and uses this to advance in removing heuristics from a quasi-polynomial time algorithm for discrete logarithm problems in small characteristic.
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. The method is general and can be used to tackle similar problems which involve factorization patterns of polynomials over finite fields.