Subquadratic-time algorithms for normal bases
From MaRDI portal
Publication:2040602
DOI10.1007/s00037-020-00204-9zbMath1485.12002arXiv2005.03497OpenAlexW3134870882MaRDI QIDQ2040602
Éric Schost, Armin Jamshidpey, Mark W. 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
Separable extensions, Galois theory (12F10) Number-theoretic algorithms; complexity (11Y16) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Randomized algorithms (68W20) Computational methods for problems pertaining to field theory (12-08)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generating fast Fourier transforms of solvable groups
- Fast arithmetic for triangular sets: from theory to practice
- On the asymptotic complexity of rectangular matrix multiplication
- An algorithm for the construction of a normal basis
- Algorithms for exponentiation in finite fields
- The efficient computation of Fourier transforms on semisimple algebras
- Algorithms to construct normal bases of cyclic number fields
- A new polynomial factorization algorithm and its implementation
- Computing Frobenius maps and factoring polynomials
- Fast computation of special resultants
- Fast multiplication of large numbers
- Constructing normal bases in finite fields
- Modern Computer Algebra
- Fast Polynomial Factorization and Modular Composition
- Powers of tensors and fast matrix multiplication
- Finding Isomorphisms Between Finite Fields
- Addition requirements for matrix and transposed matrix products
- Fast Algorithms for Manipulating Formal Power Series
- A deterministic construction for normal bases of abelian extensions
- Subquadratic-time factoring of polynomials over finite fields
- 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
This page was built for publication: Subquadratic-time algorithms for normal bases
