Logarithmic universality bounds for polynomial field representations in small-characteristic discrete logarithm algorithms (Micheli's Conjectures 1.1 and 1.2)

The quasi-polynomial-time algorithms for the discrete logarithm problem in finite fields of small characteristic rest on a field-representation heuristic: one must find coprime polynomials $h_{1},h_{2}$ of degree at most 2 over an extension $\mathbb{F}_{q^{d}}$ such that $h_{1}X^{q}+h_{2}$, and its shifts $h_{1}X^{q}+h_{2}-t_{0}$, acquire irreducible factors of every prescribed degree, with the extension degree bounded by $d=O(\log q)$. Micheli (2019) characterized the polynomials with the underlying property — called $d$-universality — group-theoretically: for degree at least 8, they are exactly the polynomials whose arithmetic and geometric monodromy groups both equal the full symmetric group, and he proved that the explicit families $X^{q}+X^{2}$ (odd $q$) and $X^{q+j}-jX$ are universal, i.e. $d$-universal for all sufficiently large $d$. What is missing, and what this problem asks for, is the quantitative side: prove Micheli's Conjectures 1.1 and 1.2, in particular that at least one explicitly constructed family is $d$-universal with $d=O(\log q)$, determine the minimal such $d$ for concrete candidates, and obtain effective uniform bounds on the least degree $d_{0}$ after which a universal polynomial stays universal. These questions remain open: the motivating goal of removing the last heuristic from quasi-polynomial DLP algorithms has since been achieved by Kleinjung–Wesolowski and by Lido via elliptic-curve-based field representations that bypass polynomial selection entirely, while the polynomial-model conjectures themselves are explicitly recorded as unproved in the most recent treatments (2022–2026).

Background

The discrete logarithm problem (DLP) in a finite field $\mathbb{F}_{Q}$ asks, given a generator $g$ of a subgroup of the multiplicative group $\mathbb{F}_{Q}^{\times}$ and an element $h$, for an integer $z$ with $g^{z}=h$. Since 2013–2014, fields of small characteristic — fields $\mathbb{F}_{p^{n}}$ whose characteristic $p$ is small compared with the field size, a regime relevant to pairing-based cryptography — have been subject to index-calculus attacks of unprecedented efficiency. Index calculus solves DLP by finding multiplicative relations among elements of a small generating set (the factor base) and then expressing the target through them; its cost is governed by how easily such relations are produced. The culminating heuristic algorithm of Barbulescu–Gaudry–Joux–Thomé (BGJT) runs in heuristic quasi-polynomial time, i.e. expected time $(\log Q)^{O(\log\log Q)}$, improving on the subexponential $L_{Q}(1/2)$ of earlier methods.

The key device of these algorithms is a special representation of the field. One seeks a prime power $q$, an integer $d$, and coprime polynomials $h_{0},h_{1}\in\mathbb{F}_{q^{d}}[X]$ of degree at most 2 such that $h_{1}X^{q}-h_{0}$ has an irreducible factor $I$ of degree $\ell$; then $\mathbb{F}_{q^{d\ell}}\cong\mathbb{F}_{q^{d}}[X]/(I)$ and, writing $x$ for the class of $X$, the Frobenius map (the field automorphism $u\mapsto u^{q}$) acts on the generator as $x^{q}\equiv h_{0}(x)/h_{1}(x)$, a rational function of tiny degree. Iterating this relation makes factor-base relations abundant and drives the quasi-polynomial descent. What is not proved — the field-representation heuristic, the only remaining heuristic of the BGJT algorithm — is that such $h_{0},h_{1}$ exist for every required extension degree $\ell$ with $d=O(\log q)$, which is what keeps all parameters small enough for the complexity to stay quasi-polynomial. Granger–Kleinjung–Zumbrägel made one fixed-characteristic algorithm conditionally rigorous: given a suitable model, its quasi-polynomial expected time follows rigorously (the descent step being justified by Bluher's exact count of the coefficients for which $x^{q+1}+ax+b$ has the required splitting), leaving precisely the model-existence question open.

Micheli recast the model-existence question as a factorization-pattern problem for a single polynomial. A polynomial $f\in\mathbb{F}_{q}[X]$ is $d$-universal if for every $1\le\ell\le\deg f$ there exists $t_{0}\in\mathbb{F}_{q^{d}}$ such that $f(X)-t_{0}$ has an irreducible factor of degree $\ell$ over $\mathbb{F}_{q^{d}}$; $f$ is universal if it is $d$-universal for some $d$. The relevant $f$ are the polynomials $h_{1}X^{q}+h_{2}$ with $\deg h_{i}\le 2$ (so $\deg f\approx q$), whose shifts must realize every factor degree up to about $q$. Micheli proved a complete characterization for $\deg f\ge 8$: $f$ is universal if and only if its arithmetic and geometric monodromy groups coincide and equal the full symmetric group $S_{n}$, $n=\deg f$ — these monodromy groups are the Galois groups of $f(X)-t$ over $\mathbb{F}_{q}(t)$ and over its constant-field extension, i.e. the symmetry groups of the generic fiber of $f$. Using Turnwald's classical criterion for full symmetric monodromy, he showed that $X^{q}+X^{2}$ (odd $q$) and $X^{q+j}-jX$ (odd $q$, $j\notin\{0,1\}\cup\{p^{k}\}$) have monodromy $S_{\deg f}$, hence are universal; and via the Chebotarev density theorem for global function fields — which equidistributes the Frobenius conjugacy classes of degree-one places in a finite Galois extension of function fields — universality then propagates to all sufficiently large $d$. The flaw is quantitative: the Chebotarev error term involves the genus of the splitting field (on the order of $q^{2}$ for $X^{q}+X^{2}$), and the density of the conjugacy classes that produce a degree-$\ell$ factor is about $1/(\ell(n-\ell)!)$ for middle-range $\ell$, so the threshold $d_{0}$ obtained this way is neither explicit nor close to $O(\log q)$. Experiments point the other way: BGJT suggested that $X^{q}+X^{2}$ is in fact 2-universal for every odd $q$, and Micheli reports that $X^{q+2}-2X$ is 3-universal for every prime $q<401$.

The original motivation has since been partly overtaken. Kleinjung–Wesolowski proved that DLP in fixed characteristic is solvable in expected quasi-polynomial time $(pn)^{2\log_{2}n+O(1)}$, and Lido proved an expected quasi-polynomial bound $(\log\#K)^{O(\log\log\#K)}$ for all small-characteristic fields — both by replacing the polynomial model with representations built from elliptic curves, using the abundance of pairwise non-isogenous curves to provably find a presentation in which Frobenius acts by low-degree maps. Both works explicitly record that proving existence of the polynomial-based model has so far failed, and practical record computations still use the polynomial ("linear" or "quadratic") presentations, with elliptic presentations currently somewhat slower in practice (Joux–Pierrot). Micheli's conjectures therefore survive as a well-posed quantitative question about the original polynomial route, with independent arithmetic content.

Problem Statement

Prove the two conjectures stated by Micheli (numbered 1.1 and 1.2 in the journal version, 1 and 2 in the arXiv version), or the central weaker special case, and supply the effective bounds the paper lacks. The common scientific objective is an effective, logarithmic instantiation of the polynomial field representation; all requested results below serve that single objective.

Conjecture 1.1, Conjecture 1.2, and the central special case are alternative sufficient forms of this objective, each sought together with the effective bound of target (b); within the central special case the two finer targets (a) and (b) are jointly required, and the logarithmic-degree universality of a single explicit family (target (a)) does not by itself supply the effective bound of target (b).

Conjecture 1.1. For any finite field $\mathbb{F}_{q}$ and any fixed positive integer $\ell\le q+2$, there exist an integer $d=O(\log q)$ and coprime $h_{1},h_{2}\in\mathbb{F}_{q^{d}}[X]$, both of degree at most 2, such that $h_{1}X^{q}+h_{2}$ has an irreducible factor of degree $\ell$ over $\mathbb{F}_{q^{d}}$.

Conjecture 1.2 (stronger form, odd characteristic). Let $\mathbb{F}_{q}$ be a finite field of odd characteristic. There exist an integer $d=O(\log q)$ and coprime $h_{1},h_{2}\in\mathbb{F}_{q^{d}}[X]$, both of degree at most 2, such that for every positive integer $\ell\le\deg(h_{1})+q$ there is a $t_{0}\in\mathbb{F}_{q^{d}}$ for which $h_{1}X^{q}+h_{2}-t_{0}$ has an irreducible factor of degree $\ell$ over $\mathbb{F}_{q^{d}}$.

Central special case. Show that at least one explicitly constructed polynomial family $f$ is $d$-universal (i.e. for every $1\le\ell\le\deg f$ there exists $t_{0}\in\mathbb{F}_{q^{d}}$ such that $f(X)-t_{0}$ has an irreducible factor of degree $\ell$ over $\mathbb{F}_{q^{d}}$) with $d=O(\log q)$ for an explicit absolute constant. This comprises two finer targets: (a) a proof that $X^{q}+X^{2}$ is 2-universal for all odd $q$ — i.e. for every $1\le\ell\le q=\deg(X^{q}+X^{2})$ there exists $t_{0}\in\mathbb{F}_{q^{2}}$ such that $X^{q}+X^{2}-t_{0}$ has an irreducible factor of degree $\ell$ over $\mathbb{F}_{q^{2}}$ — or a determination of the true minimal such $d$ (conjecturally $2$; likewise $j+1$ for $X^{q+j}-jX$); and (b) an effective uniform bound: an explicit function of $q$ and $\deg f$ for the least $d_{0}$ such that a universal polynomial $f$ is $d$-universal for every $d>d_{0}$, replacing the currently available purely existential statement.

References

1. Giacomo Micheli, "On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic", SIAM Journal on Applied Algebra and Geometry 3(2):256–265, 2019. DOI: 10.1137/18M1177196, https://doi.org/10.1137/18M1177196 (author version: arXiv:1706.08447, https://arxiv.org/abs/1706.08447)
2. Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé, "A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic", Advances in Cryptology – EUROCRYPT 2014, Lecture Notes in Computer Science, pp. 1–16, 2014. DOI: 10.1007/978-3-642-55220-5_1, https://doi.org/10.1007/978-3-642-55220-5_1
3. Robert Granger, Thorsten Kleinjung, Jens Zumbrägel, "On the discrete logarithm problem in finite fields of fixed characteristic", Transactions of the American Mathematical Society 370(5):3129–3145, 2018. DOI: 10.1090/tran/7027, https://doi.org/10.1090/tran/7027
4. Thorsten Kleinjung, Benjamin Wesolowski, "Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic", Journal of the American Mathematical Society 35(2):581–624, 2022. DOI: 10.1090/jams/985, https://doi.org/10.1090/jams/985 (arXiv:1906.10668, https://arxiv.org/abs/1906.10668)
5. Guido Lido, "A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic", Finite Fields and Their Applications 111:102753, 2026. DOI: 10.1016/j.ffa.2025.102753, https://doi.org/10.1016/j.ffa.2025.102753 (arXiv:2206.10327, https://arxiv.org/abs/2206.10327)
6. Antoine Joux, Cécile Pierrot, "Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms", Advances in Mathematics of Communications 18(5):1266–1302, 2024. DOI: 10.3934/amc.2022085, https://doi.org/10.3934/amc.2022085 (arXiv:1907.02689, https://arxiv.org/abs/1907.02689)
7. Antonia W. Bluher, "On $x^{q+1}+ax+b$", Finite Fields and Their Applications 10(3):285–305, 2004. DOI: 10.1016/j.ffa.2003.08.004, https://doi.org/10.1016/j.ffa.2003.08.004
8. Gerhard Turnwald, "On Schur's conjecture", Journal of the Australian Mathematical Society, Series A 58(3):312–357, 1995. DOI: 10.1017/S1446788700038349, https://doi.org/10.1017/S1446788700038349
9. Marie Euler, Christophe Petit, "New results on quasi-subfield polynomials", Finite Fields and Their Applications 75:101881, 2021. DOI: 10.1016/j.ffa.2021.101881, https://doi.org/10.1016/j.ffa.2021.101881 (preprint: arXiv:1909.11326, https://arxiv.org/abs/1909.11326)