Subquadratic-time algorithms for normal bases

DOI10.1007/S00037-020-00204-9MaRDI QIDQ2040602zbMATH OpenOpenAlexFDO

Authors Armin Jamshidpey, Éric Schost, Mark Giesbrecht

Publication date 14 July 2021

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.03497

zbMATH Keywords

Galois groupsnormal basesprobabilistic algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20) Separable extensions, Galois theory (12F10) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Number-theoretic algorithms; complexity (11Y16) Computational methods for problems pertaining to field theory (12-08)

Abstract: For any finite Galois field extension $mathsfK/mathsfF$, with Galois group $G=mathrmGal(mathsfK/mathsfF)$, there exists an element $alphainmathsfK$ whose orbit $Gcdotalpha$ forms an $mathsfF$-basis of $mathsfK$. Such a $alpha$ is called a normal element and $Gcdotalpha$ is a normal basis. We introduce a probabilistic algorithm for testing whether a given $alphainmathsfK$ is normal, when $G$ is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether $alpha$ is normal can be reduced to deciding whether $su{m}_{ginG}g(alpha)ginmathsfK[G]$ is invertible; it requires a slightly subquadratic number of operations. Once we know that $alpha$ is normal, we show how to perform conversions between the power basis of $mathsfK/mathsfF$ and the normal basis with the same asymptotic cost.

Recommendations

• Quadratic-Time Algorithms for Normal Elements
• Computing normal integral bases of abelian number fields
• An algorithm for the construction of a normal basis
• Constructing normal bases in finite fields
• A Polynomial Time Nilpotence Test for Galois Groups and Related Results
• A method for deciding whether the Galois group is abelian
• Fast norm computation in smooth-degree abelian number fields
• An efficient algorithm for the computation of Galois automorphisms
• Low Complexity Normal Elements over Finite Fields of Characteristic Two
• scientific article; zbMATH DE number 3924140

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 2187158 (Why is no real title available?)
• scientific article; zbMATH DE number 193016 (Why is no real title available?)
• scientific article; zbMATH DE number 3506978 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• A deterministic construction for normal bases of abelian extensions
• A new polynomial factorization algorithm and its implementation
• Addition requirements for matrix and transposed matrix products
• Algebraic construction of quasi-split algebraic tori
• Algorithms for exponentiation in finite fields
• Algorithms to construct normal bases of cyclic number fields
• An algorithm for the construction of a normal basis
• Computing Frobenius maps and factoring polynomials
• Constructing normal bases in finite fields
• Fast Algorithms for Manipulating Formal Power Series
• Fast arithmetic for triangular sets: from theory to practice
• Fast computation of special resultants
• Fast multiplication of large numbers
• Fast polynomial factorization and modular composition
• Faster inversion and other black box matrix computations using efficient block projections
• Finding Isomorphisms Between Finite Fields
• Generating fast Fourier transforms of solvable groups
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Modern computer algebra
• On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
• On matrices with displacement structure: generalized operators and faster algorithms
• On the asymptotic complexity of rectangular matrix multiplication
• On the complexity of the D5 principle
• Powers of tensors and fast matrix multiplication
• Quadratic-Time Algorithms for Normal Elements
• Subquadratic-time factoring of polynomials over finite fields
• The efficient computation of Fourier transforms on semisimple algebras

Cited in

(5)

• Constructing normal bases in finite fields
• Quadratic-Time Algorithms for Normal Elements
• Subquadratic Computational Complexity Schemes for Extended Binary Field Multiplication Using Optimal Normal Bases
• scientific article; zbMATH DE number 176719 (Why is no real title available?)
• New deterministic algorithm for constructing normal bases in finite fields

This page was built for publication: Subquadratic-time algorithms for normal bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040602)