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.

Keywords: Chinese remainder theorem, algorithm, complexity, integer matrix multiplication

View: Html, TeXmacs, Pdf, BibTeX

Note: this paper has been extracted from my previous preprint “Faster Chinese Remaindering”