A CRT Framework for Montgomery-Type Modular Reduction

Abstract

Montgomery reduction is one of the fundamental techniques for efficient modular arithmetic. In this paper, we present a new interpretation of Montgomery-type reduction algorithms through the Chinese Remainder Theorem (CRT). We show that the classical Montgomery reduction algorithm arises naturally from the CRT identity, which further reveals a common algebraic invariant underlying a family of Montgomery-type reduction algorithms. This leads to a unified CRT framework for their derivation, analysis, and verification. Within this framework, several recent variants of Montgomery reduction are interpreted in a uniform manner, their correctness proofs become transparent, and their differences are seen to lie only in the representation of the correction term and the evaluation of a common CRT quotient. The framework also provides a convenient tool for analyzing existing reduction algorithms, allowing incorrect parameter ranges to be identified and counterexamples to be constructed naturally.

arXiv comment15 pages