Finding Primitive Elements in Finite Fields of Small Characteristic

2013/04/03 by Ming-Deh A. Huang, Anand Kumar Narayanan, Huang, Ming-Deh +1
Computer Science · #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1304.1206

openalex publication_date 2013/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field \mathbbF_pⁿ where p is a prime. 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 Joux's heuristically L(1/4)-method for discrete logarithm computation. Based on a heuristic assumption, the algorithm does succeed in finding a generator. For the special case when the order of p in (ℤ/nℤ)^× is small (that is (log_p(n))^O(1)), we present a modification with greater guarantee of success while making weaker heuristic assumptions.

Related

• On the relation generation method of Joux for computing discrete logarithms
• A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
• A Short Note on Discrete Log Problem in F_p
• On the minimal number of small elements generating prime field
• Discrete logarithms in quasi-polynomial time in finite fields of fixed\n characteristic