Constructing normal bases in finite fields
type: Item
instance of: scholarly article
title: Constructing normal bases in finite fields
zbMATH Open document ID: 0718.11065
DOI: 10.1016/S0747-7171(08)80158-7
author: Joachim von zur Gathen
author: Mark Giesbrecht
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
review text: Let GF(q) denote the Galois field with q elements, and let \(GF(q^ n)\) denote an extension field of dimension n. If \(\alpha\) is an element of \(GF(q^ n)\) such that the conjugates \(\alpha,\alpha^ q,\alpha^{q^ 2},...,\alpha^{q^{n-1}}\) form a basis for \(GF(q^ n)\) over GF(q), \(\alpha\) is called a normal element of \(GF(q^ n)\) over GF(q). An element \(\beta\) of \(GF(q^ n)\) is called a primitive element if its multiplicative order is \(q^ n-1\). In this paper the authors show that a randomly chosen element of \(GF(q^ n)\) is normal over GF(q) with probability \(\Omega (1/\log_ en)\). They also give some improved lower bounds on the probability that a randomly chosen element of \(GF(q^ n)\) is simultaneously primitive and normal over GF(q). It should be noted that there is no known method for either generating or certifying a primitive element in (probabilistic) polynomial time. Based on some work of \textit{K. Hensel} [J. Reine Angew. Math. 103, 230-237 (1888; JFM 20.0073.03)] the authors then develop a probabilistic algorithm for finding a normal element of \(GF(q^ n)\) over GF(q) that is polynomial in n and log(q). For q ``small'' relative to n, an efficient deterministic variant is also given.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11T30
zbMATH DE Number: 4183545
zbMATH Keywords: normal element
zbMATH Keywords: primitive element
zbMATH Keywords: probabilistic algorithm
reviewed by: Gary L. Ebert
MaRDI profile type: Publication
cites work: Q3809261
cites work: On the computational power of pushdown automata
cites work: Q3236675
cites work: Q4101884
cites work: Architectures for exponentiation in GF(2n)
cites work: Primitive Roots in a Finite Field
cites work: Matrix multiplication via arithmetic progressions
cites work: Bases for Finite Fields
cites work: Irreducibility of multivariate polynomials
cites work: Q5772619
cites work: A Cellular-Array Multiplier for GF(2m)
cites work: Finding Isomorphisms Between Finite Fields
cites work: Primitive Normal Bases for Finite Fields
cites work: Q3216750
cites work: Probabilistic Algorithms in Finite Fields
cites work: Approximate formulas for some functions of prime numbers
cites work: Fast multiplication of large numbers
cites work: Q3824493
cites work: CONSTRUCTION OF POLYNOMIALS IRREDUCIBLE OVER A FINITE FIELD WITH LINEARLY INDEPENDENT ROOTS
cites work: On the deterministic complexity of factoring polynomials over finite fields
cites work: New Algorithms for Finding Irreducible Polynomials Over Finite Fields
cites work: ON NORMAL BASES OF A FINITE FIELD
cites work: Q3795756
cites work: Q3469197
cites work: Some Observations on Parallel Algorithms for Fast Exponentiation in $\operatorname{GF}(2^n)$
cites work: Q5511421
cites work: VLSI Architectures for Computing Multiplications and Inverses in GF(2m)
Recommended article: Quadratic-Time Algorithms for Normal Elements
Recommended article: Searching for Primitive Roots in Finite Fields
Recommended article: Elements of provable high orders in finite fields
Recommended article: Q3973393
Recommended article: Q4515264
Recommended article: A subexponential-time algorithm for computing discrete logarithms over&lt;tex&gt;GF(p^2)&lt;/tex&gt;
Recommended article: Subquadratic-time algorithms for normal bases
Recommended article: A deterministic construction of normal bases with complexity \(O(n^ 3+n\log n\log(\log n)\log q)\)
Recommended article: On Orders of Optimal Normal Basis Generators
Recommended article: Q4855469
description: scientific article