Apparaît dans la collection : 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Sparse polynomials with integer coefficients are a basic building block in computer algebra systems, as well as an important fundamental object for algorithmic study. Since at least the 1980s, efficient algorithms have been constructed based on the flexibility afforded by changing the integer modulus repeatedly during the computation. This talk will attempt to briefly survey some of the modulus-choosing techniques employed in recent results to achieve faster algorithms. We will also briefly examine when these techniques (fail to) extend to the case of floating point computations and field extensions.