Chinese Remainder Theorem Approach to Montgomery-Type Algorithms
Guangwu Xu, Yiran Jia, Yanze Yang · arXiv (Cornell University) · 2024
This paper explores the ability of the Chinese Remainder Theorem formalism to model Montgomery-type algorithms. A derivation of CRT based on Qin's Identity gives Montgomery reduction algorithm immediately. This establishes a unified framework to treat modular reduction algorithms of Montgomery-type. Several recent notable variants of Montgomery algorithm are analyzed, validation of these methods are performed within the framework. Problems in some erroneous design of reduction algorithms of Montgomery-type in the literature are detected and counter examples are easily generated by using the CRT formulation.