Modular Composition for Decomposable Polynomials
ACM Communications in Computer Algebra · 01.12.2025 · 59 (4) · 106-109
DOI: 10.1145/3832046.3832055 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Communications in Computer Algebra, online erschienen am 18.08.2026. Verfasst von Éric Schost. Die Arbeit nennt 16 Literaturangaben.
Abstract (Originalsprache)
Modular composition is one of the operations on polynomials in A[ x ] (A a commutative ring) for which no quasi-linear algorithm is known. Given polynomials f, g, a in A[ x ], with f monic of degree n and g, a of degrees less than n , it amounts to computing g ( a ) rem f , where rem denotes the Euclidean division remainder. When A is the finite field F q , this operation is a major ingredient for fast factorization algorithms in F q [ x ] [5, 9, 10]. Another important particular case is with f = x n , that is, composition of power series, which itself is an important ingredient in algorithms such as power series reversion, or the solution of certain functional equations [3].
Zitieren
APA
Schost, É. (2025). Modular Composition for Decomposable Polynomials. ACM Communications in Computer Algebra, 59(4), 106-109. https://doi.org/10.1145/3832046.3832055
Vancouver
Schost É. Modular Composition for Decomposable Polynomials. ACM Communications in Computer Algebra. 2025;59(4):106-109. doi:10.1145/3832046.3832055
BibTeX
@article{Schost2025,
author = {Schost, Éric},
title = {Modular Composition for Decomposable Polynomials},
journal = {ACM Communications in Computer Algebra},
year = {2025},
volume = {59},
number = {4},
pages = {106--109},
doi = {10.1145/3832046.3832055}
}
EUVIMED