Fast Chinese remaindering in practice


The Chinese remainder theorem is a key tool for the design of efficient multi-modular algorithms. In this paper, we study the case when the moduli are fixed and can even be chosen by the user. If is small or moderately large, then we show how to choose gentle moduli that allow for speedier Chinese remaindering. The multiplication of integer matrices is one typical application where we expect practical gains for various common matrix dimensions and bitsizes of the coefficients.

Occasion: MACIS 2017, Vienna, Austria, november 16, 2017

Documents: slideshow, TeXmacs source