Searching for Primitive Roots in Finite Fields

DOI10.2307/2153041zbMath0747.11060OpenAlexW4236247848WikidataQ56139168 ScholiaQ56139168MaRDI QIDQ3987942

Victor Shoup

Publication date: 28 June 1992

Full work available at URL: https://doi.org/10.2307/2153041

zbMATH Keywords

finite fieldprimitive rootleast primitive rootmultiplicative group of unitsdeterministic polynomial-time search procedureExtended Riemann Hypothesistheorem of Wang

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Algebraic number theory computations (11Y40)

Related Items

Local Reductions, Deterministic root finding over finite fields using Graeffe transforms, On the least square-free primitive root modulo \(p\), Local reduction, On some approximation problems concerning sparse polynomials over finite fields, On finding primitive roots in finite fields, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), Factor base discrete logarithms in Kummer extensions, An elliptic curve analogue of Pillai’s lower bound on primitive roots, Generating sets for the multiplicative groups of algebras over finite fields and expander graphs, Univariate polynomial factorization over finite fields, Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets, Computing sparse multiples of polynomials, Abelian lifts of polynomials, On the least primitive root in number fields, Factorization, malleability and equivalent problems, Efficient Finite Fields in the Maxima Computer Algebra System, ON THE MINIMAL NUMBER OF SMALL ELEMENTS GENERATING FINITE PRIME FIELDS, Generators and irreducible polynomials over finite fields, Cryptographic hash functions from sequences of lifted Paley graphs, Constructing nonresidues in finite fields and the extended Riemann hypothesis, Distinguishing eigenforms modulo a prime ideal, On primitive elements in finite fields of low characteristic, Square-full primitive roots, Comments on search procedures for primitive roots, Resolving Grosswald's conjecture on GRH, Counting curves and their projections, Explicit Burgess bound for composite moduli, Elements of high order in Artin-Schreier extensions of finite fields \(\mathbb{F}_q\), Special prime numbers and discrete logs in finite prime fields, Primitive Normal Polynomials Over Finite Fields, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, On the Average Distribution of Power Residues and Primitive Elements in Inversive and Nonlinear Recurring Sequences, Fast multivariate multi-point evaluation revisited, Discrete logarithm problems with auxiliary inputs, Using number fields to compute logarithms in finite fields, On the least prime primitive root, Explicit bounds for primes in residue classes, Uniform bounds for the least almost‐prime primitive root, Distributional properties of powers of matrices, On the construction of finite field elements of large order, Factorization properties of Chebyshev polynomials, Elements of large order on varieties over prime finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factorization of solvable polynomials over finite fields and the generalized Riemann hypothesis
• Factoring polynomials modulo special primes
• On the deterministic complexity of factoring polynomials over finite fields
• Factoring polynomials and primitive elements for special primes
• Smoothness and factoring polynomials over finite fields
• A bound for the least prime ideal in the Chebotarev density theorem
• Character sums and primitive roots in algebraic number fields
• Topics in multiplicative number theory
• Character sums and primitive roots in finite fields
• The least quadratic non residue
• Finding Isomorphisms Between Finite Fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Factoring polynomials over finite fields
• ON THE PROBLEM OF JACOBSTHAL
• Character Sums and Primitive Roots in Finite Fields
• On the error term in the linear sieve
• A note on primitive roots in finite fields
• ON PRIMITIVE ROOTS IN FINITE FIELDS
• DISTRIBUTION OF PRIMITIVE ROOTS IN A FINITE FIELD