Faster Modular Composition Using Two Relation Matrices
Open Access
- 12 July 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 315-324
Abstract
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the algebraic algorithm with the best complexity bound for this problem was that of Brent and Kung (1978). Recently, we improved this algorithm by computing and using a polynomial matrix that encodes a certain basis of algebraic relations between the polynomials. This is further improved here by making use of two polynomial matrices of smaller dimension. Under genericity assumptions on the input, this results in an algorithm using \(\tilde{O}(n^{(\omega +3)/4})\) arithmetic operations in the base field, where ω is the exponent of matrix multiplication. With naive matrix multiplication, this is \(\tilde{O}(n^{3/2})\) , while with the best currently known exponent ω this is O(n1.343), improving upon the previously most efficient algorithms.
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Faster multi-point evaluation over any fieldApplicable Algebra in Engineering, Communication and Computing, 2025
- Modular Composition Modulo Triangular Sets and Applicationscomputational complexity, 2013
- Algorithms in Real Algebraic Geometry2006
- Fast Multipoint Evaluation of Bivariate Polynomials2004
- Challenges of Symbolic Computation: My Favorite Open ProblemsJournal of Symbolic Computation, 2000
- Fast Rectangular Matrix Multiplication and ApplicationsJournal of Complexity, 1998
- Algebraic Complexity Theory1997
- Zeros, multiplicities, and idempotents for zero-dimensional systems1996
- Fast Construction of Irreducible Polynomials over Finite FieldsJournal of Symbolic Computation, 1994
- Polynomial and Matrix Computations1994