?x1??b1??a11a12...an?1?x??b??a?a...a2122n22???2???A?X?B? ?M??M???O??????aa...axn1n2nn?? ?n? ?bn?
例如方程组
4x?3y?9(mod13?43??x??9??52??y???7?(mod13)5x?2y?7(mod可以将其写为13)??????
更进一步地，我们学习一种形如
AX?B(modm)的同余方程组的求解方法。这种方法的原理是，基于求出矩阵A使得AA?I,即A是矩阵A的逆。其中，I是单位矩阵。 定义 设A和A是n?n阶矩阵，且AA?AA?I(modm)，其中
?10...?01...? I??MO??00L?0?0?A?是n阶矩阵，则称是A模m的一个?1?逆。 例如求解
?22??12?模7的逆，因为我们有 ???2?1 ?并且
2??16??814?????3???21?????7?8??10?(mod7)?0?1，
?1?3 ?6??22??814?????1?2?7?8?1???????10?(mod7)?0?1
?16??22??31??12??是??模7的逆。 所以我们得到??ab?A??cd???是整数矩阵， 定理2.17 设
12
且??detA?ad?bc与正整数m互为素数。则矩阵是A模m的逆，其中?是?模m的逆。
?35?A???47??,因为14是detA?1模13的逆，所以有 例 设
'?7?5??7??5A?14???(mod13)????43???43?
例 考虑同余方程组
6x1?2x2?6x3?3(mod7)2x1?x3?4(mod7) 2x1?4x2?2x3?1(mod7) 这等价于矩阵同余方程
?6?1??2 ??25?20??12我们可以证明出?3??4(mod7)0??41?
6??626??105?1????3??是??242??模7的一个逆。因此，我们有 26??x1????x???5??2???2????x3???3?3?x1??256????2??4?x???201???4??7????0(mod7)2???????????x??123??1???????1?4????0 ?3??
根据本节内容，有很多解线性方程组的方法修改后可以用于求解同余方程组。例
如，高斯消元法可以修改用于求解同余方程组，其中除法变为乘以模m的逆。而且，有类似于克莱姆法则的求解方法。 2.6 利用波拉德方法分解整数
本节描述的分解方法是源于同余的基础。它由波拉德在1974年提出的。波拉德称之为蒙特卡洛方法，因为它依赖于生成貌似随机挑选的整数；现在成为波拉德 方法。
为什么称此方法为波拉德方法？我们现在借助下面的图形解释一下为什么这样命名。
13
? x 2 ? 26
x1?5
? x0?2
x3?677?95(mod97) ?
? x4?7474?5(mod97)
xi2?1xx0i?1此图说明了数列x的周期特性。其中的值为2，与模97同余，i
的值大于等于1。这个序列周期性出现之前的部分为字母?的尾部，周期性的部分为?的环部。
设n是一个大合数，p是它的最小素因子。 我们的目标是选取整数
x1,x2,...,xs，使得它们有不同的模n最小非负剩余，但它
p们模p的最小非负剩余不是全部不同的。使用一些概率公式，在s与相比较
x,x,...,xs大，而与n相比较小，数字12是随机地选取时，这是可能发生的。一旦
找到整数xi和
xj0?i?j?sx?xj(modp)x?xjm(od)，，满足i，且in，则
(xi?x,j)n是n的非平凡因子，这是因为p整除几里得算法迅速求出
xi?xj，但n不整除
xi?xj。我们可以用欧
(xi?xj,n)。
xj我们用下面的方法寻找这样的整数xi和
：第一步，随机选取初始值即种子
值x0，f(x)是次数大于1的整系数多项式，紧接着我们用递归定义
x?f(kx)(modn)0?xk?1?n，
求解xk，其中k?1,2,...。多项式f(x)的选取应该使得有很高的概率在出现重复
14
2之前生成适当多的整数xi。而根据经验，我们通常选取多项式f(x)等于x?1。
2x0?2f(x)?x?1，那么我们有 n?8051例 设，，
,3?67x74,? x1?5,x2?26x值得注意的是，由xk的递归定义，如果
其中d是一个正整数，则
74x74,5?2x68?3 9,871xi?xj(mod)
xi?1?f(xi)?f(xj)?xj?1(modd)
于是，如果，则序列xk变为模d周期的，其周期整除j?i；即在q与r同余在模
j?i的条件下，并且，q与r的值均大于等于i，xq与xr模d同余。因此，如果s是不小于i的j-i的最小倍数，那么xs与x2s模d同余。因此，为寻找n的一个因子，我们要求
x2k?xk与n的最大公因子，k?1,2,3,....。当找到k使得
1?(x2k?xk,n)?n时，我们就得到了n的一个因子。根据之前的观察，我们很可
p能找到一个接近于的整数k。
关于波拉德?方法在实际生活中的应用，我们经常选用多项式f(x)使其等于
x2?1来生成整数序列x0,x1,...,xk,...。并且，经常选用初始值为2的x0。这样的
选取方法在分解过程中，使得选取的多项式和初始值所生成的序列的行为很像随机序列。
经过试验得出，如果想要分解具有相当大的素因子的整数，波拉德?方法是实用的。在实际应用中，我们如果想要分解大的整数时，首先用小素数试除，例如小于104的素数；其次，我们用波拉德?方法来找出中等大小的（例如不超过1015）的素因子。一般的，我们在采用此方法失败之后，我们才采用真正强力的方法，比如二次筛法或者椭圆曲线方法，在此不予介绍。
15
