Applied Algebra Group at the University of Zürich 

Module: MAT076 Arbeitsgemeinschaft in Codierungstheorie und Kryptographie Event: n.n. Arbeitsgemeinschaft in Codierungstheorie und Kryptographie eSeminar: Faster modular composition of polynomials
Dr. Vincent Neiger's talk Date: 19.05.21 Time: 15.00  16.00 Room: Online (**This eSeminar will take place on Zoom, using the same meeting details as previous seminars. If you do not have meeting details, please contact simran.tinani@math.uzh.ch **) This talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials a and g over a commutative field, modular composition asks to compute h(a) mod g for some given h, while the minimal polynomial problem is to compute h of minimal degree such that h(a) = 0 mod g. We propose algorithms whose complexity bound improves upon previous algorithms and in particular upon Brent and Kung's approach (1978); the new complexity bound is subquadratic in the degree of g and a even when using cubictime matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals, and from efficient operations with these bases thanks to fast univariate polynomial matrix algorithms. We report on preliminary experimental results using our new Polynomial Matrix Library ( https://github.com/vneiger/pml ). Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard. 