Practical Polynomial Factoring in Polynomial Time

par Andy Novocin (ENS-Lyon)

jeudi 10 mars 2011, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

This talk presents some recent and on-going work on factoring polynomials in Z[x]. The goal of this work is to arrive at a practical, implementable, and efficient algorithm for which we can prove a tight complexity bound (which should be the best existing complexity bound). We give the overall structure of our algorithm with insights into the practical and theoretical issues which guide the design. We also present the behavior of the algorithm in theory and give some early running times of our implementation.