Subquadratic-time algorithms for normal bases
type: Item
instance of: scholarly article
title: Subquadratic-time algorithms for normal bases
zbMATH Open document ID: 1485.12002
author: Armin Jamshidpey
author: Éric Schost
author: Mark Giesbrecht
published in: Computational Complexity
publication date: 2021-07-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/2005.03497
review text: In a finite Galois extension \(K/F\) with Galois group \(G=\mathrm{Gal}(K/F)\), an element \(\alpha\in K\) is called \textit{normal} if its Galois orbit \(\alpha^G\) forms an \(L\)-basis of \(K\). Under the assumption that \(K\) is represented \(K=L(\xi)\) with a power basis \(1,\xi,\xi^2,\ldots\), and the elements of \(G\) are given through their action on \(\xi\), and that \(G\) is abelian or metacyclic, the authors give a Monte-Carlo algorithm to test whether a particular element \(\alpha\in K\) is normal. This algorithm runs in time \(\tilde{\mathcal O}(n^e)\) for \(e<1.99\). (The soft-O notation \(\tilde{\mathcal O}\) leaves out logarithmic factors.) The concrete value for \(e\) is \(3/4\cdot\omega(3/4)\), where \(\omega(3/4)\) stems from the cost of multiplying by a \(n\times n^{3/4}\) matrix. This extends their prior result [\textit{M. Giesbrecht} et al., in: Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC '19, Beijing, China, July 15--18, 2019. New York, NY: Association for Computing Machinery (ACM), 179--186 (2019; Zbl 1467.11124)] from abelian to metabelian Galois groups. They also show that they can perform basis conversion between the power basis and \(\alpha^G\) in the same (Monte-Carlo) complexity.
reviewed by: A. Hulpke
Mathematics Subject Classification ID: 12-08
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 12F10
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7371506
zbMATH Keywords: probabilistic algorithm
zbMATH Keywords: normal bases
zbMATH Keywords: Galois groups
MaRDI profile type: Publication
OpenAlex ID: W3134870882
arXiv ID: 2005.03497
cites work: Q4888749
cites work: Fast computation of special resultants
cites work: On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms
cites work: Fast Algorithms for Manipulating Formal Power Series
cites work: Q4331740
cites work: Generating fast Fourier transforms of solvable groups
cites work: Q4039887
cites work: Q3568138
cites work: Q5301663
cites work: Algorithms for exponentiation in finite fields
cites work: Modern computer algebra
cites work: Constructing normal bases in finite fields
cites work: Computing Frobenius maps and factoring polynomials
cites work: Quadratic-Time Algorithms for Normal Elements
cites work: An algorithm for the construction of a normal basis
cites work: Q4650358
cites work: Algebraic construction of quasi-split algebraic tori
cites work: Q4087417
cites work: Subquadratic-time factoring of polynomials over finite fields
cites work: Addition requirements for matrix and transposed matrix products
cites work: Fast Polynomial Factorization and Modular Composition
cites work: Q2770573
cites work: Powers of tensors and fast matrix multiplication
cites work: Q4607951
cites work: Finding Isomorphisms Between Finite Fields
cites work: Fast arithmetic for triangular sets: from theory to practice
cites work: On the asymptotic complexity of rectangular matrix multiplication
cites work: The efficient computation of Fourier transforms on semisimple algebras
cites work: A deterministic construction for normal bases of abelian extensions
cites work: Algorithms to construct normal bases of cyclic number fields
cites work: Fast multiplication of large numbers
cites work: On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
cites work: A new polynomial factorization algorithm and its implementation
cites work: Q3025353
DOI: 10.1007/S00037-020-00204-9
Recommended article: Quadratic-Time Algorithms for Normal Elements
Recommended article: COMPUTING NORMAL INTEGRAL BASES OF ABELIAN NUMBER FIELDS
Recommended article: An algorithm for the construction of a normal basis
Recommended article: Constructing normal bases in finite fields
Recommended article: A Polynomial Time Nilpotence Test for Galois Groups and Related Results
Recommended article: A method for deciding whether the Galois group is abelian
Recommended article: Fast norm computation in smooth-degree abelian number fields
Recommended article: An efficient algorithm for the computation of Galois automorphisms
Recommended article: Low Complexity Normal Elements over Finite Fields of Characteristic Two
Recommended article: Q3698311
description: scientific article