EUVIMEDEUVIMED entdecken
Crossref

Modular Composition for Decomposable Polynomials

Éric Schost

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →