Fast Polynomial Factorization and Modular Composition 2: Multimodular Reduction with Primes up to 16 log N and Kronecker Lifting Correctly Evaluate Multivariate Polynomials over (ℤ/rℤ)[Z]/(E(Z))Research Paper
Multivariate multipoint evaluation asks for the values of a polynomial over a ring , with individual degrees at most , at given points of . Kedlaya and Umans showed that, over finite fields and rings , this problem can be solved in time nearly linear in the input…