Skip to content
DraconiticResearch
Search Sources API
186,125 studies31 sourcesUpdated 58 min ago
Peer-reviewedCC BY-NC-ND 4.0Journal of Complexity

Fast modular composition using spiroids

  • Joris van der Hoeven
  • Grégoire Lecerf
Open at sourcePDFDOICite

Abstract

Given three univariate polynomials P, Q, and R with coefficients in a prime finite field, we present a new algorithm for computing P ∘ Q modulo R in time close to linear and with an asymptotic complexity smaller than the one of the Kedlaya-Umans algorithm. As a novelty, our method mostly performs fast floating point Fourier transforms, while previously known ones rely on ad hoc algebraic constructions of finite fields.

Related

  1. Sensing Fast and Distant Targets in Overspread Channels with Zak-OTFS and Modular Arithmetic
    Andrea Novero, Mudasir Ahmad Sheikh, Danish Nisar +3
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Explicit height bounds on modular polynomials for the elliptic j-invariant, cube root of j, and Weber modular function f
    Abraham Zhang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Modular integrals for individual modular knots
    Toshiki Matsusaka
    arXivPreprintarXiv licenceFull textAlgebra & number theoryGeometry & topologyarXiv
  4. Modular resurgent structures for vectors
    Miranda C.N Cheng, Ioana Coman, Veronica Fantini +1
    HALPreprintLicence not statedMathematical physicsHigh-energy & particle physicsHAL
  5. Classification of integral modular data up to rank 13
    Max A. Alekseyev, Winfried Bruns, Sébastien Palcoux +1
    Journal of Mathematical PhysicsPeer-reviewedLicence not statedFull text6 citedGeometry & topologyOpenAlex

Cite

BibTeXRIS
BibTeX
@article{hoeven2026fast,
  title = {{Fast modular composition using spiroids}},
  author = {Joris van der Hoeven and Grégoire Lecerf},
  journal = {Journal of Complexity},
  year = {2026},
  month = oct,
  doi = {10.1016/j.jco.2026.102073},
  url = {https://hal.science/hal-05378789v2},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - JOUR
TI  - Fast modular composition using spiroids
AU  - Joris van der Hoeven
AU  - Grégoire Lecerf
PY  - 2026
DA  - 2026/10/06
JO  - Journal of Complexity
DO  - 10.1016/j.jco.2026.102073
UR  - https://hal.science/hal-05378789v2
AB  - Given three univariate polynomials P, Q, and R with coefficients in a prime finite field, we present a new algorithm for computing P ∘ Q modulo R in time close to linear and with an asymptotic complexity smaller than the one of the Kedlaya-Umans algorithm. As a novelty, our method mostly performs fast floating point Fourier transforms, while previously known ones rely on ad hoc algebraic constructions of finite fields.
SN  - 0885-064X
SN  - 1090-2708
ER  -