Constructing normal bases in finite fields
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.
- Quadratic-Time Algorithms for Normal Elements
- Searching for Primitive Roots in Finite Fields
- Elements of provable high orders in finite fields
- scientific article; zbMATH DE number 16708
- scientific article; zbMATH DE number 1528681
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- Subquadratic-time algorithms for normal bases
- A deterministic construction of normal bases with complexity \(O(n^ 3+n\log n\log(\log n)\log q)\)
- On Orders of Optimal Normal Basis Generators
- scientific article; zbMATH DE number 815372
- A Cellular-Array Multiplier for GF(2m)
- Approximate formulas for some functions of prime numbers
- Architectures for exponentiation in GF(2n)
- Bases for Finite Fields
- CONSTRUCTION OF POLYNOMIALS IRREDUCIBLE OVER A FINITE FIELD WITH LINEARLY INDEPENDENT ROOTS
- Fast multiplication of large numbers
- Finding Isomorphisms Between Finite Fields
- scientific article; zbMATH DE number 3882549 (Why is no real title available?)
- scientific article; zbMATH DE number 3121635 (Why is no real title available?)
- scientific article; zbMATH DE number 4136075 (Why is no real title available?)
- scientific article; zbMATH DE number 4061359 (Why is no real title available?)
- scientific article; zbMATH DE number 4078798 (Why is no real title available?)
- scientific article; zbMATH DE number 4097511 (Why is no real title available?)
- scientific article; zbMATH DE number 3523640 (Why is no real title available?)
- scientific article; zbMATH DE number 3222940 (Why is no real title available?)
- scientific article; zbMATH DE number 3032896 (Why is no real title available?)
- Irreducibility of multivariate polynomials
- Matrix multiplication via arithmetic progressions
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- ON NORMAL BASES OF A FINITE FIELD
- On the computational power of pushdown automata
- On the deterministic complexity of factoring polynomials over finite fields
- Primitive Normal Bases for Finite Fields
- Primitive Roots in a Finite Field
- Probabilistic Algorithms in Finite Fields
- Some Observations on Parallel Algorithms for Fast Exponentiation in $\operatorname{GF}(2^n)$
- VLSI Architectures for Computing Multiplications and Inverses in GF(2m)
- Processor-efficient exponentiation in finite fields
- Normal generators of finite fields
- Trace- and norm-compatible extensions of finite fields
- Density of normal elements
- On the computation of minimal polynomials, cyclic vectors, and Frobenius forms
- Normal bases and irreducible polynomials
- On the density of normal bases in finite fields
- Subquadratic-time algorithms for normal bases
- Existence results on \(k\)-normal elements over finite fields
- Computing Frobenius maps and factoring polynomials
- Construction of self-dual integral normal bases in abelian extensions of finite and local fields
- scientific article; zbMATH DE number 446402 (Why is no real title available?)
- ON THE CONSTRUCTION OF A PRIMITIVE NORMAL BASIS IN A FINITE FIELD
- О построении нормального базиса конечного поля
- scientific article; zbMATH DE number 16708 (Why is no real title available?)
- Primitive Normal Polynomials Over Finite Fields
- A fast algorithm to compute irreducible and primitive polynomials in finite fields
- Subquadratic-time factoring of polynomials over finite fields
- A new criterion on normal bases of finite field extensions
- scientific article; zbMATH DE number 815372 (Why is no real title available?)
- Algebraic construction of quasi-split algebraic tori
- On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
- Skew differential Goppa codes and their application to McEliece cryptosystem
- Constructing irreducible polynomials recursively with a reverse composition method
- Normal elements and irreducible polynomials in finite fields
- Specific irreducible polynomials with linearly independent roots over finite fields
- Efficient and optimal exponentiation in finite fields
- Two-generation of traceless matrices over finite fields
- Computing primitive elements of extension fields
This page was built for publication: Constructing normal bases in finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639102)
