Fast Multiplication for Skew Polynomials
Fast Multiplication for Skew Polynomials
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 …