？林开亮 中国剩余定理与剩余倍分法

以往，由于人们在处理中国剩余定理（同余）的问题时，人们只考虑m1,m2,,mk模自身求乘率M （倍数），而忽视了（发现）模与模是一种相互平等对称关系概念。特别在两两互素人们又把精力的重点集中放在只考虑a 的求乘率、而忽视b 的求乘率，且没有考虑模与模a ，b两两互素的关系与概念，所给出的Mi Mi =1(modm i) 必有解。更没有考虑模与模之间存在的隐性“不完全商”，所造成（-1）负余数现象，根据a ，b相互同等对称关系，他们必然存在各自的反乘率（倍数）、反乘数，由于这种隐性现象的存在长期没有被发现，所以导致很长一段时间“中国剩余定理”没有获得完善完美的解决方案。

       剩余倍分法对于以上方法及此类问题中存在的不完全商，以及对大商数形成的负余数的性质与概念，均研究得较为深入，对模两两互素且余数为负的问题也同步得到解决，进而推出此类问题有较为完善同步解决方案，此外，上述方法在反解问题上的研究及在深度、广度上也能令人满意。以上所述的剩余倍分法对于同余、辗转相除法、同余式组、二元一次不定方程问题有着相对完善的解决方案，且使用范围较广，可作为解决该类问题的一般方法推广。

剩余倍分法的优势

1. 剩余倍分法之倍分式计算简便，只通过简单的移位运算和四则运算即可实现，计算

所用的时间较同类的其他方法更少，其算法的时间复杂度与空间复杂度均较低。

2. 剩余倍分法的使用范围较广，既可以应用于初等数论中解决同余式、同余式组和二

元一次不定方程的相关问题，亦可用于解决计算机算法、计算机辅助设计、最优 HASH 函数

设计、快速傅里叶变换，以及环论、域论等领域中的相关问题。

3. 剩余倍分法将两两互素的模放在同等对称的地位，引入了反乘数和反乘率的概念，

考虑了负余数以及所获解数的正、反性质，从而将获解答案稳定在非负数的范围内。

4. 剩余倍分法可同时求解反乘数、反乘率，从而得出两两互素模之间存在的规律和性

质，计算方法严谨且效率高。

5. 剩余倍分法求解的中间过程，每一步都具有实际的算数意义，不同于辗转相除法的

中间过程，每一步都没有明显的实际意义。

6. 剩余倍分法具有同步纠错功能，计算过程中的每一步都可以自动检验，即若出现无

法整除的情况，则意味着计算错误；只要计算出错，后续的步骤便无法进行，由此可保证

计算的正确性。

7. 剩余倍分法所计算出的乘数、乘率、反乘数、反乘率可根据实际情况灵活选用，例

如在大模数计算时，使用反乘率或反乘数代入计算，或可大大节省计算量。

8. 剩余倍分法的原理浅显准确，易于理解，且比起其他方法来更适用于计算机编程实

现。

9. 在应用中国剩余定理定理时，按照通常的办法，是先做辗转相除法，再往回逐次算

出寄数，这样得出的答案既可能是乘数，也可能是反乘数；而剩余倍分法是往回逐次算出

乘数，最后的答案一定就是乘数，含义直观而明确。

 10. 应用剩余倍分法可以完美地解决困扰人类多年的“蓍卦发微”“行程相及”等数学问题，不仅证明了秦九韶大衍求一术、大衍总数术演算方法的正确性，而且发现“行程相及”这类问题的计算方法已不再局限于求解同余式组一般的未知数，只用速度即可求出距离，而非通 常的用速度和时间求距离，算法极尽巧妙。

引：陈永乐《素数分布及其在RSA分析中的应用》     

《国家科技报告》服务系统405700021--201701D111002/01