Constructing normal bases in finite fields

DOI10.1016/S0747-7171(08)80158-7zbMath0718.11065MaRDI QIDQ2639102

Joachim von zur Gathen, Mark W. Giesbrecht

Publication date: 1990

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

probabilistic algorithmprimitive elementnormal element

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

Computing Frobenius maps and factoring polynomials, On the computation of minimal polynomials, cyclic vectors, and Frobenius forms, Skew differential Goppa codes and their application to McEliece cryptosystem, Constructing irreducible polynomials recursively with a reverse composition method, A fast algorithm to compute irreducible and primitive polynomials in finite fields, Normal bases and irreducible polynomials, Algebraic construction of quasi-split algebraic tori, A new criterion on normal bases of finite field extensions, On the density of normal bases in finite fields, Processor-efficient exponentiation in finite fields, Specific irreducible polynomials with linearly independent roots over finite fields, Efficient and optimal exponentiation in finite fields, Trace- and norm-compatible extensions of finite fields, Subquadratic-time factoring of polynomials over finite fields, Primitive Normal Polynomials Over Finite Fields, On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other, CONSTRUCTION OF SELF-DUAL INTEGRAL NORMAL BASES IN ABELIAN EXTENSIONS OF FINITE AND LOCAL FIELDS, Subquadratic-time algorithms for normal bases, Density of normal elements, Existence results on \(k\)-normal elements over finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the deterministic complexity of factoring polynomials over finite fields
• Matrix multiplication via arithmetic progressions
• Irreducibility of multivariate polynomials
• On the computational power of pushdown automata
• Fast multiplication of large numbers
• Approximate formulas for some functions of prime numbers
• Some Observations on Parallel Algorithms for Fast Exponentiation in $\operatorname{GF}(2^n)$
• Finding Isomorphisms Between Finite Fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• VLSI Architectures for Computing Multiplications and Inverses in GF(2^m)
• Architectures for exponentiation in GF(2n)
• CONSTRUCTION OF POLYNOMIALS IRREDUCIBLE OVER A FINITE FIELD WITH LINEARLY INDEPENDENT ROOTS
• ON NORMAL BASES OF A FINITE FIELD
• Probabilistic Algorithms in Finite Fields
• Primitive Normal Bases for Finite Fields
• Bases for Finite Fields
• A Cellular-Array Multiplier for GF(2^m)
• Primitive Roots in a Finite Field