Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation.

par Vincent Neiger

jeudi 22 oct. 2020, 10:30 → 11:30 Europe/Paris

https://bbb.unilim.fr/b/vac-m6r-7dv

This talk presents joint work with J. Rosenkilde and G. Solomatov, about
new algorithms for bivariate multi-point evaluation, interpolation and
modular composition, which under certain assumptions have quasi-linear
complexity. For multi-point evaluation and interpolation we assume that
the set of points is generic and available for precomputation. In the
case of modular composition, similar assumptions are made on a bivariate
ideal which depends on part of the input. The key tool is an algorithm
that reshapes the degree bounds of a given bivariate polynomial while
preserving its membership in a coset of some fixed bivariate ideal
available for precomputation.