论文部分内容阅读
同余式组求解是数论中最基本的问题之一,在公钥系统与通信编码等领域具有许多重要的应用.本文通过将求衍数的过程转化为求解一个二元一次不定方程整数特解,提出了求解此类问题的新算法.理论上证明了:对给定的k个一次同余式,经典的孙子算法同本文的改进算法的复杂度之比为klog_KMM(若Mi为同余式组中除去第i个同余式,其余k-1个同余式的模的乘积,M是M的平均值).数值实验结果表明了新算法所需时间接近于经典孙子定理所需时间的0.5倍,验证了该改进算法的高效性.