附录：数学基础

1、四川大学1/72上周讲到应用密码学应用密码学(数论、有限域和计算复杂性基础数论、有限域和计算复杂性基础 )四川大学电子信息学院2/72一、数论基础一、数论基础整数具有以下性质：（整数具有以下性质：（1）b | a，c | b，则，则c | a（2）a | 1，则，则a=1（3）对任一）对任一b（b0）, b 0（4） b | g， b | h，则对任意整数，则对任意整数m, n有有b | (mg+nh)定理定理1 1：任给两个整数任给两个整数a，b，其中，其中 b0，则存在两个唯一的整数，则存在两个唯一的整数q和和r，使得使得 a = qb + r ， 0 r b 成立。成立。余数，也叫做非负

2、最小剩余余数，也叫做非负最小剩余不完全商不完全商1.1.素数与互为素数素数与互为素数 整除与因子的概念：整除与因子的概念： 任给两个整数任给两个整数a，b，其中，其中 b0，如果存在一个整数，如果存在一个整数q使得等式使得等式 a = q b 成立，此时称成立，此时称b整除整除a，记为，记为b | a，并称，并称b为为a的的因子因子，把，把a为为b的的倍数倍数。 否则否则b不整除不整除a，记为，记为 b a四川大学电子信息学院3/72 最大公因数与辗转相除法最大公因数与辗转相除法定义：定义：设设a1，a2，an是是n个不全为零的整数，若整数个不全为零的整数，若整数d（通常考虑（通常考虑d0）是

3、它们之中每一个的因数是它们之中每一个的因数(子子)，那么，那么d 就叫做设就叫做设a1,a2,an的一个公因数。的一个公因数。 公因数只有有限个，其中最大的一个公因数叫最大公因数公因数只有有限个，其中最大的一个公因数叫最大公因数(子子) 。 记为记为： （ a1,a2,an ）， 若（若（ a1,a2,an ）=1，则称，则称a1，a2，an互素。互素。 对于整数对于整数a, b，其最大公因数等价的定义形式是：，其最大公因数等价的定义形式是： （a, b）maxk， k | a且且k | b注意：注意： （a, b）= （a, b）= （a, b）= （|a|，|b|）定理定理2 2：设设a,

4、 b, c是任意不全为零的整数，且是任意不全为零的整数，且 a = qb + c ；其中其中q是整数，是整数， 则有则有 （ a, b ）=（ b, c ）。 即被除数和除数的最大公因子与除数和余数最大公因子相同。即被除数和除数的最大公因子与除数和余数最大公因子相同。a 除以b, 商q余c例：(18, 12) = ( 12, 6) = (6, 0) = 6 (11, 10) = ( 10, 1) = (1, 0) = 1四川大学电子信息学院4/72辗转相除法辗转相除法: （Euclid算法，欧几里德算法）任给两个整数任给两个整数a，b，设，设 a b0，由代余数的除法，有下列等式：，由代余数的

5、除法，有下列等式： a = bq1 + r1，0 r1 b， b = r1 q2 + r2，0 r2 r1 ， （1） rn-2 = rn-1 qn + rn ，0 r1 r2 r3 , 故经有限次代余数除法后，总可以得到故经有限次代余数除法后，总可以得到一个余数是零，即上式中一个余数是零，即上式中rn+1 = 0。定理定理3 3：任给整数任给整数 a b 0 ，则（，则（a, b）就是（）就是（1）中最后一个不等于）中最后一个不等于零的余数，即（零的余数，即（a, b）= rn （举例）（举例）定理定理4 4：任给整数任给整数 a b 0 ，则存在两个整数，则存在两个整数 m, n 使得使得

6、 （a, b）= m a + n b 由上式，显然有推论：由上式，显然有推论：a 和和 b 的公因数是的公因数是(a, b)的因数的因数。转一次不定方程5/72 288 = 1581 + 130， 158 = 130 1 + 28， 130 = 28 4 + 18， 28 = 18 1 + 10， 18 = 10 1 + 8， 10 = 8 1 + 2， 8 = 2 4 + 0 因此，最大公因数因此，最大公因数 (a, b) = 2 再进行逆向迭代，再进行逆向迭代，2 = 108 1 (代代2) = 10(1810) 1 (代代8) = 102 18 = (2818 1)2 18 (代代10)

7、 = 282183 = 282(13028 4 )3 (代代18) = 28141303 = (158130 1 )14 1303 (代代28) = 1581413017 = 15814(2881581 )17 (代代130) = 1583128817 = 17 288 + 31158所以所以 m = 17, n=31例：用辗转相除法求，例：用辗转相除法求，a=288，b=158的最大公因数和的最大公因数和m, n，使，使ma + nb=(a, b)四川大学电子信息学院6/72最小公倍数：最小公倍数：)(:00bababababa，的最小公倍数，有：， 素数素数(质数质数)的概念的概念： 大于

8、大于1的整数的整数 被称为被称为素数素数是指是指 p 的因子仅有的因子仅有1, 1, p, p。定义：若（定义：若（a，b）=1，则，则a与与b互素。互素。引理引理1 1：若若p是素数，是素数，a是任意整数，则有是任意整数，则有 p | a 或或 (p, a) = 1 即素数与一个数要么互素，要么可整除该数。即素数与一个数要么互素，要么可整除该数。引理引理2 2：若若p是素数，是素数， p | ab ，则，则 p | a 或或 p | b 四川大学电子信息学院7/72定理定理5 5：任一整数任一整数 a ( a 1)都能唯一地分解为以下形式：都能唯一地分解为以下形式：5325322212021

9、03212121如：是素数，其中，)k,.,i (p.ppp.ppaikkk （整数的惟一分解性定理）（整数的惟一分解性定理）推论推论1 1：若若d | a，则，则d一定有形一定有形式：式：kkxkxxxxpppdk0.0;.112121这里如整数如整数120120的所有因子可表示为：的所有因子可表示为：16)120(16224120D记为：所有可能的因数个数为) 1).(1)(1()(,21kaDaZa的因数个数：则推广到一般：转一次不定方程转一次不定方程101030532321321xxxxxx；，且四川大学电子信息学院8/72 有有 5050个队员，分别编号为个队员，分别编号为1 1、2

10、 2、5050；另有；另有5050盏电灯盏电灯（为拉线式开关），分别编号为（为拉线式开关），分别编号为(1)(1)、(2)(2)、(50)(50)。规则：规则：若某灯的编号正好是某队员编号的倍数，则该队员就若某灯的编号正好是某队员编号的倍数，则该队员就拉该灯一次。拉该灯一次。 如如1 1号队员将对号队员将对5050个灯都拉一次；个灯都拉一次； 3 3号队员将拉号队员将拉(3)(3)、(6)(6)、(9)(9)、(45)(45)、(48)(48)号灯各一次；号灯各一次； 50 50号队员将只拉号队员将只拉(50)(50)号灯一次；号灯一次； 问题：问题：最后有哪几盏灯是亮的最后有哪几盏灯是亮的?

11、 ?（设初始为全熄）。（设初始为全熄）。结果：共结果：共7 7盏灯是亮的。即：盏灯是亮的。即： (1)(1)，(4)(4)，(9)(9)，(16)(16)，(25)(25)，(36)(36)，(49)(49)一个趣味问题一个趣味问题推论推论2 2：a是一个完全平方数是一个完全平方数 D(D(a) )是奇数。是奇数。“拉灯拉灯”问题：问题：定理定理5 5四川大学电子信息学院9/722.2.一次不定方程一次不定方程二元一次不定方程是指：二元一次不定方程是指： a1x + a2 y = n （1）其中其中a1，a2，n是给定的整数，是给定的整数， a1，a2 0定理定理6 6：方程方程 (1) 有解

12、的充分必要条件是：有解的充分必要条件是： ( a1，a2 ) | n由前面定理由前面定理4，当，当 (a1，a2 ) =1，存在整数，存在整数s，t 使：使： s a1 + t a2= (a1，a2 ) =1两边乘以两边乘以n， s na1 + tn a2= n与与(1)式比较，有解：式比较，有解： x0 = s n ， y0 = t n ，充分条件得证。，充分条件得证。此为方程此为方程(1)的一组特解，而全部解可由下面定理给出：的一组特解，而全部解可由下面定理给出：定理定理7 7：(a1，a2 ) =1，则方程，则方程 (1) 一定有解，且全部解（通解）为：一定有解，且全部解（通解）为：1)

13、b ,a(b)b ,a(aZb ,a，有可利用性质：不失一般性对转同余方程（组）转同余方程（组）x = x0 + a2 k y = y0 a1 k其中，其中，k Z， x0, y0是是方程方程 (1) 的一组特解。（证明略）的一组特解。（证明略）证明：证明： 式式 (1) 有解有解 (a1，a2 ) | n显然成立，必要条件得证。显然成立，必要条件得证。当当(a1，a2 ) | n，不失一般性不失一般性，可假设，可假设 (a1，a2 ) =1, a1 0，a2 0 四川大学电子信息学院10/72 得得 s = 2，t = 3 所以所求特解为：所以所求特解为： x0 =224=48， y0 =

14、324 = 72 所以，方程的完全解为：所以，方程的完全解为： x = x0 +a2k = 48 +7k y = y0a1k = 7210k 其中其中 k Z 【例例】 解方程解方程 10 x + 7y = 24解：此例，解：此例， a1=10， a2=7， n=24， 因为因为(10, 7) = 1 所以方程有解。所以方程有解。由辗转相除法计算满足下式的由辗转相除法计算满足下式的s和和t： 10s + 7t = 1 ，有，有10 =71+3 7 =32+1 1= 732 = 7(1071) 2 = 10(2) + 73四川大学电子信息学院11/723.3.模运算与同余式模运算与同余式定义：设

15、定义：设 n 是一正整数，是一正整数，a是整数，如果用是整数，如果用n除除a，得商为，得商为q，余数为，余数为r， 则则 a = qn + r ，0 r n， q = a/n 其中，其中， x 为小于或等于为小于或等于x的最大整数。的最大整数。 用用a mod n 表示余数表示余数 r，则，则 a = a/n n + a mod n 如果如果 (a mod n ) = (b mod n ) ，则称两整数，则称两整数 a 和和 b 模模n 同同余，记为：余，记为： a b mod n 称与称与 a 模模 n 同余的数的全体为同余的数的全体为 a 的的同余类同余类，记为，记为a，并称并称 a 为该

16、同余类的表示元素。为该同余类的表示元素。（显然，同余类中的每一元素都可作为这个同余类的表示元素）（显然，同余类中的每一元素都可作为这个同余类的表示元素） 如果如果 a 0 mod n ，n|a四川大学电子信息学院12/723.3.模运算与同余式（续）模运算与同余式（续） (2) 同余的性质：同余的性质：如果如果(a mod n ) = (b mod n ) ，则，则a b mod n； (定义定义)自反性：自反性： a a mod n； 对称性：对称性： 如果如果a b mod n，则则b a mod n； 传递性：传递性： 如果如果则则a b mod n，b c mod n，则则a c mo

17、d n； 四川大学电子信息学院13/72如果如果 n|(ab)，则则a b mod n ；证明：证明：必要性：必要性：设设 a b mod n，则有，则有 a= k1n + r，b= k2n + r，0rn故故 a b = n ( k1k2 ) 显然有显然有， n|(a-b) 充分性：充分性：设设 a= k1n + r1， b= k2n + r2， 0r1n，0r2n 有有 a b = n(k1k2)+ r1r2， 如果有如果有，n|(a b)，必有必有 n|(r1r2) ，而而 |r1r2| n 所以所以 r1 = r2， 即即 a b mod n a, b对模对模n同余的充要条件：同余的充

18、要条件：返回模运算性质返回模运算性质四川大学电子信息学院14/72(3) 模运算及性质：模运算及性质：模运算性质模运算性质：模n下的算术运算性质 下面设 a, b, c, d 都是整数，而 n 为正整数，有模运算性质： (ab)mod n = (a mod n)(b mod n ) mod n 证明： 设 a mod n = ra ， b mod n = rb ，有： a =jn + ra ， b = kn + rb ，j，k分别为两个整数。有： (ab)mod n =(jn + ra kn rb ) mod n = (rarb + jnkn) mod n = (rarb) mod n = (

19、a mod n)(b mod n ) mod n (ab)mod n = (a mod n)(b mod n ) mod n 概念：概念：求余数运算求余数运算 a mod n 将整数将整数 a 映射到映射到非负整数集合非负整数集合Zn= 0, 1, , n-1，称为求余运算，在这个集合上的运算称为模运算。，称为求余运算，在这个集合上的运算称为模运算。四川大学电子信息学院15/72交换律交换律: (a * b) mod n = (b * a) mod n ; “ * ”可为可为 +、结合律结合律: a * ( b * c) mod n = ( a * b ) * c mod n ; “ * ”可

20、为可为 +、分配律分配律: a ( b + c) mod n = a b + a c) mod n 恒等恒等: ( 0 + a ) mod n = ( 1a ) mod n = a mod n 加法逆元加法逆元: 对每一个对每一个w Zn ，存在一个存在一个u，使得，使得 w + u0 mod n 记为，记为，u = w，显然，显然: 在模在模n下，下， w n w满足交换律、结合律、分配律、恒等、加法逆元。满足交换律、结合律、分配律、恒等、加法逆元。（证明略）模运算性质模运算性质(续续)四川大学电子信息学院16/72如果如果 a b mod n c d mod n 则有则有 (1) (ac)

21、 (bd) mod n ；特例：特例： ac bc mod n 更一般式：更一般式： (ax cy) (bx dy) mod n x, y Z (2) ac bd mod n ；特例：特例： ac bc mod n (3) f (a) f (b) mod n 其中其中f (x)为任给定的一个整系数多项式为任给定的一个整系数多项式证证(1)：因为：因为n|(ab)， n|(cd)，故，故 n| x(ab)y (cd ) 即，即，n| (axc y) ( bxdy ) 即即(ax cy) (bx dy) mod n 证证(2)：由：由 n| c(ab) b (cd ) 即即n| ac b d )

22、所以所以 ac bd mod n 模运算性质模运算性质(续续)四川大学电子信息学院17/72解：解： 实际上是要证明：实际上是要证明： 5601(mod56), 223 1(mod47) (1) 有：有：560 = ( 56 )10 = (53 )2 )10 ( ( (53) mod56 )2 ) mod56)10 (mod56) 而而 5 3=12513(mod56) 于是于是 (5 3 )21691(mod56) (5 3 ) 2 ) 10 1 (mod56) ， 于是有：于是有： 56 5601。 (2) 有：有： 223 = (26)3 25 26 = 64 17 mod(47) (2

23、6)3 17 3 25mod(47) (26)325 25 32 1 mod(47) 于是有：于是有： 47 223 1 转同余充要条件【例例1】 通过同余式演算证明通过同余式演算证明: 5601是是56的倍数，的倍数，2231是是47的倍数。的倍数。四川大学电子信息学院18/72【例例2】证明：正整数证明：正整数 N 被被 9 整除的充要条件是整除的充要条件是 N 的各位数字的各位数字(10进制进制)的和被的和被9整除。整除。证明：证明： 实际上是要证明实际上是要证明正整数正整数 N 与与N 的各位数字的和的各位数字的和在模在模9下同余。下同余。 设设 N = a0 +10a1 + 10 2

24、 a2 + 10 k ak ，将，将N看成是看成是10的整的整系数多项式系数多项式, f () a0 +a1 +2 a2 +k ak N记为：记为： N = f (10) ，显然有：，显然有： f (1) = a0 +a1 + a2 + ak 有有 10 1mod 9 由模运算性质，有由模运算性质，有 f (10) f (1) mod 9 即：即： N a0 +a1 + a2 + ak mod 9四川大学电子信息学院19/72证明证明: dncbcbdndndadnacbdadncbanmod: )( |1),(),()(|)(|)( 同同余余充充要要条条件件有有，再再由由从从而而，有有又又由

25、由，故故，有有充充要要条条件件由由同同余余性性质质如果如果 (ab) (ac) mod n，且且 (a, n) = d，则，则dncbmod（乘法的消去律）（乘法的消去律）如果如果 (ab) (ac) mod n，则则b c mod n； (加法的可约律加法的可约律) 例如：例如：(5 23) (5 7) mod 8， 23 7md 8 定理定理8：加法的加法的可约律与乘法的消去律可约律与乘法的消去律四川大学电子信息学院20/72推论推论1：如果如果 (ab) (ac) mod n，且且 (a, n) = 1， 则则b c mod n。（消去律）推论推论2： 如果如果 (a, n) =1，则，

26、则 a Zn = Zn 。 这里这里， aZn 表示表示 a 与中每一元素做模与中每一元素做模 n 乘法乘法。定义：定义：模模n下的乘法逆元下的乘法逆元：如果，(a, n) = 1，则 a 在 mod n下有存在一个 x ( x a0 ， ，则，则存在两个整数存在两个整数 x, y 使得使得 xa + yn = (a, n)当当(a, n) = 1时，即有时，即有 xa + yn = 1等式两端取模等式两端取模n，有，有 xa mod n=1 即存在一个即存在一个 x ，使得，使得 a x 1 mod n。如何求如何求 x ? 用辗转相除法求乘法逆元用辗转相除法求乘法逆元，即扩展的，即扩展的E

27、uclid算法算法【 例例 】计算550 1mod1769有有 x = 550, y = 171 所以所以 550 1mod 1769 = 550 1769 = 5503 + 119， 1 = 133 4 (代代3) 550 = 1194 + 74， =13(16131)4 =135164 (代代13) 119 = 74 1 + 45， = (29161 )5164 = 295 169 (代代16) 74 = 451 + 29， = 295 (45291 )9 =2914 459 (代代29) 45 = 291 + 16， = (74451 )14459 =74144523 (代代45) 29

28、 = 161 + 13， =7414(119741)23 = 7437 11923 (代代74) 16 = 131 + 3 = (5501194 )37 11923=55037 119171(代代119) 13 = 3 4 + 1 =55037(1769 5503 )171= 550550 1769171正向迭代过程正向迭代过程逆向迭代过程逆向迭代过程四川大学电子信息学院22/724.4.剩余类与完全剩余类剩余类与完全剩余类全体整数：全体整数：Z=0, 1 , 2 , 3 ，前面已定义：，前面已定义：a Z，称与称与 a 模模 n 同余的数的同余的数的全体全体为为 a 的同余类，显然的同余类，

29、显然全体全体整数模整数模 n 的同余类共有的同余类共有 n 个，他们分别为个，他们分别为n k+0， n k+1， n k+2， n k+(n -1)，( kz) ，共，共 n 类；类；若取若取n=4，整数分为，整数分为 4 类：类： C0 = 4k | kZ C1 = 4k +1 | kZ C2 = 4k +2 | kZ C3 = 4k +3 | kZ 所以，当所以，当n 1时，整数分为时，整数分为 n 类：类： C0 ， C1 ，Cn-1 Cj = nk +j | kZ ；j = 0,1,2,n1称称Cj为模为模n的一个的一个剩余类剩余类（即（即“一类余数一类余数”）。）。四川大学电子信息

30、学院23/724.4.剩余类与完全剩余类（续）剩余类与完全剩余类（续） 若从所有剩余类若从所有剩余类C0 ， C1 ，Cn-1类中各取一个数类中各取一个数构成集合，该集合则称为模构成集合，该集合则称为模n的一组的一组完全剩余系。完全剩余系。 显然，这样的集合有无数个，而最简单的完全剩余系为：显然，这样的集合有无数个，而最简单的完全剩余系为： 0, 1, 2, , n1称为称为非负最小完全剩余或标准完全剩余系。非负最小完全剩余或标准完全剩余系。 如，如，Z模模12的标准剩余系为：的标准剩余系为：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11定理定理9 9：设设a1，a2

31、 ，an是是 模模n的一组完全剩余系。的一组完全剩余系。 有整数有整数k，且，且 ( k, n ) = 1 ， 则则 k a1， k a2， ，k an也是一组完全剩余系。也是一组完全剩余系。 24/725.5.费马费马(Fermat)(Fermat)小定理与欧拉小定理与欧拉(Euler)(Euler)定理定理 (这两个定理在公钥密码体制中起着重要作用)定义：如果一个模定义：如果一个模n的剩余类里面的数都与的剩余类里面的数都与n互素，就把该剩互素，就把该剩余类称为余类称为与模数与模数n互素的剩余类互素的剩余类。 如如n=4， C3 = 4k +3 | kZ ， C3为与模数为与模数4互素的剩余

32、类互素的剩余类 在在与模数与模数n互素的的互素的的全部全部剩余类中，各取一数所组成的集剩余类中，各取一数所组成的集合叫模合叫模n的一组的一组缩系缩系。如。如1，3为模为模4的一组的一组缩系。缩系。定义：定义：欧拉函数欧拉函数 (n)是一个定义在正整数正整数集上的函数， (n)的值等于小于的值等于小于n且与且与 n互素的正整数的个数。互素的正整数的个数。欧拉函数：欧拉函数：例如：例如： (4) = (6) =2，(7) = 6， (8) = 4，25/72欧拉函数欧拉函数(续续)定理：定理：设整数设整数n (1)的唯一性分解形式为：的唯一性分解形式为：),.,2 , 1(0.2112121kip

33、ppppppnikkiikik是素数，其中，kiiippni11) 1()(则例如，例如，n = 120736 = 25 7311 (n) = 24 72610 = 47040 26/72特别，特别，当当 p 是一个素数，有是一个素数，有 ( p) = p1 当当 n 是两个素数是两个素数 p 和和 q的乘积，则对的乘积，则对n = p q，有，有 (n) = (p q) = (p) (q) = (p1)(q1) 证明：证明： 考虑模考虑模 n 的标准完全剩余系为的标准完全剩余系为0，1，( pq1)，而不与而不与n 互素的元素包括：互素的元素包括：p因子集合因子集合p，2p，(q1)p，q因

34、子集合因子集合q，2q，(p1)q和和0。 因此，有：因此，有： (n) = pq(q1)+ (p1) +1 = pq(p+ q) +1 (p1) (q1) = (p) (q) 例如：例如： (21) (37) = (3) (7) (31) (71)2 6=12欧拉函数欧拉函数(续续)四川大学电子信息学院27/72证明：当证明：当 x 过模过模 n 的一组缩系，则的一组缩系，则 ax 通过通过 (n) 个整数，个整数，由于由于（a，n）=1， （ xi， n ）=1 所以所以， （ a xi， n ）=1 i, j =1,2,. (n) 若若 a xi= a xj，可得可得 a xi a xj

35、 mod n 与所设与所设 x 过模过模 n 的一组的一组缩系矛盾，缩系矛盾， 故故 a x也过也过 n 的一组缩系。的一组缩系。定理定理1212：若（若（a，n）=1，x 过模过模 n 的一组缩系的一组缩系 ( 即即 x 取取x1， x (n) ，且，且xi与与 n 互素互素 ), 则则 a x也过也过 n 的一组缩系的一组缩系 。定理定理1111： 若若a1，a (n) 是是 (n) 个与个与n互素的整数，则互素的整数，则a1，a (n) 是模是模n的一组缩系的充要条件是它们两两对模的一组缩系的充要条件是它们两两对模n不同余。不同余。（从定义看，定理（从定义看，定理10，11时显然的）时显

36、然的）定理定理1010：模数模数n的一组缩系的元素个数为的一组缩系的元素个数为 (n) 。四川大学电子信息学院28/72定理定理1313 ：若：若 p 是素数，且不能整除是素数，且不能整除a，则有：，则有： a p1 1 mod p 或或 a p a mod p 显然，显然， a k (p1) 1 mod p a N = a k (p1) + r a N mod (p1) mod p 费马小定理应用举例：费马小定理应用举例： 计算计算 7 7560 560 mod 31 = ? mod 31 = ? 7560 = 7560mod (311) = 7(311)18+20 720 mod31 75

37、757575 mod31 5555 5 mod31 费马小定理费马小定理29/72证明：设证明：设 r1， r (n) 是模是模 n 的一组缩系，则由定理的一组缩系，则由定理12， ar1， ar (n) 也是模也是模 n 的一组缩系，的一组缩系， 故故 (ar1)(ar1 )(ar (n) r1r (n) mod n 即即 a (n) r1r (n) r1r (n) mod n 由于由于 ( ri, n ) =1 i=1,2,. (n) 故故 ( r1r (n) , n ) =1 由由定理定理8的推论的推论1（消去律）（消去律），有：，有： a (n) 1 mod n 得证得证定理定理141

38、4（EulerEuler定理）定理） ：设 n , a Z，且(a，n)=1， 则 a (n) 1 mod n 如， a = 3，n = 10； (10) = 4，34 = 81 1 mod 10 a = 2，n = 11； (11) = 10，210 = 1024 1 mod 11 30/72 有有 a k (n)+1 a mod n ( kZ )EulerEuler定理的推论定理的推论 : 给定两个素数给定两个素数 p, q，以及整数，以及整数 n = p q 和和 m， 其中其中0 m 0，则同余式：，则同余式： a x b mod n 恰有一个解。恰有一个解。而而 x = ba (n)

39、 1 就是其唯一解。就是其唯一解。 ( a1 a (n) 1 mod n ) 思路：思路：让让 x 过模过模 n 一个完全剩余系，一个完全剩余系，x = b = b1 1,b,b2 2, ,.,b.,bn n1 1， ax= = ab b1 1, , ab b2 2, ,., ., ab bn n1 1， 因为因为(a，n) = 1，所以，所以 ax 也过一个完全剩余系也过一个完全剩余系 故一定有一个故一定有一个 xi，使，使 a xi = b b mod n 故有解故有解( (其解可其解可代入证明代入证明) ) 定理定理1616： 设设 n 0，则同余式：，则同余式： a x b mod n

40、 有解的充要条件是：有解的充要条件是： (a, n)|b 且恰有且恰有(a, n)个解。个解。 6.6.同余方程（组）与中国剩余定理同余方程（组）与中国剩余定理四川大学电子信息学院32/72 例例: (1) 求求 2 x 179 mod 562 的整数解。的整数解。(2) 求求 256 x 179 mod 337 的整数解。的整数解。因为因为(256, 337) = 1, 所以所以同余式同余式有一个整数解。有一个整数解。 解法解法1： ( 256, 337 ) = 1 256在模在模337有逆元存在。有逆元存在。 2561 mod 337 = 104 用用104 乘以同余方程两边，有乘以同余方

41、程两边，有 104256 x 104179 mod 337 即即 x 104179 81 mod 337 解法解法2： 考虑二元一次不定方程：考虑二元一次不定方程：256 x+337 y=179 .(1) 由不定方程有解的充要条件，由不定方程有解的充要条件， 当当(256, 337) = 1 ,则一次不定方程则一次不定方程(1) 一定有解一定有解 。 利用扩展的利用扩展的Euclid算法，不定方程算法，不定方程(1)的一组特解为：的一组特解为： x0 = 104179 y0 = 79179显然，对式显然，对式(1)等式两端取等式两端取 mod337，即为同余式，即为同余式256 x 179 m

42、od 337所以得同余式解：所以得同余式解： x = 104179 81 mod 337 因为因为(2, 562)=2, 而而2 | 179, 故同余式没有整数解。故同余式没有整数解。 四川大学电子信息学院33/72例子：（孙子算经）今有物不知其数；三三数之余二；五五数之余三；例子：（孙子算经）今有物不知其数；三三数之余二；五五数之余三； 七七数之余二。问物几何？七七数之余二。问物几何？ 设设 x 为所求未知数。原问题为求解同余方程组：为所求未知数。原问题为求解同余方程组：7mod25mod33mod2xxx 对此方程组的一般解法，在明朝程大位的对此方程组的一般解法，在明朝程大位的“算法统算法

43、统宗宗”(1593)里有一首歌谣给出了答案：里有一首歌谣给出了答案： 三三人同行人同行七十七十稀，稀，五五树梅花树梅花廿一廿一枝，枝， 七七子团圆子团圆月正半月正半，除，除百零五百零五便得知。便得知。 其解为：其解为： x 702 + 213 +152 mod 105 = 23一般应如何求解同余方程组？一般应如何求解同余方程组？中国剩余定理中国剩余定理四川大学电子信息学院34/727mod25mod33mod2xxx(1) 3，5 = 15， 15mod 7 = 1 152 mod 7 = 2(2) 3，7 = 21， 21mod 5 = 1 213 mod 5 = 3 5，7 = 35， 3

44、5mod 3 = 2 351 mod 3 = 2显然，显然， 152 + 213 + 351 = 128 是一个解（但还不是最小解）是一个解（但还不是最小解）有：有：128k 3, 5,7 = 233 +k 105 ； kZ 所以最小正整数解为：所以最小正整数解为：x = 23普通解法：普通解法：四川大学电子信息学院35/72 设设m1, m2, mk是是 k 个两两互素的正整数，个两两互素的正整数， 并记并记 M = m1 m2 mk，Mi= M/mi， 则同余方程组：则同余方程组：在模在模 M 同余的意义下同余的意义下有唯一解有唯一解： x M1 M1 b1 M2 M2 b2 Mk Mk

45、bk mod M （2） 其中其中 Mi Mi 1 mod mi定理定理17（中国剩余定理，（中国剩余定理，CRT-China Residue Theorem ）：）：第 2 周)(mod.)(mod)(mod2211kkmbxmbxmbx（1）四川大学电子信息学院36/72定理定理17（中国剩余定理证明（中国剩余定理证明 ）：）：证明：由于证明：由于( mi , mj) =1，i j，所以，所以 (Mi , mi) = 1 注意到注意到 M = Mi mi 所以当所以当 i j， mi | Mj，即，即 Mj 0 mod mi，故故 M1 M1 b1 M2 M2 b2 Mk Mk bk （应

46、用模运算性质）（应用模运算性质） Mi Mi bi bi mod mi 故故(2)为为(1)的解的解 ( 注意：注意： Mi Mi 1 mod mi )另外，设整数另外，设整数y 也能同时满足式也能同时满足式(1)，由于，由于(2)式是满足式是满足(1)的正整数解，的正整数解，即即 y x mod m1，y x mod m2，y x mod mk， 也即，也即， m1 | ( x y )， m2 | ( x y )， ， mk | ( x y )由于由于m1, m2, mks两两互素，所以两两互素，所以 (m1 m2mk )| ( x y ) 所以所以 x y mod M 即在模即在模 M 同

47、余的意义下同余的意义下(2)是唯一解。是唯一解。第第 2 周周四川大学电子信息学院37/72 【举例举例】 11数剩数剩3，12数剩数剩2，13数剩数剩1，求本数。，求本数。解：依题意有，解：依题意有，3mod112mod121mod13xxx即即 m1 =11，m2 =12，m3 =13，b1 =3， b2 =2， b3 =1， 此时有：此时有： M =1112 13 =1716， M1 = 1716 /11=156，M2 = 1716 /12=143，M3 = 1716 /13=132而而M1 为一正整数，它满足：为一正整数，它满足：M1 M1 1 mod 11，即即1 M1 M1 156

48、 M1 mod 11 2 M1 mod 11 ，易得，易得 M1 = 6(可用扩展可用扩展Euclid算法求得：算法求得：M1 = M11 mod m1 = 1561 mod 11 = 21 mod 11 ) 同理，可求出：同理，可求出：M2 = 11， M3 = 7由由CRT，得解：，得解：x b1 M1 M1 b2 M2 M2 b3 M3 M3 3 156 6 + 2 143 11 + 1 132 7 14mod 1716所以，完全解为：所以，完全解为： x =14 + 1716 k kZ 四川大学电子信息学院38/72中国剩余定理的主要应用：中国剩余定理的主要应用：1、求解同余方程组、求

49、解同余方程组（模（模M下的唯一解）下的唯一解）；2、在模、在模M下可将一个非常大的数下可将一个非常大的数N，用一组较小的数组成的，用一组较小的数组成的 k 元组元组 (b1，b2，bk)来表达。来表达。 且在模且在模M下，下， N与与(b1，b2，bk) 唯一对应。唯一对应。3、ZM上元素的运算等价于上元素的运算等价于k 元组元组 对应元素之间的运算，即如果：对应元素之间的运算，即如果： A (a1，a2，ak)， B (b1，b2，bk) 则则 (A + B)mod M (a1 + b1) mod m1， (ak + bk) mod mk (AB)mod M (a1 b1) mod m1，

50、(akbk) mod mk (AB)mod M (a1b1) mod m1， (akbk) mod mk 四川大学电子信息学院39/72中国剩余定理的主要应用（续）中国剩余定理的主要应用（续） 例例: 将将973 mod 1813用模数为用模数为37和和49的两个数表示（的两个数表示（1813 = 3749 ）。）。 解：可取解：可取 N=973，M=1813， m1 =37，m2 =49， 有：有： b1 = N mod m1 = 973 mod 37=11 b2 = N mod m2 = 973 mod 49=42 所以所以 973 (11，42)若要计算若要计算 973mod1813 +

51、 678mod1813，则可先求出：，则可先求出： 678 (678 mod 37 , 678 mod 49)即即 678 (12 , 41)，应用上面性质可得加法表达为：，应用上面性质可得加法表达为： (11 + 12) mod 37, (42 +41) mod 49 = (23，34)四川大学电子信息学院40/727.7.离散对数离散对数 1 1）求模下的整数幂）求模下的整数幂 由由EulerEuler定理，如果定理，如果 ( (a, n)=1, n)=1，则，则 a (n) 1 mod n 现考虑一般形式，现考虑一般形式， a m 1 mod n ； m为一正整数为一正整数 (1)如果如

52、果 ( (a,n)=1,n)=1，则至少有一整数，则至少有一整数m ( m = = (n) )满足该方程。满足该方程。定义：定义：满足式满足式(1)(1)的的最小正整数最小正整数 m 为模为模n 下下a 的阶的阶( (又称次数又称次数) )。 例：例： a =7=7，n=19n=19，则易求出，则易求出 7 1 7 mod 19 ， 7 2 11 mod 19，7 3 1 mod 19， 即即7在模在模19下的阶为下的阶为3。四川大学电子信息学院41/727.7.离散对数离散对数 1 1）求模下的整数幂）求模下的整数幂( (续续) ) 由于由于7 3kj 7 3k7 j 7 j mod 19

53、所以，所以， 7 4 7 mod 19 ， 7 5 7 2 mod 19，即从，即从7 4 mod 19 开始，所求的幂出现循环，循环周期为开始，所求的幂出现循环，循环周期为3，即等于元素，即等于元素 7在模在模19下的阶。下的阶。 性质性质1 1：a的阶的阶m 整除整除 (n) ，即，即 m| (n) （注意：（注意： ( (a,n)=1,n)=1 ） 证：若证：若m不能整除不能整除 (n) ，可令，可令 (n) = k m+r，其中其中 0 r m1，那么由那么由EulerEuler定理：定理： a (n) =a k m+ r =(a m ) k a r mod n a r mod n 1

54、 mod n 即即 a r 1 mod n 与与m是模是模n下下a 的阶矛盾。的阶矛盾。 实际上，任意满足式实际上，任意满足式(1)的整数的整数m一定是一定是a的的阶的倍数。阶的倍数。 四川大学电子信息学院42/72定义：如果定义：如果 a 的阶等于的阶等于 (n) ，则称，则称a为为n的本原元（又称为素根）。的本原元（又称为素根）。特别地，如果特别地，如果a是是素数素数 p p 的本原元，则的本原元，则 a, ,a2 2, , ,ap p1 1 (p-1) (p-1)个数在模个数在模 p p 下互不相同，且均与下互不相同，且均与 p p 互素。互素。性质性质2 2：如果：如果a是是n n的本

55、原元，则的本原元，则 a, ,a2 2, , ,a ( (n) )在模在模n下互不相同，且均与下互不相同，且均与n互素。互素。证明：证明： 因为因为a, ,n互素，互素，ak k与与n互素显然。互素显然。 设设 ai a j mod mod n ；0 0 i 0 )，则称该算，则称该算法是多项式阶的；法是多项式阶的；l 若对某个常数若对某个常数a ( a1) 和多项式和多项式h(n)，算法的运行时间，算法的运行时间 T = O( ah(n) ), 则称该算法是指数阶的。则称该算法是指数阶的。 空间复杂性与时间复杂性空间复杂性与时间复杂性四川大学电子信息学院74/72 假设一台计算机在假设一台计

56、算机在1秒钟内可以执行秒钟内可以执行100万条指令，输入规模万条指令，输入规模n=106 。下表列出该台计算机上执行不同时间复杂度算法所需的运行时间。下表列出该台计算机上执行不同时间复杂度算法所需的运行时间。 空间复杂性与时间复杂性空间复杂性与时间复杂性( (续续) ) 当当T = O( n3 )，在串行机上执行算法在计算上变得不可行了，但在串行机上执行算法在计算上变得不可行了，但当采用当采用100万个处理器的机器就可在大约万个处理器的机器就可在大约10天内完成计算。天内完成计算。 但对于但对于T = O( 2n )，即使我们采用上万亿个处理器并行工作，要，即使我们采用上万亿个处理器并行工作，要执行这类算法在计算上也是不可行的。执行这类算法在计算上也是不可行的。 因此，如果破译一个密码体制所需的时间是因此，如果破译一个密码体制所需的时间是指数阶指数阶的，则它是的，则它是计算上安全的。计算上安全的。算法类型算法类型复杂度复杂度n106时的时的运算次数运算次数时间需求时间需求常数线性二次方三次方指数O(1)O(n)O(n2)O(n3)O(2n)110610121018103010301微秒1秒10天27397年3 10301016年四川大学电子信息学院75/72 许多密码可以采用穷尽搜索整个密钥空间来破译，即尝试每许多密码可以采用穷尽搜索整个密钥空间来破译，即尝试每个可能的密钥断定