一种新型的因数分解算法.DOC

1、http:/- 1 -中 国 科 技 论 文 在 线一种新型的因数分解算法 李联林 *作者简介：李联林，男，1953 年出生。国防科技大学（原长沙工学院）自动控制系毕业，曾长期在西昌卫星发射中心工作，1985 年担任 01 号发射指挥员，成功地指挥了我国第一颗实用通信卫星发射，中央电视台于 2010 年 11 月在“风雨探月港 “的专题片中对作者进行过介绍。因科研成果突出，多次立功受奖，并于 1986 年被共青团中央、解放军总政治部联合授予了“边陲优秀儿女“ 的荣誉称号。现在主要研究方向为计算数学及数论. E-mail: （保利科技有限公司）5 摘要：本文给出了一种原创性的因数分解（快速筛除）

2、算法，对奇数 N 的计算复杂度为O(n*N1/2)。算法利用一个多项式公式，只需要经过有限次的加、减法计算，复杂度仅为O（n），即可完成对任意大奇数 N 的一次筛除，计算复杂度要比传统的除法方式下降一个等级，并且简单易行。本文还以定理的形式创立了一个二元二次方程，可以作为判定任意质数与合数的充分必要条件。10 关键词：计算数学；初等数论；因数分解；除法中图分类号：TP301.6；O156.1A New Algorithm for FactorizationLI Lianlin15 (Poly Technologies, Inc.)Abstract: This paper presents an

3、 original algorithm for factorization and/or rapid sieve. The complexity to any odd number N is O(n*N1/2). Each exact division and/or sieve completed by a polynomial formula to a very large odd number only needs limited times of addition and subtraction. Hence the complexity of each division by this

4、 simple algorithm is O(n) only. It will be 20 reduced one grade compared with the tradional division method. Also the author of the paper establishes a binary quadratic equation by the theorem as the necessary and sufficient conditions of prime numbers and composite numbers.Key words: computational

5、mathematics; elementary number theory; factorization; division25 0 引言因数分解始终是数论研究中的一个重要课题，它不仅仅只是一个抽象的数学理论问题，更是一个在工程领域里被广泛遇到的计算数学难题。因数分解与质数识别是密切相关的两个不同课题，但是因数分解问题的难度要更高一些。这就是说在很多情况下，即使我们可以有多项式时间复杂度的算法来进行质数识别，甚至明知某一个整数 N 就是一个合数，但30 是要得到它的一个因子仍然非常困难，因为目前所有因数分解算法的计算复杂度都是指数时间等级的。公钥密码的理论基石，就是建立在因数分解难解性的基础上

6、发展起来的。如果针对因数分解问题能够找到一种更加有效的算法，那么目前正在广泛使用的绝大多数 RSA 公开密钥码体制，将面临着被破解的风险，因为 RSA 体制与因数分解问题密切相关。35 一种虽然效率并不高，但是却非常简明的因数分解算法就是试除法。因为合数 N 最小的因子不会大于 N1/2，所谓的试除法，就是用所有小于 N1/2的奇（质）数分别去试除奇数N，在最坏的情况下需要进行不多于 N1/2次除法，而使用传统的竖式算法（长除法），每次除法的计算复杂度为 O（n 2）。本文给出一种属于原创性质的快速筛除算法，因为需要讨论这种新型除法方式在连续筛除的情况下，对于除数的适用范围，所以是通过试除法来

7、进http:/- 2 -中 国 科 技 论 文 在 线40 行应用举例的。但是，核心内容却是讨论如何对于传统的除法方式进行一种创新：首先创立一种奇数的 X 集列表，推导出一个可以换模求余的多项式公式，在试除法的模式下，通过有规律地置换（迭代）、修改一个余数公式中间的部分参数，即可完成用从大到小的模数，对于奇数 N 的连续模除求余；为了进一步提高计算效率，对于所有小于 N1/2的模（除）数进行分段，引进自动控制系统理论中负反馈的概念再对算法进行改进。这样一来，可以45 使得无论奇数 N 有多么大，每次筛除都只需要进行有限次数（多项式）的加减法即可完成，筛除的计算复杂度就不会大于 O（n），相比传

8、统的除法方式下降了一个等级。实质上这种快速筛除算法，是对于四则运算中原有除法方式的一种创新或者补充。为了便于读者的阅读和理解，建议先浏览一下本文最后的结束语部分，可以对这种新型快速筛除算法的要点有个初步的了解。50 1 X 集列表1.1X 集的定义定义：任意一个奇数N都可以用一组由N位符号（1或0）所构成的X集来表达，X = X1，X 2，X j ,，X N-1,XN。如果这个奇数N能够被某个小于或者等于它的质数j所整除，那么它的X集中第j位的符号X j ，以及j的倍数位上的X值符号都被标记为0；除此以外其余55 位数上的X值符号，均被标记为1。X集定义与作者曾经提出过的S集定义的主要区别，就

9、是多出来一个第N位的X值符号XN，而且被标记为1的X值符号也没有+1和-1的正负之分，这将给算法带来很多便利，也就彻底脱离了数论中原有的三角和、特征和概念的束缚。合数的X集中，必定会有某些位数小于N的X值符号等于0，因为这个合数能够被某个质60 因数j所整除。质数的X集中只有最后一位X值等于0，因为质数只能够被它本身整除。奇数61以下的X集列表如下。3， X =1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，05， X =1，1，1，1，0，1，1，1，1，0，1，1，1，1，0，1，1，1，1，0 7， X =1，1，1，1，1，1，0，1，1，1

10、，1，1，1，0，1，1，1，1，1，1，09， X =1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，011，X =1，1，1，1，1，1，1，1，1，1，0，1，1，1，1，1，1，1，1，1，1，013，X =1，1，1，1，1，1，1，1，1，1，1，1，0，1，1，1，1，1，1，1，1，1，1，1，1，015，X =1，1，0，1，0，0，1，1，0，0，1，0，1，1，0，1，1，0，1，0，0，1，1，0，0，1，0，1，1，017，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，0http:/- 3 -中 国 科 技 论 文 在 线1

11、9，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，021，X =1，1，0，1，1，0，0，1，0，1，1，0，1，0，0，1，1，0，1，1，023，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，025，X =1，1，1，1，0，1，1，1，1，0，1，1，1，1，0，1，1，1，1，0，1，1，1，1，027，X =1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1， 0，1，1，029，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1

12、，1，1，1，1，1，1，1，1，031，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，033，X =1，1，0，1，1，0，1，1，0，1，0，0，1，1，0，1，1，0，1，1，0，0，1，0，1，1，0，1，1，0，1，1，035，X =1，1，1，1，0，1，0，1，1，0，1，1，1，0，0，1，1，1，1，0，0，1，1，1，0，1，1，0，1，0，1，1，1，1，037，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1，1，1，1，1，

13、1，1，1，1，1，039，X =1，1，0，1，1，0，1，1，0，1，1，0，0，1，0，1，1，0，1，1，0，1，1，0，1，0，0，1，1，0，1，1，0，1，1，0，1，1，041，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，043，X =1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，045，X =1，1，0，1，0，0，1，1，0，0，1

14、，0，1，1，0，1，1，0，1，0，0，1，1，0，0，1，0，1，1，0，1，1，0，1，0，0，1，1，0，0，1，0，1，1，047，X = http:/- 4 -中 国 科 技 论 文 在 线1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，049，X = 1，1，1，1，1，1，0，1，1，1，1，1，1，0，1，1，1，1，1，1，0，1，1，1，1，1，1，0，1，1，1，1，1，1，0，1，1，1，1，1，1，0，1，1，1，1，1，1，051

15、，X = 1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，0，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，0，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，053，X = 1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，055，X = 1，1，1，1，0，1，1，1，1，0，0，1，1，1，0，1，1，1，1，0，1，0，1，1，0，1，1，1，1，0，1，1，0，1，0，1，1，1

16、，1，0，1，1，1，0，0，1，1，1，1，0，1，1，1，1，057，X = 1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，0，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，0，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1，059，X = 1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，061，X = 1，1，1，1，1，1，1，1

17、，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，01.2X 集中 X 值符号的循环规律传统的试除法只是按照质数与合数的定义，在一维的数轴上对整数进行筛除，效率当然低一些。而X集列表表示出来的却是一个二维坐标下的符号列表，它的纵坐标是奇数（也65 可以扩大到所有的整数），横坐标则是X值的位数。所谓某个奇数的X j，指的就是这个奇数X集中位数为j的X值符号。单个奇数的X集本身并无特别之处，但是用多个奇数X集组合成的X集列表，却能给我们创造

18、出在二维平面上对奇数进行筛除的条件，效率因而可以提高。X集列表中各个奇数上下左右的X值符号相互之间都有规律可寻，简单地可以概括为http:/- 5 -中 国 科 技 论 文 在 线“上下、左右循环”。纵向的X值符号X j，以位数j为周期进行循环；横向的X值符号X j，以70 奇数N为周期进行循环。无论奇数有多大，位数有多长，都是如此。因而就可以根据X值符号纵向和横向的循环规律，无限制地纵向和横向扩张X集列表。纵向或横向循环的X值符号，循环的周期长度既可以等于奇数和位数，也可以小于奇数和位数，但是能够整除奇数和位数。例如，X 3的位数为3，纵向循环的X值是0，1，1，周期长度等于3；奇数9的X值

19、X 9，位数为9，纵向循环的X值也是0，1，1，周期长度等于3。奇数75 15横向循环的X值是1，1，0，1，0，0，1，1，0，0，1，0，1，1，0，周期长度等于15；奇数15的X集中从第16位到第30位横向循环X值，仍然是1，1，0，1，0，0，1，1，0，0，1，0，1，1，0。相同的奇数与位数之间，除了循环的起止点有所区别以外，横向和纵向的循环规律也相同。例如，奇数15的X 15纵向循环规律是0，1，1，0，1，0，0，1，1，0，0，1，0，1，1，与横向的循环规律类似。80 1.3X 集中质数位上纵向循环周期长度无论奇数N为何值，它的X集中质数位上纵向循环的X值，循环周期的长度就

20、等于这个质数。换句话说，在j个连续的奇（整）数当中，必（只）有一个能够被质数j整除。证明假定任意一个奇数N，能够被某一个小于或者等于它的质数j所整除，那么新的奇数k*N85 仍然能够被j所整除，其中k = 1，3，5，7， 。而在这些奇数之间分布的其余奇数，k*N + R，当R为偶数且小于2*j时，R = 2，4，6，均不可能被j所整除。显然R只能有j-1个，那么奇数k*N + R，都不可能被j所整除。证明完毕。1.4X 集列表的快速扩张假定我们已经获得了奇数N以下所有的X集列表，就能够区分所有小于N的质数和合数，90 也就能够获得所有小于N的质数位上X值的纵向循环规律，从而可以迅速得到新的奇

21、数（N+2）的X集。因为篇幅的限制，X集列表中描红加粗的那部分X值只是示意如何进行这种横向循环扩张。X集列表扩张后的X值与X集原有的定义完全相符，也不会破坏原有的循环变化规律。例如，奇数3本来是没有X值X 9的，扩张后奇数3就可以有X 9；在位数为9上，纵向循环的X值仍95 然是0，1，1，周期长度等于3，与原有奇数9的X集中X 9的纵向循环规律完全相同。例如奇数15的X 15，因此也可以向上循环，向上循环和原有向下的循环规律相同。利用X集列表中的这种循环规律，使得我们能够快速地扩张X集列表。但是，计算机的存储空间始终是有限的，这种扩张当然不可能无限制地进行下去。所以本文将把讨论的重点放在如何

22、利用有限的X集列表，或者是仅仅利用X集列表这种二维平面的概念（并不真正需要在计算机中存储100 这种X集列表），通过对于一种多项式公式的计算，即可对更大的奇数进行快速筛除或者是有效地进行因数分解，因此不需要对X集列表如何进行扩张展开更多的讨论。2 一种新型的因数分解（快速筛除）算法2.1如何利用 X 集列表进行因数分解基本思路就是先把奇数 N 与某个模（奇）数进行模除求余计算，然后讨论用连续的模105 数分别对于 N 进行筛除时，余数的变化规律；根据余数 r 在模数的 X 集中所对应的 X 值http:/- 6 -中 国 科 技 论 文 在 线Xr，来判断出 N 与这个余数或者模数之间是否有公

23、约数。在一般情况下，某个模数能否整除一个整数，取决于余数是否等于零；但是通过余数 r 所对应的 Xr，也可以获知余数或者模数与被除数之间是否互质。这也就是说，如果余数与模数不互质，那么余数和模数也必然都与被除数不互质。我们先从一个简单的例子开始，利用 61 以下奇数的 X 集列表对奇数110 77 进行因数分解。第一步：用 61 对 77 进行模除求余，可以得到 77 = 1*61 + 16，其中系数 k=1，余数r=16，在模数 61 的 X 集列表中余数所对应的 X16是 1，所以 77 与 61 互质。第二步：77 = 1*61 + 16 = 1*61 1*2 + 1*2 + 16 =

24、1*59 + 18，在模数 59 的 X集列表中余数所对应的 X18是 1，说明 77 与 59 互质。115 第三步：77 = 1*59 + 18 = 1*59 1*2 + 1*2 + 18 = 1*57 + 20，在模数 57 的 X集列表中余数所对应的 X20是 1，说明 77 与 57 互质。第四步：77 = 1*57 + 20 = 1*57 1*2 + 1*2 + 20 = 1*55 + 22，虽然余数r0，但是在模数 55 的 X 集列表中余数所对应的 X22是 0，说明被除数 77 与余数 22 和模数 55 之间都不互质，两（三）个数之间必有公约数。因为余数 22 是个偶数，2

25、2 = 2*11，120 所以 77 与 55 之间的公约数只能是奇数 11，11 就是 77 的一个因子。从第四个计算步骤中还可以看出，即使 77 不能被 55 整除，但仍能判断出 77 是个合数并得到它的一个因子，所以每一步的计算并不只是简单的模除求余概念，还可以得到两个整数之间的公约数，这是一种互质求（同）余或者公约求（同）余的概念。互质求余的计算效率当然要比单纯的整除求余高一些。125 上述计算过程的本质，就是把 77 逐一地换算成对于 61、59、57、55 等不同模数的余数表达式；可以发现，当模数逐渐减小时，余数是在按照某种规律有序地增大。除了判断余数是否等于零以外，还可以根据余数

26、所对应的 X 值是否等于零，来判断出 77 与模数或者余数之间是否有公约数。在上述的举例过程中要用到除法或者乘法，只是因为模数 61 与被除数 77 较为接近，130 使得系数 k=1，所以乘除法的计算量可以被忽略。但是当被计算的奇数 N 为极大值时，如果模数接近等于 N1/2，系数 k 也将变得很大，这将使得余数增长的速度很快，会给判断出模数能否整除奇数 N 或者是否与 N 互质带来不便。所以，即使是能够用 X 集列表的方式来对奇数 N 进行因数分解，也只能算是一个新方式而已，这种算法的计算量应该更小些才会有实际的应用价值。这个例子虽然简单，但是却可以为减少计算量带来一种换模求余的新135

27、思路：借助于一个多项式公式，利用算法在上一个计算步骤中已经获得的某些计算结果，只需要有限次（多项式）的加、减法运算，就可以在下一个计算步骤中得到新的余数，根据新的余数所对应的 X 值来进行 N 与新模数之间的互质判断；或者说，无论奇数 N 的数值有多么大，都可以用有限次数的加、减法计算来代替一次复杂的模除求余。2.2 因数分解（快速筛除）算法多项式公式的推导举例140 2.2.1 换模求余多项式公式对于任意一个数值N，用任意一个模数M 2对它进行模除求余后都可有N = k*M2 + R假设N=1927，M 2=61，那么1927 = 31*61 + 36，令k=31， R=36。假定M 3是任

28、意一个整数，M 3=0，1，2， 3，（如果是要求用从小到大的模数对数值Nhttp:/- 7 -中 国 科 技 论 文 在 线145 进行筛除时，还可以有M 3=0，-1，-2， -3，本文暂不对此展开讨论），显然还可以有N = k*M2 + R= k*M2 - k*M3*2 + M3*M2 - M3*M3*2 - M3*M2 + M3*M3*2 + k*M3*2 + R= k*（M 2-M3*2） + M 3*(M2-M3*2) - M3*（M 2-M3*2） + k*M 3*2 + R= (k+M3)(M2-M3*2) - M3*（M 2-M3*2） + k*M 3*2 + R150 这个

29、公式实际上相当于是一种可以换模求余的多项式，当新的模数减小为(M 2-M3*2)时，利用已知的M 2、k和R等数值，能够立即求出新的余数r，r = - M3*（M 2-M3*2） + k*M3*2 + R。例如当M 3=0时，公式中对应的模数就是61，余数为36；而当M 3=2时，对应的新模数则变为(61-2*2) = 57，此时可以不需要使用竖式算法，仅凭着对于一个余数多项式的计算，也能够完成对新模数的模除求余，直接获取到余数46。即155 1927 = 31*61 + 36= (k+M3)(M2-M3*2) - M3*（M 2-M3*2） + k*M 3*2 + R= （31+2）(61-

30、2*2) - 2*(61-2*2) + 31*2*2 + 36= 33*57 114 + 124 + 36= 33*57 + 46160 这个换模求余公式告诉我们，在已知N = k*M2 + R的情况下，如果要用一个新的模数(M2-M3*2)对于整数N进行模除求余时，并不一定需要采用传统的竖式算法，可以根据已知的M 2、k和R，直接转化为对于一个余数多项式的计算。在四则运算中，加减法是进行乘除法运算时的基础；虽然都是建立在以相同方式运算的加减法基础上，但是传统竖式计算的除法方式和利用多项式公式进行模除求余，却又属于两种不同的除法运算架构。如何应用165 则完全取决于它们的用途以及计算效率，当N

31、的数值很大时，采用多项式的架构进行筛除计算效率会很高（参见2.4）。不过，在对于这个换模求余公式的计算过程当中，尚存在着两点不足：从形式上看，当M 3的数值较大时，显然其中还是会含有复杂的乘法运算；从结果上看，根据公式得出的余数r，数值将会随着M 3的增大而单调地增长，最终会远远大于新的模数(M 2-M3*2)，不便于判断出真实的余数。这种不足会使得计算效率受到限制，需要进一170 步研究如何根据这种余数公式，在计算较小的模数时，也可以更加快捷地计算出小于模数的真实余数。2.2.2 改进余数多项式公式的推导举例首先利用61以下的X集列表，通过对一个大一些的奇数1927进行计算举例，然后再总结出

32、能够计算余数的更加便捷的新通项公式。175 第一步：模除求余。先用模数61对1927进行一次模除求余，可有1927 = 31*61 + 36。因为余数r0，而且在61的X集列表中余数所对应的X 36是1，说明1927与61互质。此时，可令k=31，M 2=61，R=36，M 3=1，为下一步的计算做好准备工作。第二步：继续设置参数。180 1927 = 31*61 + 36 = (k+M3)(M2-M3*2) M3*(M2-M3*2) + k*M3*2 + R= （31+1）（61-1*2） - 1*（61-1*2） + 31*1*2 + 36= 32*59 59 + 62 + 36 = 32

33、*59 + 39http:/- 8 -中 国 科 技 论 文 在 线185 因为在新模数（M 2-2）= 59的X集列表中，余数所对应的的X 39是1，所以可知1927与59互质。令M 1=59，M 4=62，在M 2中减去二，使得M 2=59，在M 3中加上一，使得M 3=2。这样，通过在前两个步骤中对于存储单元M 1、M 2、M 3、M 4、k以及R的参数设置，为推导出计算余数的通项公式以及下一步的计算做好了准备工作。190 第三步：推导新的计算余数r的通项公式。因为在上一个步骤结束时，已经在M 2中减去了二，使得M 2=59，在M 3中加上了一，使得M3=2，并且令M 1=59，M 4=

34、62；所以在这个步骤中当M 3=2时，可以使得原来换模求余公式中的(61-2*2) = (M2-2)，2*(61-2*2) = M 3*(M2-2)，那么换模求余多项式可以演变为1927 = 31*61 + 36195 = （31+2）(61-2*2) - 2*(61-2*2) + 31*2*2 + 36= (k+M3)(M2-2) M3*(M2-2) + k*M3*2 + R= （31+2）*(59-2) 2*(59-2) + 31*2*2 + 36= （31+2）*(59-2) （59+59-2*2） + （62+31*2） + 36= (k+M3)(M2-2) (M1+M2-M3*2)

35、+ (M4+k*2) + R200 = (31+2)(59-2) 114 + 124 + 36= 33*57 + 46实际上本步骤中新的模数（M 2-2）= 57，是否能够整除1927或者与它互质，与上述公式中33*57 = (k+M3)(M2-2)的大小无关，并不需要把33*57的确切数值用乘法计算出来，只要把余数计算出来就可以了。205 因为在模数57的X集列表中，余数所对应的X 46是1，所以1927与57互质。这时我们发现，M 3*(M2-2) = 2*(59-2)的乘法计算，可以被(59+59-2*2) = (M1+M2-M3*2)的两次加、减法计算所代替，而k*M 3*2 = 31

36、*2*2的乘法计算，也可以被(62+31*2) = (M4+k*2)的一次加法所代替。这样新的余数计算公式为r = (M1+M2-M3*2) + (M4+k*2) + R210 对于这种多项式公式，无论其中的数值或大或小，都只需要进行五次加、减法计算就可以得出余数。再加上为下一个计算步骤做好准备时另外需要的两次加、减法，把M 2减去二以及在M 3中加上一，算法在每一个计算步骤过程中一共只需要进行七次加、减法的运算。即使当奇数N是一个极大的数值时，每一步的计算过程也只需要有限次数的加、减法即可完成。余数的计算公式是一个不含有复杂乘除法计算的多项式，所需要加、减法的次数因此215 是固定的且与奇数

37、N的大小无关，是这种算法计算效率能够提高的关键所在。虽然在上述公式的计算过程中还有一次变量M 3乘以二的乘法，M 3*2，但是在二进制体系下数字乘以二的运算，只需要在被乘数M 3的最低一位添加一个零即可完成，因此这种乘法的计算量可以被忽略不计。有限次数加、减法的计算复杂度仅为O（n），这要比传统除法的复杂度O（n 2）下降一220 个等级。为了减少在下一个计算步骤中所需要的计算量，可以利用已经进行过的计算工作，此时把动态存储单元M 1中的数值，由59置换成刚才已经得到的计算结果(59+59-2*2) = 114，把M 4中的数值，由62置换成已经得到的计算结果(62+31*2) = 124；并

38、且在M 2中减去二变成57，在M 3中加上一变成3，为下一步的计算做好准备工作。225 第四步：推导出计算余数r的通项公式，可以直接用来计算对于新模数55的余数。http:/- 9 -中 国 科 技 论 文 在 线因为在上一个步骤结束时，又在M 2中减去了二，使得M 2=57，在M 3中加上了一，使得M3=3，所以在这个步骤中当M 3=3时，仍然可以使得原来换模求余公式中的(61-3*2) = (M 2-2)，3*(61-3*2)= M3*(M2-2)，那么1927 = 31*61 + 36230 = （31+3）(61-3*2) - 3*(61-3*2) + 31*3*2 + 36= (k+

39、M3)(M2-2) - M3*（M 2-2） + k*M 3*2 + R= 34*55 - 3*55 + 31*3*2 + 36= 34*55 165 + 186 + 36= 34*55 + 57235 又因为在上一个计算步骤结束时已经置换了M 1和M 4中的数值，令M 1 = (59+59-4) = 114，M 4 = (62+62) = 124，如果直接应用新的余数计算公式，同样可以有1927 = 31*61 + 36= (k+M3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R= (31+3)(57-2) - （114+57-3*2） + （124+31*2） +

40、36240 = 34*55 165 + 186 + 36= 34*55 + 57这时我们可以发现，M 3*（M 2-2） = 3*55的乘法计算，仍然可以被（114+57-3*2） = (M1+M2-M3*2)的两次加、减法计算所代替，而k*M 3*2 = 31*3*2的乘法计算，也仍然可以被(124+31*2) = (M4+k*2)的一次加法所代替。换句话说，无论进行过的计算步骤次数M 3等于245 几，每一个步骤中新的模数(M 2-2)等于几，系数k有多么大，通过置换（迭代）M 1和M 4中数值的方式，使得上一个计算步骤进行过的计算工作，在这一个步骤中可以继续被利用，对于公式中余数部分的计

41、算仍然只需要进行五次加、减法运算即可完成。这就是为什么利用在上一个计算步骤中已经获得的计算结果，(59+59-4) = 114，(62+62) = 124，再把它们分别代入到M 1和M 4中去，并且有规律地修改了M 2和M 3的数值以后，仍然需要同样有限次数250 （多项式）的加、减法运算，就可以在下一个步骤中得到新余数的推导过程。因为余数57大于模数（M 2-2）= 55，需要进行一次减法计算，57-（M 2-2）= 57-55 = 2，直到0255时为止，方能获得真实的余数r=2；在模数55的X集列表中，真实余数所对应的X 2是1，所以1927与55互质。此时把存储单元M 1置换成刚才已经

42、得到的计算结果(114+57-6) = 165，在M 2中减去二255 变成55，在M 3中加上一变成4，把M 4置换成刚才已经得到的计算结果(124+62) = 186，为下一步的计算做好准备工作。上述的讨论过程也就是说，只要是在前一个步骤中有规律地修改了M 1、M 2、M 3和M 4的数值以后，就可以获得一个新的余数计算公式；不再需要进行复杂的乘除法，仅仅通过有限次数的加减法计算，同样可以完成用不断递减的新模数（M 2-2）对于整数1927的模除求余260 计算。即1927 = 31*61 + 36= (k+M3)(M2-2) - M3*（M 2-2） + k*M 3*2 + R= (k+

43、M3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R更严格地讲，上述过程可以用数学归纳法来进行严格的证明，并且得到在每一个计算265 步骤中始终会有(M 1+M2-M3*2) 0（mod（M 2-2），且(M 4+k*2) 0（mod（2*k）。http:/- 10 -中 国 科 技 论 文 在 线第五步：直接利用新的余数计算公式计算1927对于模数53的余数。1927 = (k+M3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R= (k+M3)(M2-2) (165+55-4*2) + （186+31*2） + 36270 = 35*53 + 7

44、2因为余数72大于模数（M 2-2）= 53，可有72-（M 2-2）= 72-53 = 19，使得01953；在模数53的X集列表中，真实余数所对应的X 19是1，所以1927与53互质。此时把存储单元M 1置换成刚才已经得到的计算结果(165+55-4*2) = 212，在M 2中减去二变成53，在M 3中加上一变成5，把M 4置换成刚才已经得到的计算结果（186+31*2） = 275 248，为下一步的计算做好准备工作。第六步：直接利用公式计算1927对于模数51的余数。1927 = (k+M3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R= (k+M3)(M2

45、-2) (212+53-5*2) + （248+31*2） + 36= 36*51 + 91280 因为余数91大于模数（M 2-2）= 51，可有91-（M 2-2）= 91-51 = 40，04051；在模数51的X集列表中，真实余数所对应的X 40是1，所以1927与51互质。此时把存储单元M 1置换成刚才已经得到的计算结果(212+53-5*2) = 255，在M 2中减去二变成51，在M 3中加上一变成6，把M 4置换成刚才已经得到的计算结果（248+31*2） = 310，为下一步的计算做好准备工作。285 第七步：直接利用公式计算1927对于模数49的余数。1927 = (k+M

46、3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R= (k+M3)(M2-2) (255+51-6*2) + （310+31*2） + 36= 37*49 + 114因为余数114大于模数（M 2-2）= 49，可有114-（M 2-2） = 114-49 = 65，因为65仍然290 大于49，继续65-49 = 16，使得01649；在模数49的X集列表中，真实余数所对应的X 16是1，所以1927与49互质。此时把存储单元M 1置换成刚才已经得到的计算结果(255+51-6*2) = 294，在M 2中减去二变成49，在M 3中加上一变成7，把M 4置换成刚才已经得

47、到的计算结果（310+31*2） = 372，为下一步的计算做好准备工作。295 第八步：直接利用公式计算1927对于模数47的余数。1927 = (k+M3)(M2-2) (M1+M2-M3*2) + (M4+k*2) + R= (k+M3)(M2-2) (294+49-7*2) + （372+31*2） + 36= 38*47 + 141因为余数141大于模数（M 2-2）= 47，可有141-（M 2-2） = 114-47 = 94，仍然大于300 47，继续94-47 = 47，因为47等于模数，可以继续47-47 = 0，直到0047时为止；因为真实余数r=0，或者因为X 47是0，所以可知47就是1927的一个因子。一共经过了八个步骤的计算，当M 3=7，模数为（61-7*2）= 47时，可以得到合数1927的一个因子。除去在第一个步骤中用竖式算法进行过一次模除求余以外，其余的每一个步骤中大约需要七次（或略多）加、减法。如果再继续进行三个计算步骤，还可以得到1927305 的另外一个因子41。这样就可以获得一种新的余数计算公式，r = (M1+M2-M3*2) + (M4+k*2) + R。虽然这个与原有换模求余公式一脉相承的新公式，可以解决原有公式中含有复杂乘法运算的不