解一元线性同余式组的一个新算法

A New Algorithm for Solving Simultaneous Linear Congruences in One Variable

中国余数定理是1000多年来中外数学家在对一元线性同余式组的研究过程中形成的一个世界公认的经典算法,在计算机中运用该经典算法可以快速处理庞大数值和庞大数量的数据,且效率远超人工计算。作为寻求比经典算法更高效地解一元线性同余式组的一个尝试,本文提出了一个新算法。新算法首先构建一个通过逐一试探来求解的基本策略,然后逐级进行变量置换以小值求大值以减少试探次数,最后推导出一个完全无需试探而求得结果的迭代算法。理论分析和计算机对比计算结果都表明:新算法可以处理的最大数据比经典算法能处理的最大数据大几倍到千倍。同时,新算法解一元线性同余式组所需的运算时间比经典算法缩短了25%以上。

Over more than a thousand years of research on simultaneous linear congruences in one variable,Chinese and foreign mathematicians have developed a world-renowned classic algorithm-Chinese Remainder Theorem.This classic algorithm can be run in computers to handle large values and large amounts of data quickly,and its efficiency far exceeds manual calculation.As an attempt to seek a more efficient way to solve simultaneous linear congruences in one variable than the classic algorithm,a new algorithm was proposed here.The new algorithm first constructed a basic strategy for solving the problem through trial and error.Then,variable replacement was progressively performed to find larger value with small value,in order to reduce the number of trials.Finally,an iterative algorithm was derived that can obtain the solution without any trial and error.Analysis and comparison with computer-calculated results show that the maximum data that can be processed by the new algorithm is several times,up to a thousand times,larger than those of the classic algorithm.In addition,the computation time required by the new algorithm to solve simultaneous linear congruences in one variable is reduced by over 25%compared to the classic algorithm.