中北大学学报（自然科学版）2023，Vol.44Issue(6)：591-596,631,7.DOI:10.3969/j.issn.1673-3193.2023.06.002
解一元线性同余式组的一个新算法
A New Algorithm for Solving Simultaneous Linear Congruences in One Variable
谢照林1
作者信息
- 1. 美国布鲁克斯自动化公司,加州佛利蒙市94538
- 折叠
摘要
Abstract
Over more than a thousand years of research on simultaneous linear congruences in one varia-ble,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 a-mounts 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 prob-lem through trial and error.Then,variable replacement was progressively performed to find larger val-ue 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-calcu-lated 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 re-quired by the new algorithm to solve simultaneous linear congruences in one variable is reduced by over 25％compared to the classic algorithm.关键词
同余式/模数运算/模倒数/迭代算法Key words
congruence/modulo operation/modular inverse/iteration algorithm分类
数理科学引用本文复制引用
谢照林..解一元线性同余式组的一个新算法[J].中北大学学报（自然科学版）,2023,44(6):591-596,631,7.
