On the selection of polynomials for the DLP quasi-polynomial time algorithm in small characteristic

Abstract

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.

Accepted for publication in SIAM Journal on Applied Algebra and Geometry

References in corpus (2)

• On the discrete logarithm problem in finite fields of fixed characteristic
• A short proof of a Chebotarev density theorem for function fields