Subquadratic-time algorithms for normal bases

DOI10.1007/S00037-020-00204-9zbMATH Open1485.12002arXiv2005.03497OpenAlexW3134870882MaRDI QIDQ2040602FDOQ2040602

Authors: Armin Jamshidpey, Éric Schost, Mark Giesbrecht 

Publication date: 14 July 2021

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)