Composition Modulo Powers of Polynomials | Zendy

Joris van der Hoeven | Zendy; Grégoire Lecerf | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Composition Modulo Powers of Polynomials

Author(s) -

Joris van der Hoeven,

Grégoire Lecerf

Publication year - 2017

Publication title -

hal (le centre pour la communication scientifique directe)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/3087604.3087634

Subject(s) - modulo , composition (language) , polynomial , finite field , context (archaeology) , univariate , mathematics , modular design , computational complexity theory , arithmetic , computer science , discrete mathematics , algebra over a field , algorithm , pure mathematics , mathematical analysis , paleontology , philosophy , linguistics , statistics , multivariate statistics , biology , operating system

Modular composition is the problem to compose two univariate polynomials modulo a third one. For polynomials with coefficients in a finite field, Kedlaya and Umans proved in 2008 that the theoretical bit complexity for performing this task could be made arbitrarily close to linear. Unfortunately, beyond its major theoretical impact, this result has not led to practically faster implementations yet. In this paper, we study the more specific case of composition modulo the power of a polynomial. First we extend previously known algorithms for power series composition to this context. We next present a fast direct reduction of our problem to power series composition.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research