Faster Modular Composition

10/15/2021
by   Vincent Neiger, et al.
0

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(n^1.63) field operations in general, and n^3/2+o(1) field operations in the particular case of power series over a field of large enough characteristic. If using cubic-time matrix multiplication, the new algorithm runs in n^5/3+o(1) operations, while previous ones run in O(n^2) 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset