《代数与数论》课件第十九章.ppt

1、1主要内容主要内容l 素数素数l 最大公约数与最小公倍数最大公约数与最小公倍数l 同余同余l 一次同余方程一次同余方程l 欧拉定理与费马小定理欧拉定理与费马小定理l 初等数论在计算机科学技术中的几个应用初等数论在计算机科学技术中的几个应用第六部分第六部分 初等数论初等数论2第十九章第十九章 初等数论初等数论 主要内容主要内容l 素数素数l 最大公约数与最小公倍数最大公约数与最小公倍数l 同余同余l 一次同余方程一次同余方程l 欧拉定理与费马小定理欧拉定理与费马小定理l 初等数论在计算机科学技术中的几个应用初等数论在计算机科学技术中的几个应用319.1 素数素数今后只考虑正整数的正因子今后只考虑

2、正整数的正因子.平凡因子平凡因子:1 和自身和自身真因子真因子:除除 1 和自身之外的因子和自身之外的因子例如例如,2,3 是是 6 的真因子的真因子设设a,b是两个整数，且是两个整数，且b0.如果存在整数如果存在整数c 使使 a=bc，则，则称称a 被被b 整除整除，或，或 b 整除整除a，记作，记作 b|a.此时此时,又称又称 a 是是b 的的倍数倍数，b是是a 的的因子因子.把把 b 不整除不整除 a 记作记作 b a.例如例如,6有有8个因子个因子1,2,3和和6.4整除的性质整除的性质性质性质19.1 若若a|b且且a|c,则则 x,y,有有a|xb+yc.性质性质19.2 若若a|

3、b且且b|c,则则a|c.性质性质19.3 设设 m0,则则 a|b 当且仅当当且仅当 ma|mb.性质性质19.4 若若a|b且且b|a,则则a=b.性质性质19.5 若若a|b且且b0,则则|a|b|.带余除法带余除法:a=qb+r,0r 1,p是素数且是素数且d|p,则则d=p.性质性质19.7 设设p是素数且是素数且p|ab,则必有则必有p|a 或者或者 p|b.设设p是素数且是素数且p|a1a2ak,则必存在则必存在1ik,使得使得p|ai.注意注意:当当d不是素数时不是素数时,d|ab不一定能推出不一定能推出d|a或或d|b.性质性质19.8 a1是合数当且仅当是合数当且仅当a=b

4、c,其中其中1ba,1c1,则则 a=,其中其中p1,p2,pk是不相同的素数是不相同的素数,r1,r2,rk是正整数是正整数,并且在并且在不计顺序的情况下不计顺序的情况下,该表示是惟一的该表示是惟一的.该表达式称作整数该表达式称作整数 a 的的素因子分解素因子分解.例如例如 30=235,117=3213,1024=210 推论推论 设设a=,其中其中 p1,p2,pk 是不相同的素数是不相同的素数,r1,r2,rk是正整数是正整数,则正整数则正整数d为为a的因子的充分必要条件的因子的充分必要条件是是d=,其中其中0siri,i=1,2,k.krkrrppp2121krkrrppp2121k

5、skssppp21217例题例题例例1 21560有多少个正因子有多少个正因子?解解 21560=2357211由推论由推论,21560的正因子的个数为的正因子的个数为4232=48.例例2 10!的二进制表示中从最低位数起有多少个连续的的二进制表示中从最低位数起有多少个连续的0?解解 2,3,4=22,5,6=23,7,8=23,9=32,10=25.得得 10!=2834527,故故10!的二进制表示中从最低位数起有的二进制表示中从最低位数起有8 8个连续的个连续的0.8素数的分布素数的分布梅森数梅森数(Marin Mersenne):2p 1,其中其中p为素数为素数 当当n是合数时是合数

6、时,2n 1一定是合数一定是合数,2ab 1=(2a 1)(2a(b 1)+2a(b 2)+2a+1).梅森数可能是素数梅森数可能是素数,也可能是合数也可能是合数:22 1=3,23 1=7,25 1=31,27 1=127都是素数都是素数,而而211 1=2047=2389是合数是合数.到到2002年找到的最大梅森素数是年找到的最大梅森素数是213466917 1,有有4百万位百万位.定理定理19.2 有无穷多个素数有无穷多个素数.证证 用反证法用反证法.假设只有有穷多个素数假设只有有穷多个素数,设为设为p1,p2,pn,令令m=p1p2pn+1.显然显然,pi m,1in.因此因此,要么要

7、么m本身本身是素数，要么存在大于是素数，要么存在大于pn的素数整除的素数整除m,矛盾矛盾.9素数的分布素数的分布(续续)(n):小于等于小于等于n的素数个数的素数个数.例如例如 (0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.168 1229 9592 78498 664579 145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.071(n)n/ln n(n)n/ln n 103 104 105 106 107n定理定理19.3(素数定理素数定理)1ln/)(limnnnn 10素数测试素数测试aa定理定理11.4 如果如果a

8、是合数是合数,则则a必有小于等于必有小于等于 的真因子的真因子.证证 由性质由性质19.8,a=bc,其中其中1ba,1c()2=a,矛盾矛盾.推论推论 如果如果a是合数是合数,则则a必有小于等于必有小于等于 的素因子的素因子.证证 由定理由定理,a有小于等于有小于等于 的真因子的真因子b.如果如果b是素数是素数,则结论成立则结论成立.如果如果b是合数是合数,由性质由性质19.9和性质和性质19.5,b有有素因子素因子pb .根据性质根据性质11.2,p也是也是a 的因子的因子,结论也结论也成立成立.aaaa11157161例例3 判断判断157和和161是否是素数是否是素数.解解 ,都小于都

9、小于13,小于小于13的素数有的素数有:2,3,5,7,11.检查结果如下检查结果如下:2 157,3 157,5 157,7 157,11 157 结论结论:157是素数是素数.2 161,3 161,5 161,7|161（161=723）结论：结论：161是合数是合数.例题例题12 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

10、 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3

11、7 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

12、40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

13、 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4

14、5 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100埃拉托斯特尼埃拉托斯特尼(Eratosthene)筛法筛法13d是是a与与b的的公因子公因子(公约数公约数):d|a且且d|bm是是a与与b的的公倍数公倍数:a|m且且b|m定义定义19.3 设设a和和b是两个不全为是两个不全为0的整数的整数,称称a与与b的公因子中

15、的公因子中最大的为最大的为a与与b的的最大公因子最大公因子,或或最大公约数最大公约数,记作记作gcd(a,b).设设a和和b是两个非零整数是两个非零整数,称称a与与b最小的正公倍数为最小的正公倍数为a与与b的的最小公倍数最小公倍数,记作记作lcm(a,b).例如例如 gcd(12,18)=6,lcm(12,18)=36.对任意的正整数对任意的正整数a,gcd(0,a)=a,gcd(1,a)=1,lcm(1,a)=a.19.2 最大公约数与最小公倍数最大公约数与最小公倍数14定理定理19.5 (1)若若a|m,b|m,则则 lcm(a,b)|m.(2)若若d|a,d|b,则则d|gcd(a,b)

16、.证证(1)记记M=lcm(a,b),设设m=qM+r,0rD,注意到注意到d|a,D|a,由由(1),得得m|a.同理同理,m|b.即即,m是是a和和b的公因子的公因子,与与D是是a和和b的最大公约数矛盾的最大公约数矛盾.最大公约数与最小公倍数的性质最大公约数与最小公倍数的性质15最大公约数与最小公倍数最大公约数与最小公倍数(续续)例例4 求求150和和220的最大公约数和最小公倍数的最大公约数和最小公倍数.利用整数的素因子分解利用整数的素因子分解,求最大公约数和最小公倍数求最大公约数和最小公倍数.设设 其中其中p1,p2,pk是不同的素数是不同的素数,r1,r2,rk,s1,s2,sk是非

17、负是非负整数整数.则则 gcd(a,b)=lcm(a,b)=,2121krkrrpppa,2121ksksspppb,),min(),min(2),min(12211kksrksrsrppp),max(),max(2),max(12211kksrksrsrppp解解 150=2352,168=2337.gcd(150,168)=21315070=6,lcm(150,168)=23315271=4200.16辗转相除法辗转相除法定理定理19.6 设设a=qb+r,其中其中a,b,q,r 都是整数都是整数,则则 gcd(a,b)=gcd(b,r).证证 只需证只需证a与与b和和b与与r有相同的公因

18、子有相同的公因子.设设d是是a与与b的公因的公因子子,即即d|a且且d|b.注意到注意到,r=a qb,由性质由性质19.1,有有d|r.从而从而,d|b且且d|r,即即d也是也是b与与r的公因子的公因子.反之一样反之一样,设设d是是b与与r的公的公因子因子,即即d|b且且d|r.注意到注意到,a=qb+r,故有故有d|a.从而从而,d|a且且d|b,即即d也是也是a与与b的公因子的公因子.17辗转相除法辗转相除法欧几里得欧几里得(Euclid)算法算法辗转相除法辗转相除法设整数设整数a,b,且且b0,求求gcd(a,b).做带余除法做带余除法 a=qb+r,0r0,再对再对b和和r做带余除法

19、做带余除法 b=q r+r,0r 0是是a和和b的公因子的公因子,有有 d|xa+yb,即即 d|1.从而从而 d=1,得证得证a和和b互素互素.定义定义19.2 如果如果gcd(a,b)=1,则称则称a和和b互素互素.如果如果a1,a2,an中中的的任意两个都互素任意两个都互素,则称它们则称它们两两互素两两互素.例如例如,8和和15互素互素,而而8和和12不互素不互素.4,9,11,35两两互素两两互素.21例题例题例例6 设设a|c,b|c,且且a与与b互素互素,则则ab|c.证证 根据定理根据定理19.8,存在整数存在整数x,y,使使xa+yb=1.两边同乘以两边同乘以c,得得cxa+c

20、yb=c.又由又由a|xa和和b|c,可得可得ab|cxa.同理同理,ab|cyb.于是于是,有有ab|cxa+cyb,即即ab|c.2219.3 同余同余定义定义19.3 设设m是正整数是正整数,a和和b是整数是整数.如果如果m|a b,则称则称a模模m同余于同余于b,或或a与与b模模m同余同余,记作记作ab(mod m).如果如果a与与b模模m不同余不同余,则记作则记作a b(mod m).例如例如,153(mod 4),160(mod 4),14 2(mod 4),15 16(mod 4).下述两条都是下述两条都是a与与b模模m同余的充分必要条件同余的充分必要条件:(1)a mod m=

21、b mod m.(2)a=b+km,其中其中k是整数是整数.23同余的性质同余的性质性质性质19.10 同余关系是等价关系同余关系是等价关系,即同余关系具有即同余关系具有 自反性自反性.aa(mod m)传递性传递性.ab(mod m)bc(mod m)ac(mod m).对称性对称性.ab(mod m)ba(mod m).缩写缩写 a1a2ak(mod m).性质性质19.11 模算术运算模算术运算 若若ab(mod m),cd(mod m),则则 acbd(mod m),acbd(mod m),akbk(mod m),其中其中k是非负整数是非负整数.性质性质19.12 设设d1,d|m,则

22、则ab(mod m)ab(mod d).性质性质19.13 设设d1,则则ab(mod m)dadb(mod dm).性质性质19.14 设设c,m互素互素,则则ab(mod m)cacb(mod m).24模模m等价类等价类模模m等价类等价类:在模在模m同余关系下的等价类同余关系下的等价类.am,简记作简记作a.Zm:Z在模在模m同余关系下的商集同余关系下的商集在在Zm上定义加法和乘法如下上定义加法和乘法如下:a,b,a+b=a+b,ab=ab.例例7 写出写出Z4的全部元素以及的全部元素以及Z4上的加法表和乘法表上的加法表和乘法表.解解 Z4=0,1,2,3,其中其中i=4k+i|kZ,i

23、=0,1,2,3.0123 0 1 2 3+0 1 2 31 2 3 02 3 0 13 0 1 2 0123 0 1 2 30 0 0 00 1 2 30 2 0 20 3 2 125例例8 3455的个位数是多少的个位数是多少?解解 设设3455的个位数为的个位数为x,则则3455x(mod10).由由341(mod 10),有有 3455=34 113+3337(mod 10),故故3455的个位数是的个位数是7.例例9 日期的星期数日期的星期数 y年年m月月d日星期数的计算公式日星期数的计算公式:其中其中M=(m3)mod12+1,Y=y M/11=100C+XY年年M月月:3月月下一

24、年下一年2月月,C:Y年的世纪数年的世纪数 )7(mod12/2/)7/(224/4/dmMMMCCXXw 例题例题26例题例题 )7(mod6112/82/)7/88(821924/194/4949 w )7(mod31512/62/)7/66(621924/194/4545 w例例9(续续)例如例如,中华人民共和国成立日中华人民共和国成立日1949年年10月月1日日,C=19,X=49,M=8,d=1,是星期六是星期六.中国人民抗日战争胜利日中国人民抗日战争胜利日1945年年8月月15日日,C=19,X=45,M=6,d=15,是星期三是星期三.2719.4 一次同余方程一次同余方程定理定

25、理19.9 方程方程axc(mod m)有解的充要条件是有解的充要条件是gcd(a,m)|c.证证 充分性充分性.记记d=gcd(a,m),a=da1,m=dm1,c=dc1,其中其中a1与与m1互素互素.由定理由定理11.8,存在存在x1和和y1使得使得a1x1+m1y1=1.令令x=c1x1,y=c1y1,得得a1x+m1y=c1.等式两边同乘等式两边同乘d,得得ax+my=c.所以所以,axc(mod m).必要性必要性.设设x是方程的解是方程的解,则存在则存在y使得使得ax+my=c.由性质由性质19.1,有有d|c.一次同余方程一次同余方程:axc(mod m),其中其中m0.一次同

26、余方程的一次同余方程的解解:使方程成立的整数使方程成立的整数例如例如,2x0(mod 4)的解为的解为x0(mod 2),2x1(mod 4)无解无解28例题例题例例10 解一次同余方程解一次同余方程 6x3(mod 9).解解 gcd(6,9)=3|3,方程有解方程有解.取模取模9等价类的代表等价类的代表x=4,3,2,1,0,1,2,3,4,检查它检查它们是否是方程的解们是否是方程的解,计算结果如下计算结果如下:6(4)6(1)623(mod 9),6(3)60630(mod 9),6(2)61646(mod 9),得方程的解得方程的解 x=4,1,2(mod 9),方程的最小正整数解是方

27、程的最小正整数解是2.29模模m逆逆定理定理19.10 (1)a的模的模m逆存在的充要条件是逆存在的充要条件是a与与m互素互素.(2)设设a与与m互素互素,则在模则在模m下下a的模的模m逆是惟一的逆是惟一的.证证(1)这是定理这是定理19.9的直接推论的直接推论.(2)设设ab11(mod m),ab21(mod m).得得a(b1 b2)0(mod m).由由a与与m互素互素,b1 b20(mod m),得证得证b1b2(mod m).定义定义19.4 如果如果ab1(mod m),则称则称b是是a的的模模m逆逆,记作记作a 1(mod m)或或a 1.a 1(mod m)是方程是方程ax1

28、(mod m)的解的解.30例题例题例例11 求求5的模的模7逆逆.解解 5与与7互素互素,故故5的模的模7逆存在逆存在.方法方法1.解方程解方程5x1(mod7).检查检查x=3,2,1,0,1,2,3,得到得到 5 13(mod7).方法方法2.做辗转相除法做辗转相除法,求得整数求得整数b,k使得使得 5b+7k=1,则则b是是5的模的模7逆逆.计算如下计算如下:7=5+2,5=22+1.回代回代 1=5 22=5 2(7 5)=35 27,得得 5 13(mod7).方法方法3.直接观察直接观察5 3=15,15 1(mod 7),得得 5 13(mod7).31欧拉函数欧拉函数(n):

29、0,1,n 1中与中与n互素的数的个数互素的数的个数 例如例如 (1)=(2)=1,(3)=(4)=2.当当n为素数时为素数时(n)=n 1;当当n为合数时为合数时(n)n 1.定理定理19.11(欧拉定理欧拉定理)设设a与与n互素互素,则则 a(n)1(mod n).19.5 欧拉定理和费马小定理欧拉定理和费马小定理 32欧拉定理的证明欧拉定理的证明证证 设设r1,r2,r(n)是是0,1,n 1中与中与n互素的互素的(n)个数个数.由于由于a与与n互素互素,对每一个对每一个1i (n),ari也与也与n互素互素,故存故存在在1(i)(n)使得使得 arir(i)(mod n).是是1,2,

30、(n)上的映射上的映射.要证要证 是一个单射是一个单射.a的模的模n逆逆a 1存在存在,a 1也与也与n互素互素.假设假设ij,(i)=(j),则有则有ariarj(mod n).两边同乘两边同乘a 1,得得rirj(mod n),矛盾矛盾.得证得证 是是1,2,(n)上的单射上的单射,当然也是当然也是1,2,(n)上的上的双射双射.从而从而,有有而而 与与n互素互素,故故a(n)1(mod n).)(mod)(1)(1)(1)(nrarraniiniiniin )(1niir 33费马费马(Fermat)小定理小定理定理定理19.12(费马小定理费马小定理)设设p是素数是素数,a与与p互素互

31、素,则则 ap-11(mod p).另一种形式是另一种形式是,设设p是素数是素数,则对任意的整数则对任意的整数a,apa(mod p).费马小定理提供了一种不用因子分解就能断定一个数是费马小定理提供了一种不用因子分解就能断定一个数是合数的新途径合数的新途径.例如例如,29 14(mod 9),可以断定可以断定9是合数是合数.3419.6 19.6 初等数论在计算机科初等数论在计算机科学技术中的几个应用学技术中的几个应用主要内容主要内容l 产生均匀伪随机数的方法产生均匀伪随机数的方法l 密码学密码学35产生均匀伪随机数的方法产生均匀伪随机数的方法随机数随机数:随机变量的观察值随机变量的观察值伪随

32、机数伪随机数(0,1)上的均匀分布上的均匀分布U(0,1):a(0a1),P0Xa=a 线性同余法线性同余法 选择选择4个非负整数个非负整数:模数模数m,乘数乘数a,常数常数c和种子数和种子数x0,其中其中2am,0cm,0 x0m,用递推公式产生伪随机数序列用递推公式产生伪随机数序列:xn=(axn 1+c)mod m,n=1,2,取取 un=xn/m,n=1,2,作为作为U(0,1)伪随机数伪随机数.36线性同余法与乘同余法线性同余法与乘同余法线性同余法产生的序列的质量取决于线性同余法产生的序列的质量取决于m,a和和c.例如例如m=8,a=3,c=1,x0=2,得到得到7,6,3,2,7,

33、6,周期为周期为4 m=8,a=5,c=1,x0=2,得到得到3,0,1,6,7,4,5,2,3,0,1,周期为周期为8.a=0,得到得到c,c,c,a=1,得到得到x0+c,x0+2c,x0+3c,乘同余法乘同余法:c=0(x00)的线性同余法的线性同余法,即即 xn=axn 1 mod m,n=1,2,.最常用的均匀伪随机数发生器最常用的均匀伪随机数发生器:m=231 1,a=75的乘同余法的乘同余法,它的周期是它的周期是231 2.37密码学密码学恺撒恺撒(Caesar)密码密码加密方法加密方法:ABCDEFGH I J KLMNOPQRS TUVWXYZ DEFGH I JKLMNO

34、PQRS TUVWXYZ ABC明文明文:SEE YOU TOMORROW密文密文:VHH BRX WRPRUURZ 18 4 4 24 14 20 19 14 12 14 17 17 14 22 21 7 7 1 17 23 22 17 15 17 20 20 17 25加密算法加密算法 E(i)=(i+k)mod 26,i=0,1,25,解密算法解密算法 D(i)=(i k)mod 26,i=0,1,25其中其中密钥密钥k是一取定的整数是一取定的整数,这里取这里取k=3.38加密算法加密算法线性同余加密算法线性同余加密算法 E(i)=(ai+b)mod 26,i=0,1,25,其中其中a与

35、与26互素互素.维吉利亚维吉利亚(Vigenere)密码密码把明文分成若干段把明文分成若干段,每一段有每一段有n个数字个数字,密钥密钥k=k1k2kn,加密算法加密算法 E(i1i2in)=c1c2cn,其中其中cj=(ij+kj)mod 26,ij=0,1,25,j=1,2,n.39RSA公钥密码公钥密码 私钥密码私钥密码:加密密钥和解密密钥都必须严格保密加密密钥和解密密钥都必须严格保密公钥密码公钥密码(W.Diffie,M.Hellman,1976):加密密钥公开加密密钥公开,解密解密密钥保密密钥保密RSA公钥密码公钥密码(R.Rivest,A.Shamir,L.Adleeman,1978

36、)取取2个大素数个大素数p和和q(pq),记记n=pq,(n)=(p 1)(q 1).选择正选择正整数整数w,w与与(n)互素互素,设设d=w 1(mod(n).将明文数字化将明文数字化,分成若干段分成若干段,每一个明文段每一个明文段mn.加密算法加密算法 c=E(m)=mwmod n,解密算法解密算法 D(c)=cdmod n,其中加密密钥其中加密密钥w和和n是公开的是公开的,而而p,q,(n)和和d是保密的是保密的.40解密算法正确性证明解密算法正确性证明要证要证m=cdmod n,即即cdm(mod n),亦即亦即mdwm(mod n).由由dw1(mod(n),存在存在k使得使得dw=

37、k(n)+1.有两种可能有两种可能:(1)m与与n互素互素.由欧拉定理由欧拉定理m(n)1(mod n),得得 mdwmk(n)+1 m(mod n).(2)m与与n不互素不互素.不妨设不妨设m=cp且且q不整除不整除m.由费马小定理由费马小定理 mq 11(mod q).于是于是,mk(n)mk(p 1)(q 1)1k(p 1)1(mod q).从而存在从而存在h使得使得 mk(n)=hq+1,两边同乘以两边同乘以m,并注意到并注意到m=cp,mk(n)+1=hcpq+m=hcn+m,得证得证 mk(n)+1m(mod n),即即 mdwm(mod n).41模幂乘运算模幂乘运算 )(mod

38、)()(111022naaaarrbbbb)(mod110110nAAAarbrbbb模幂乘运算模幂乘运算ab(mod n)设设b=b0+b12+br 12r 1,其中其中bi=0或或1,于是于是令令 A0=a,Ai(Ai 1)2(mod n),i=1,2,r 1,则有则有42例题例题例例12 p=43,q=59,n=4359=2537,(n)=4258=2436,w=13.A,B,Z依次用依次用00,01,25表示表示,各占各占2位位.设明文段设明文段m=2106,即即VG,密文密文c=210613mod 2537.计算如下计算如下:13=(1101)2,即即13=1+22+23.A0=21

39、06 431(mod 2537),A1(431)2560(mod 2537),A25602 988(mod 2537),A3(988)2 601(mod 2537),210613(431)(988)(601)2321(mod 2537),得密文得密文c=2321.43例题例题(续续)设密文设密文c=0981.d=13 1937(mod 2436),明文明文m=981937(mod 2537).计算如下计算如下:937=(1110101001)2,A0=981,A19812838(mod 2537),A28382 505,A3(505)21325,A41325221,A5212441,A6441

40、2 868,A7(868)2 65,A8(65)2 849,A9(849)2293,9819379811325441(65)(849)293 704(mod 2537),得明文得明文m=0704,即即HE.44第十九章第十九章 习题课习题课主要内容主要内容l 素数与合数素数与合数,埃拉托斯特尼筛法埃拉托斯特尼筛法l 最大公约数与最小公倍数最大公约数与最小公倍数,辗转相除法辗转相除法l 同余同余,模模m等价类及其运算等价类及其运算l 一次同余方程及有解的充分必要条件一次同余方程及有解的充分必要条件l 欧拉定理与费马小定理欧拉定理与费马小定理l 产生均匀伪随机数的方法产生均匀伪随机数的方法l 密码

41、学密码学45基本要求基本要求l 熟练掌握整除、素数、合数的概念及其性质熟练掌握整除、素数、合数的概念及其性质,掌握算术掌握算术基本定理基本定理,能熟练地素因子分解能熟练地素因子分解,会判断素数会判断素数,掌握埃拉掌握埃拉托斯特尼筛法托斯特尼筛法.l 熟练掌握最大公约数和最小公倍数的概念及其性质熟练掌握最大公约数和最小公倍数的概念及其性质,会求最大公约数和最小公倍数会求最大公约数和最小公倍数,掌握辗转相除法掌握辗转相除法.l 熟练掌握互素的概念及其性质熟练掌握互素的概念及其性质.l 熟练掌握同余的概念及其性质熟练掌握同余的概念及其性质,掌握一次同余方程的掌握一次同余方程的解存在的充分必要条件解存

42、在的充分必要条件,掌握模掌握模m逆逆的概念及存在的充的概念及存在的充分必要条件分必要条件,会求一次同余方程的解和模会求一次同余方程的解和模m逆逆.l 掌握欧拉定理和费马小定理掌握欧拉定理和费马小定理.46要求要求(续续)l 会做不太难的证明会做不太难的证明.l 了解初等数论在伪随机数生成和密码学中的应用了解初等数论在伪随机数生成和密码学中的应用,掌握掌握产生均匀伪随机数的线性同余法和乘同余法产生均匀伪随机数的线性同余法和乘同余法,知道明文、知道明文、密文、加密、解密、密钥、私钥密码和公钥密码等概密文、加密、解密、密钥、私钥密码和公钥密码等概念，了解恺撒密码、维吉利亚密码和念，了解恺撒密码、维吉

43、利亚密码和RSA公钥密码公钥密码.47练习练习11.判断下述命题是真是假判断下述命题是真是假:(1)3|-12;(2)3|8;(3)0|8;(4)-21|0;(5)527 465(mod 15);(6)215-175(mod 13).TTTFFF482.求求280与与180的最大公约数和最小公倍数的最大公约数和最小公倍数.练习练习2解解 方法一方法一 利用整数的素因子分解利用整数的素因子分解.280=23 5 7,180=22 32 5.gcd(280,180)=22 5=20,lcm(280,180)=23 32 5 7=2520.方法二方法二 用辗转相除法和公式用辗转相除法和公式ab=gc

44、d(a,b)lcm(a,b)280=180+100,180=100+80,100=80+20,80=4 20得得 gcd(280,180)=20,lcm(280,180)=280 180/20=2520.493.计算计算:(1)2100mod 11;练习练习3解解 方法一方法一 用带余除法用带余除法.2100=190 11+10,得得 2100mod 11=10.方法二方法二 利用同余的性质化简计算利用同余的性质化简计算.2100 21 10 10(-1)(-1)(-1)-1 10(mod 11),得得2100mod 11=10.(2)2340mod 31.解解 2340 25 68 3268

45、 168 1(mod 31),故故2340mod 31=1.504.8的模的模3逆是否存在逆是否存在?若存在若存在,试给出试给出.练习练习4解解 8与与3互素互素,根据定理根据定理19.10,8的模的模3逆存在逆存在.方法一方法一 直接观测直接观测.不难看出不难看出 2 8 1(mod 3),故故8-1(mod 3)2.方法二方法二 检查模检查模3等价类的代表等价类的代表0,1,2.检查结果如下检查结果如下:0 8 0(mod 3),1 8 2(mod 3),2 8 1(mod 3),得得 8-1 2(mod 3).方法三方法三 用辗转相除法用辗转相除法.计算如下计算如下:8=2 3+2,3=2+11=3-2=3-(8-2 3)=3 3-8,得得 (-1)8 1(mod 3),8-1-1 2(mod 3).515.利用费马小定理证明利用费马小定理证明10不是素数不是素数.练习练习5证证 310-1 273(-3)3 -27 3 1(mod 10),得证得证10不是素数不是素数.