4
$\begingroup$

The recent papers:

  • R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math. Soc., 370(5) (2018), 3129–3145.
  • T. Kleinjung, B. Wesolowski, “Discrete Logarithms in Quasi-polynomial Time in Finite Fields of Fixed Characteristic," J. Amer. Math. Soc., 35(2) (2022), 581–624.

have established that the discrete logarithm problem can be solved in expected quasi-polynomial time, $e^{{\mathcal O}(\log^2 n)}$, in families of fields $GF(p^n)$ with fixed characteristic $p$. (More generally, the complexity is quasi-polynomial also in the case when $p$ grows polynomially with $n$, if I understood correctly.)

My question is the following: can this algorithm, or a modification thereof, be used for testing whether a given element $g$ is primitive? Namely, if we ask for the logarithm of $h=1$ with respect to base $g$, is it possible to modify the algorithm so that it returns the smallest positive integer $x$ satisfying $g^x=1$ (i.e., the order of $g$), instead of some integer $x$ that satisfies this relation? Together with a result of V. Shoup:

  • V. Shoup,"Searching for Primitive Roots in Finite Fields," Math. Comp., 58(197) (1992), 369–380.

this would give a quasi-polynomial time algorithm for finding primitive elements in these families of fields.

P.S. The mathematics in the two above-mentioned papers is beyond my familiarity with the subject, so I was hoping for a direct and simple answer.

Improve this question
$\endgroup$
3
  • $\begingroup$ Since $p^n-1$ is a multiple of $x$, finding $x$ is easy if we can factor $p^n-1$. $\endgroup$
    – Max Alekseyev
    Commented Apr 18, 2022 at 13:30
  • $\begingroup$ @MaxAlekseyev Sure, but we don't know how to do that efficiently as far as I know. $\endgroup$
    – aleph
    Commented Apr 18, 2022 at 13:52
  • $\begingroup$ These are instances of Cunningham numbers and at very least we have cyclotomic factorization. Also, proving that $g$ is not primitive in some cases can be done from an incomplete factorization (by noticing that $g^{(p^n-1)/q}=1$ for a known prime divisor $q$). $\endgroup$
    – Max Alekseyev
    Commented Apr 18, 2022 at 14:16

1 Answer 1

Reset to default
-1
$\begingroup$

Ming-Deh Huang and Anand Kumar Narayanan, Finding primitive elements in finite fields of small characteristic, https://arxiv.org/pdf/1304.1206v4.pdf

From the abstract:

We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field with $p^n$ elements. In time polynomial in $p$ and $n,$ the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. [...] The algorithm relies on a relation generation technique in a recent breakthrough for discrete logarithm computation in small characteristic finite fields.

Followup work includes (included since it was peer reviewed) a paper co-authored by one of the authors above "Generating sets for the multiplicative groups of algebras over finite fields and expander graphs" in the Journal of Symbolic Computation available here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .