大数据

当前位置:首页 > 大数据

《算法导论》第三十一章 续3

31.4 求解模线性方程

现在来考虑求解下列方程的问题:

QQ截图20220624113754.jpg

其中a>0,n>0。这个问题有若干种应用。例如,在31.7节中,我们将它用在RSA公钥加密系统中,作为寻找密钥过程的一部分。假设已知a,b和n,希望找出所有满足式(31.25)的对模n的x值。这个方程可能没有解,也可能有一个或多个这样的解。

令<a>表示由a生成的zn的子群。由于<a>={a(x):x>0}= {ax mod n:x>0},所以当且仅当[b]∈<a>时,方程(31. 25)有一个解。拉格朗日定理(定理31. 15)告诉我们,|<a>| 必定是n的约数。下列定理准确地刻画了<a>的特性。

定理31.20  对任意正整数a和n,如果d=gcd(a, n),则在Zn中,

QQ截图20220624114103.jpg

因此,

QQ截图20220624114112.jpg

证明  首先证明d∈<a>。注意到EXTENDED-EUCLID(a, n)可生成整数x'和y',使得ax'+ny'=d。因此ax'=d(mod n),所以d∈<a>。换句话说,d是Zn中a的一个倍数。

由于d∈<a>,所以d的所有倍数均属于<a>,这是因为a的倍数的倍数其本身仍然是a的倍数。所以,<a>包含了集合{0,d,2d,...,((n/d)- 1)d}中的每-个元素。也就是说,<d>QQ截图20220624102026.jpg<a>。

现在来证明<a>QQ截图20220624102026.jpg<d>。如果m∈<a>,则对某个整数x,有m=ax mod n,所以对某个整数y,有m=ax+ny。然而,d|a且d|n,所以由式(31.4)有d|m。因此,m∈<d>。

由以上这些结论,得到<a>=<d>。注意到在0和n-1之间(包括0和n-1)恰有n/d个d的倍数,这说明了| <a>|=n/d。

推论31.21  当且仅当d|b时,方程ax=b(mod n)对于未知量x有解,这里d=gcd(a, n)。

证明  当且仅当[b]∈<a>时,方程ax=b(mod n)有解。由定理31.20,这等同于

QQ截图20220627101000.jpg

如果0≤b<n,则当且仅当d|b时,b∈<a>成立,这是由于<a>的成员恰恰是d的倍数。如果b<0或b≥n,则观察到d|b当且仅当d |(b mod n)时成立,可得推论,这是由于b和b modn可以由n的倍数区分开,而其本身是d的倍数。

推论31.22  方程 ax=b(mod n)或者对模n有d个不同的解,或者无解,这里d=gcd(a, n)。

证明  如果 ax=b(mod n)有一个解,则b∈<a>。根据定理31.17,ord(a)= |<a>|,而且推论31. 18和定理31.20意味着,对i=0,1,...,n-1,b序列ai mod n是周期性的,其周期为|<a>|=n/d。如果b∈<a>,则对i=0,1,...,n-1,b在序列ai mod n中恰好出现d次,因为当i从0增加到n-1时,长度为n/d的一组值<a>恰好重复了d次,这d个满足ax modn=b的位置的下标x,就是方程ax=b(mod n)的解。

定理31.23  令d=gcd(a, n),假设对某些整数x'和y',有d=ax' +ny'(例如EXTENDED-EUCLID所计算出的结果)。如果d|b,则方程ax=b(mod n)有一个解的值为x0,这里

QQ截图20220627101813.jpg

证明  有

QQ截图20220627101853.jpg

因此x0是ax=b(mod n)的一个解。

定理31.24  假设方程ax=b(mod n)有解(即d|b,这里d= gcd(a,n)), 且x0是该方程的任意一个解。因此,该方程对模n恰有d个不同的解,分别为xi=x0十i(n/d),这里i=0,1,...,d-1。

证明  因为 n/d>0并且对于i=0,1,..., d-1,有0≤i(n/d)<n,所以对模n,值x0

x1,...,xd-1都是不相同的。因为x0是ax=b(mod n)的一个解,故有ax0 mod n=b(mod n)。因此,对i=0,1,...,d-1,有

QQ截图20220627102238.jpg

又因为axi=b(modn),故xi也是一个解。根据推论31.22可知,方程ax=b(mod n)恰有d个解,因此x0,x1,...,xd-1必定是方程的全部解。

现在已经为求解方程ax=b(mod n)完成了数学上的必要准备,下列算法可输出该方程的所有解。输入a和n为任意正整数,b为任意整数。

QQ截图20220627102511.jpg

作为一个说明该过程中操作的例子,考察方程14x=30(mod 100)(这里,a=14,b= 30,n=100)。在第1行中调用EXTENDED-EUCLID,得到(d, x',y')=(2,- 7, 1)。因为2|30,所以执行第3~5行。在第3行,计算出x0=(- 7)(15) mod100=95。第4~5行的循环输出这两个解95和45。

过程MODULAR-LINEAR-EQUATION-SOLVER的工作方式如下。第1行计算出d=gcd(a, n)及两个值x'和y',满足d'=ax'+ny',同时表明x'是方程ax' =d(mod n)的一个解。如果d不能整除b,则由推论31.21可知,方程ax=b(mod n)没有解。第2行检查是否有d|b;如果没有,则第6行报告方程无解。否则,第3行将根据定理31.23,计算出方程ax=b(mod n)的一个解x0。已知一个解后,定理31.24说明,通过加上对模n等于(n/d)的倍数,可以得到其他d-1个解。第4~5行的for 循环输出所有d个解,从x0开始,每两个解之间模n相差(n/d)。

MODULAR-LINEAR-EQUATION-SOLVER执行O(lgn+ gcd(a, n)) 次算术运算,因为EXTENDED-EUCLID需要执行O(lgn)次算术运算,并且第4~5行for循环中的每次迭代均要执行常数次算术运算。

定理31.24的下述推论给出了几个非常有趣的特例。

推论31.25  对任意 n>1,如果gcd(a, n)=1,则方程ax=b(mod n)对模n有唯一解。

如果b=1,则要求的x是a对模n的乘法逆元,这是一种常见的重要有趣情形。

推论31.26  对任意n>1,如果gcd(a, n)=1,那么方程ax=1(modn)对模n有唯一解;否则方程无解。

由于推论31.26,在a和n互质时,可以用记号a-1 modn来表示a对模n的乘法逆元。如果gcd(a,n)=1,则方程ax=1 (mod n)的唯一解就是EXTENDED-EUCLID所返回的整数x,因为方程

gcd(a,n) = 1= ax+ ny

意味着ax=1(mod n)。因此,运用EXTENDED-EUCLID可以高效地计算出a-1 mod n。


练习

31.4-1  找出方程 35x=10(mod 50)的所有解。

31.4-2  证明:只要gcd(a,n)=1,方程ax=ay( mod n)就意味着x=y(modn)。通过一个gcd(a, n)>1情况下的反例,证明条件gcd(a, n)=1是必要的。

31.4-3  考察下列对过程MODULAR-LINEAR-EQUATION-SOLVER的第3行的修改:3 x0=x'(b/d) mod (n/d)能否正确运行?解释能或者不能的原因。

*31.4-4 令P为一个素数,且f(x)=f0+f1x+...+f1xt(mod p)是一个t次多项式,其系数fi是从Zp得到的。如f(a)=0(mod p),则将a∈Zp称为f的零元。证明:如果a是f的一个零元,则对某个t-1次的多项式g(x),有f(x)=(x- a)g(x)(mod p)。通过对t进行归纳来证明:如果p是素数,t次多项式f(x)对模p至多有t个不同的零元。


31.5 中国余数定理

大约在公元100年,中国数学家孙子解决了这个问题:找出所有整数x,它们被3,5和7除时,余数分别为2,3和2。一个这样的解为x=23,所有的解是形如23+ 105k(k为任意整数)的整数。“中国余数定理”提出,对一组两两互质的模数(如3, 5和7)来说,其取模运算的方程组与对其积(如105)取模运算的方程之间存在着一种对应关系。

中国余数定理有两个主要应用。设整数n因式分解为n=n1n2...nk,其中因子ni两两互质。首先,中国余数定理是一个描述性的“结构定理”,它用等同于笛卡儿积Zn1 XZn2X...XZnk的结构描述了Zn的结构,其中第i个分量定义了对模ni的分量方式加法与乘法运算。其次,这种描述有助于设计出高效的算法,因为处理Zni系统中的每个系统可能比处理模n运算效率更高(从位操作次数看)。

定理31.27(中国余数定理)令 n=n1n2...nk,其中因子ni两两互质。考虑以下对应关系:

QQ截图20220627104426.jpg

这里a∈Zn,ai∈Zni,而且对i=1, 2, ..., k,

QQ截图20220627104457.jpg


因此,映射(31. 27)是一个在Zn与笛卡儿积Zn1 XZn2 X...XZnk之间的一一对应(双射)。通过在合适的系统中对每个坐标位置独立地执行操作,对Zn中元素所执行的运算可以等价地作用于对应的k元组。也就是说,如果

QQ截图20220627104728.jpg

那么

QQ截图20220627104749.jpg

证明  两种表示之间的变换是相当 直接的。从a转换为(a1,a2,...,ak)十分简单,仅需执行k次模运算。

从输入(a,a, ., an)算出a要复杂一点。从定义mi=n/ni(对于i=1, 2, ..., k)开始,于是mi是除了ni以外的所有nj的乘积:mi=n1n2...ni-1ni+1...k 。接着,对i=1, 2, ...k,定义

QQ截图20220627105610.jpg

等式(31.31)总是良定义的:因为mi和ni互质(根据定理31. 6),推论31.26保证mi-1mod ni存在。最后,作为a1,a2,...,ak的函数,计算a的方式如下:

QQ截图20220627105906.jpg


现在证明对i=1,2,...,k,等式(31. 32)能保证a=ai(mod ni)。注意,如果j≠i,则mj=0(mod nj),这意味着cj=mj=0(mod ni)。而且注意到,由等式(31.31)知,ci=1(mod n)。因此得到这个既中看又中用的对应关系

QQ截图20220627110211.jpg

这是一个除了在第i个坐标上为1外其余坐标均为0的向量。因此,在某种意义上,ci构成了这种表示的“基”。所以对每个i,有

QQ截图20220627110332.jpg

这正是我们希望证明的:对i=1, 2,...,k,用从ai计算a的方法得到了满足约束条件a=ai(mod ni)的结果a。由于能进行双向变换,所以这种对应关系是一一对应。最后,由于对任何x和i=1, 2,...,k,有x mod ni=(x mod n) mod ni,所以根据练习31.1-7, 可以直接推出式(31.28)~(31.30)成立。

下面的推论将在本章的后面用到。

推论31.28  如果 n1,n2,...,nk两两互质,且n=n1n2...nk,则对任意整数a1,a2,...,ak,关于未知量x的联立方程组

QQ截图20220627110702.jpg

对模n有唯一解。

推论31.29  如果n1, n2,...,nk两两互质,n=n1n2...nk,则对所有整数x和a,

QQ截图20220627111418.jpg

(其中i=1,2,...,k)当且仅当

QQ截图20220627111517.jpg

作为中国余数定理应用的例子,假设已给出两个方程:

QQ截图20220627111550.jpg

那么a1=2, n1=m2=5, a2=3,且n2=m1=3,而且由于n=n1n2= 65,所以我们希望算出a mod 65。因为13-1 =2(mod 5)和5-1=8(mod 13),所以有

微信截图_20220627111831.png

以及

QQ截图20220627111853.jpg

图31-3是对模65的中国余数定理的说明。

QQ截图20220627111920.jpg

图31-3  对于n1=5和 n2=13中国余数定理的一个说明。对这个例子,c1=26,c2=40。在第i行第j列显示的是对模65的a的值,使得a mod 5=i和a mod 13=j。注意,第0行第0列的值为0。类似地,第4行第12列包含64(等价于一1)。因为c1=26,往下移动一行让a增加26。类似地,c2=40 表示往右移动一列,让a增加40。让a增加1对应于沿着对角线往右下移动,从底端折返到顶端,以及从右端折返到左端

因此,如果要执行模n运算,则既可以直接对模n进行计算,为了方便,也可以分别对模n变换表示后的模n;进行计算。这两种计算是完全等价的。


练习

31.5-1  找出所有解,使方程x=4(mod 5)和x=5(mod 11)同时成立。

31.5-2  找出被9,8, 7除时,余数分别为1, 2, 3的所有整数x。

31.5-3  论证:在定理31. 27的定义下,如果gcd(a, n)=1,则

(a-1 mod n)→((a1-1 mod n),(a2-1 mod n2),...,(ak-1 mod n))

31.5-4  在定理 31. 27的定义下,证明:对于任意的多项式f,方程f(x)=0(mod n)的根的个数等于f(x)=0(mod n1), f(x)=0(mod n2),...。f(x)=0(mod n4)中每个方程根的个数的积。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~