Faster Modular Composition - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Journal of the ACM (JACM) Année : 2023

Faster Modular Composition

Résumé

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.
Fichier principal
Vignette du fichier
Faster Modular Composition.pdf (1.18 Mo) Télécharger le fichier

Dates et versions

hal-03380258 , version 1 (15-10-2021)

Identifiants

Citer

Vincent Neiger, Bruno Salvy, Éric Schost, Gilles Villard. Faster Modular Composition. Journal of the ACM (JACM), 2023. ⟨hal-03380258⟩
302 Consultations
125 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More