Fast Multiplication for Skew Polynomials
Authors:
Open Access
- 23 July 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 77-84
Abstract
We describe an algorithm for fast multiplication of skew polynomials. It is based on fast modular multiplication of such skew polynomials, for which we give an algorithm relying on evaluation and interpolation on normal bases. Our algorithms improve the best known complexity for these problems, and reaches the optimal asymptotic complexity bound for large degree. We also give an adaptation of our algorithm for polynomials of small degree. Finally, we use our methods to improve on the best known complexities for various arithmetics problems.Keywords
All Related Versions
Funding Information
- Investissements d'Avenir (ANR-11-LABX-0020-01)
This publication has 12 references indexed in Scilit:
- A new faster algorithm for factoring skew polynomials over finite fieldsJournal of Symbolic Computation, 2017
- Sub-quadratic decoding of Gabidulin codes2016
- Quasi-optimal Multiplication of Linear Differential Operators2012
- An Algorithm for the Construction of a Normal BasisJournal of Number Theory, 1999
- Factoring in Skew-polynomial Rings over Finite FieldsJournal of Symbolic Computation, 1998
- Maximum-rank array codes and their application to crisscross error correctionIEEE Transactions on Information Theory, 1991
- Constructing normal bases in finite fieldsJournal of Symbolic Computation, 1990
- Bilinear forms over a finite field, with applications to coding theoryJournal of Combinatorial Theory, Series A, 1978
- Galoissche Theorie und DarstellungstheorieMathematische Annalen, 1933
- Theory of Non-Commutative PolynomialsAnnals of Mathematics, 1933