Existence of degree-two polynomial models for the quasi-polynomial discrete logarithm algorithm in finite fields of fixed characteristic

Granger–Kleinjung–Zumbrägel (Trans. Amer. Math. Soc. 2018) proved that the discrete logarithm problem (DLP) in a finite field $\mathbb{F}_{q^{kl}}$ is solvable in expected quasi-polynomial time whenever the field admits a degree-two model: coprime polynomials $h_0,h_1\in\mathbb{F}_{q^k}[X]$ of degree at most two such that $h_1X^q-h_0$ has an irreducible factor of degree $l$, in which case the Frobenius map becomes the low-degree rational function $h_0/h_1$. Such models provably exist for infinitely many extension degrees of every fixed prime $p$ (the Kummer case), but the authors stated that proving existence for the parameters needed to cover every extension degree $n$ appears to be a very hard problem, although heuristically almost certain. Micheli (2019) reduced the question to a clean conjecture on irreducible factors of $h_1X^q+h_2$ over coefficient fields of logarithmic degree and proved a relaxed version without the logarithmic bound; Kleinjung–Wesolowski (J. Amer. Math. Soc. 2022) achieved the motivating unconditional quasi-polynomial complexity for all fixed-characteristic fields by substituting provably existing elliptic-curve models, explicitly leaving the degree-two model question open, as does Lido (2026) for small characteristic. Whether, for every prime $p$ and every $n$, there exist $q=p^i$ in the window $n-2\le q\le n^{1+o(1)}$, an integer $k=o(\log q)$ (asymptotics as $n\to\infty$ with $p$ fixed), and coprime quadratic $h_0,h_1$ over $\mathbb{F}_{q^k}$ such that $h_1X^q-h_0$ has an irreducible factor of degree $n$ remains open.

Background

For a prime power $Q$, the discrete logarithm problem (DLP) in the multiplicative group $\mathbb{F}_{Q}^{\times}$ asks, given $g$ and $h$ in the cyclic subgroup generated by $g$, for an integer $x$ with $g^{x}=h$; its difficulty underpins many cryptographic protocols. In fields of fixed characteristic, $Q=p^{n}$ with $p$ fixed and $n$ growing, index-calculus methods — which generate multiplicative relations among elements of a small factor base and solve a linear system — are dramatically more efficient than in large-characteristic fields. After a series of record computations, Barbulescu–Gaudry–Joux–Thomé (EUROCRYPT 2014) gave a heuristic algorithm of quasi-polynomial complexity, meaning expected time $\exp(O((\log n)^{2}))$.

The engine of these algorithms is a compact description of the Frobenius automorphism, the map $x\mapsto x^{q}$ on an extension of $\mathbb{F}_{q}$. Suppose the field $\mathbb{F}_{q^{kl}}$ is represented as $\mathbb{F}_{q^{k}}[X]/(I)$, where $I$ is an irreducible factor of degree $l$ of $h_{1}X^{q}-h_{0}$ for coprime polynomials $h_{0},h_{1}\in\mathbb{F}_{q^{k}}[X]$ of degree at most two. Then in the quotient ring one has $X^{q}\equiv h_{0}(X)/h_{1}(X)$, so raising to the $q$-th power — normally a large field operation — becomes evaluation of a rational function of degree at most two. This makes relation generation extremely fast and supports a recursive descent from arbitrary elements down to the factor base. Granger–Kleinjung–Zumbrägel (Trans. Amer. Math. Soc. 370 (2018) 3129–3145) proved rigorously, without smoothness heuristics, that whenever such a representation exists with $q>61$ not a power of 4 and $k\ge 18$, the DLP in $\mathbb{F}_{q^{kl}}\cong\mathbb{F}_{q^{k}}[X]/(I)$ is solvable in expected time $q^{\log_{2}l+O(k)}$, which is quasi-polynomial when $q$ is polynomially bounded and $k=O(\log q)$. By Kummer theory the required polynomials provably exist in the special case $l=q-1$ (there is an $a\in\mathbb{F}_{q^{k}}$ with $I=X^{q-1}-a$ irreducible, and $I$ divides $X^{q}-aX$), which yields infinitely many explicit extension degrees $n$ per prime $p$ — but not all $n$.

To cover an arbitrary extension degree $n$ with fixed $p$, one would embed the DLP of $\mathbb{F}_{p^{n}}$ into a field $\mathbb{F}_{q^{kn}}$ with $q=p^{i}$ satisfying $n-2\le q$ and $q$ not too large, and $k=o(\log q)$. The condition $q\ge n-2$ is forced: $h_{1}X^{q}-h_{0}$ has degree at most $q+2$, so it cannot have an irreducible factor of degree $n$ when $q<n-2$; taking $i$ minimal with $q\ge n-2$ automatically gives $q\le p(n-2)$, so the real content of the question is whether, with the coefficient extension degree restricted to $k=o(\log q)$, suitable $h_{0},h_{1}$ exist at all. The authors state that proving this appears to be a very hard problem, even though heuristically it would seem almost certain, and computations support it. The delicacy is genuine: Cheng–Wan–Zhuang (LMS J. Comput. Math. 17 (2014) 218–229) showed that several heuristics underlying the original Barbulescu–Gaudry–Joux–Thomé algorithm are problematic precisely in non-Kummer cases. Micheli (SIAM J. Appl. Algebra Geom. 3 (2019) 256–265) isolated the clean form of the question (his Conjecture 1): for any finite field $\mathbb{F}_{q}$ and any $\ell\le q+2$ there should exist $d=O(\log q)$ and coprime degree-≤2 $h_{1},h_{2}\in\mathbb{F}_{q^{d}}[X]$ such that $h_{1}X^{q}+h_{2}$ has an irreducible factor of degree $\ell$; he proved a relaxed version in which the extension degree $d$ exists and the polynomials are explicit, but no logarithmic bound on $d$ is obtained.

Meanwhile the motivating complexity target has been reached by other means. Kleinjung–Wesolowski (J. Amer. Math. Soc. 35 (2022) 581–624) introduced elliptic curve models, in which Frobenius is congruent modulo a divisor to translation by a rational point on an ordinary elliptic curve; such models provably exist up to a logarithmic extension by classical results on elliptic curves with prescribed point counts, and they prove that the DLP in $\mathbb{F}_{p^{n}}^{\times}$ is solvable in expected time $(pn)^{2\log_{2}n+O(1)}$, unconditionally. Lido (Finite Fields Appl. 111 (2026) 102753) obtained the analogous unconditional quasi-polynomial algorithm for small characteristic (characteristic logarithmic in the field order) using elliptic presentations. Both works bypass — and explicitly decline to answer — the question of whether the original degree-two model itself always exists.

Problem Statement

Fix a prime $p$ and an integer $n\ge 1$; all asymptotic ($O$, $o$) notation below is understood as $n\to\infty$ with $p$ fixed. Does there exist a choice of $q=p^{i}$ with $q>61$, $q$ not a power of 4, and $n-2\le q\le n^{1+o(1)}$ (one requires $q$ 'at least $n-2$ but not too large'; the upper bound ensures that the running time $q^{\log_{2}n+O(k)}$ of the Granger–Kleinjung–Zumbrägel theorem matches the target bound $\exp((1/\log 2+o(1))(\log n)^{2})$; taking $i$ minimal already gives $q\le p(n-2)$, which satisfies it), together with an integer $k$ satisfying $18\le k=o(\log q)$ and coprime polynomials $h_{0},h_{1}\in\mathbb{F}_{q^{k}}[X]$, each of degree at most two, such that $h_{1}X^{q}-h_{0}$ has an irreducible factor of degree $n$ over $\mathbb{F}_{q^{k}}$ — so that $\mathbb{F}_{p^{n}}$ embeds into $\mathbb{F}_{q^{kn}}\cong\mathbb{F}_{q^{k}}[X]/(I)$ and the Granger–Kleinjung–Zumbrägel theorem applies? Prove this for all primes $p$ and all $n$, or refute it by exhibiting a prime $p$ and extension degree $n$ for which no admissible choice of $(i,k,h_{0},h_{1})$ exists. A related statement is Micheli's Conjecture 1 in the literature: for every prime power $q$ and every integer $\ell$ with $1\le \ell\le q+2$ there exist $d=O(\log q)$ and coprime $h_{1},h_{2}\in\mathbb{F}_{q^{d}}[X]$ of degree at most two such that $h_{1}X^{q}+h_{2}$ has an irreducible factor of degree $\ell$. Because Conjecture 1 guarantees only $d=O(\log q)$ for the coefficient field, whereas the present problem requires the strictly sharper bound $k=o(\log q)$, applying that statement with $q=p^{i}$ in the window above and $\ell=n$ does not by itself yield the requested instance, and the present problem is accordingly a strengthening of Conjecture 1 in the coefficient-field degree. In the other direction, a proof of the present problem would not settle Conjecture 1: the conjecture prescribes $q$ (hence the Frobenius exponent $X^{q}$) for every prime power $q$, whereas the present problem existentially chooses $q=p^{i}$, so a proof here would establish the conjecture only for the chosen values of $q$. Note that the complexity-theoretic consequence once attached to this question — an unconditional quasi-polynomial-time algorithm for the DLP in all $\mathbb{F}_{p^{n}}$ — is already known by the elliptic-curve route of Kleinjung–Wesolowski, so the problem asks specifically whether the original degree-two Frobenius model always exists.

References

1. 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 (2018), no. 5, 3129–3145. DOI: 10.1090/tran/7027, https://doi.org/10.1090/tran/7027 (arXiv:1507.01495, https://arxiv.org/abs/1507.01495)
2. Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé, "A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic", in Advances in Cryptology – EUROCRYPT 2014, Lecture Notes in Computer Science 8441, Springer, 2014, pp. 1–16. DOI: 10.1007/978-3-642-55220-5_1, https://doi.org/10.1007/978-3-642-55220-5_1
3. 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 (2019), no. 2, 256–265. DOI: 10.1137/18M1177196, https://doi.org/10.1137/18M1177196 (arXiv:1706.08447, https://arxiv.org/abs/1706.08447)
4. Thorsten Kleinjung, Benjamin Wesolowski, "Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic", Journal of the American Mathematical Society 35 (2022), no. 2, 581–624. 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 (2026), 102753. 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. Qi Cheng, Daqing Wan, Jincheng Zhuang, "Traps to the BGJT-algorithm for discrete logarithms", LMS Journal of Computation and Mathematics 17 (2014), 218–229. DOI: 10.1112/s1461157014000242, https://doi.org/10.1112/s1461157014000242