The stronger polynomial selection conjecture for small-characteristic DLP

Let Fq\mathbb F_q be a finite field of odd characteristic. The polynomials h1,h2Fqd[X]h_1,h_2\in\mathbb F_{q^d}[X] are required to be coprime and have degree at most 22. Stronger polynomial selection conjecture. There exists an integer d=O(log(q))d=O(\log(q)) and such polynomials h1,h2h_1,h_2 such that, for every positive integer deg(h1)+q\ell\leq\deg(h_1)+q, there is an element t0Fqdt_0\in\mathbb F_{q^d} for which h1Xq+h2t0h_1X^q+h_2-t_0 has an irreducible factor of degree \ell. This stronger requirement is motivated by the use of polynomials of the form h1=1h_1=1 and h2=X2t0h_2=X^2-t_0 in the discrete logarithm algorithm; its proof would support a non-heuristic quasi-polynomial-time algorithm in small characteristic.

Sources & referencesView supporting material

Primary source

Giacomo Micheli, “On the selection of polynomials for the DLP quasi-polynomial time algorithm in small characteristic”, arXiv:1706.08447 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.