Faster modular composition using two relation matrices
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914277588205568 |
|---|---|
| author | Neiger, Vincent Salvy, Bruno Schost, Éric Villard, Gilles |
| author_facet | Neiger, Vincent Salvy, Bruno Schost, Éric Villard, Gilles |
| contents | Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem was that of Brent and Kung (1978). Recently, we improved Brent and Kung's 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^{(ω+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(n^{1.343})$, improving upon the previously most efficient algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17422 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster modular composition using two relation matrices Neiger, Vincent Salvy, Bruno Schost, Éric Villard, Gilles Symbolic Computation Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem was that of Brent and Kung (1978). Recently, we improved Brent and Kung's 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^{(ω+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(n^{1.343})$, improving upon the previously most efficient algorithms. |
| title | Faster modular composition using two relation matrices |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2601.17422 |