1. Faster Modular Composition.
- Author
-
Neiger, Vincent, Salvy, Bruno, Schost, Éric, and Villard, Gilles
- Subjects
MATRIX multiplications ,POWER series ,POLYNOMIALS ,EXPONENTS ,SYMBOLIC computation - Abstract
A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n, the algorithm uses O(n
1.43 ) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O(n1.63 ) field operations in general, and n3/2+o(1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n5/3+o(1) operations, while previous ones run in O(n2 ) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF