TY - GEN
T1 - Composition modulo powers of polynomials
AU - Van Der Hoeven, Joris
AU - Lecerf, Grégoire
N1 - Publisher Copyright:
© 2017 Copyright held by the owner/author(s).
PY - 2017/7/23
Y1 - 2017/7/23
N2 - 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.
AB - 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.
KW - Algorithm
KW - Complexity
KW - Modular composition
KW - Series composition
UR - https://www.scopus.com/pages/publications/85027705772
U2 - 10.1145/3087604.3087634
DO - 10.1145/3087604.3087634
M3 - Conference contribution
AN - SCOPUS:85027705772
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 445
EP - 452
BT - ISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation
A2 - Burr, Michael
PB - Association for Computing Machinery
T2 - 42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017
Y2 - 25 July 2017 through 28 July 2017
ER -