同余式组求解的改进算法  

A Modified Algorithm for Solving System of Congruence

作　　者：童昱博 李奥[1] 

机构地区：[1]中南大学数学与统计学院,长沙410083

出　　处：《数学理论与应用》2015年第4期74-79,共6页Mathematical Theory and Applications

摘　　要：同余式组求解是数论中最基本的问题之一,在公钥系统与通信编码等领域具有许多重要的应用.本文通过将求衍数的过程转化为求解一个二元一次不定方程整数特解,提出了求解此类问题的新算法.理论上证明了:对给定的k个一次同余式,经典的孙子算法同本文的改进算法的复杂度之比为klog_(kM)M(若M_i为同余式组中除去第i个同余式,其余k-1个同余式的模的乘积,M是M_i的平均值).数值实验结果表明了新算法所需时间接近于经典孙子定理所需时间的0.5倍,验证了该改进算法的高效性.Solving the system of congruence is a fundamental problem in number theory which applies common- ly in the field of public key system and communication coding etc. In this paper, we transform the preeess of seeking the derivative numbers into searching the particular integer solutions of an indeterminate binary linear function and come up with a new algorithm to solve this class of problems. Theoretically, given a certain group of k linear congruence expressions, we prove the complexity ratio of classical Sunzi algorithm to our new algo- rithm is k logkmM（ Mi is the product of all modules of congruence expressions except for the ith one, M is the mean value of Mi ）. The numerical experiment demonstrates that our modified algorithm consumes just roughly half of the time the classical Sunzi algorithm does and therefore indicates the high effcieney this algorithm en- dows.

关 键 词：同余式组 孙子定理 数值实验 

分 类 号：O156[理学—数学]