密码学与网络安全第二章密码数学ppt课件.ppt

《密码学与网络安全第二章密码数学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章密码数学基础（1）§1整数运算一、整数集Z={0,±1,±2,±3,…….}为整数集。Z+={0,1,2,3,…….}为正整数集。N={1,2,3,…….}为自然数集。在N、Z+上能进行普通加法和乘法运算，不能做普通减法和除法运算；在Z上能进行加法、减法、乘法运算，不能做普通除法运算；运算不能封闭！二、整数除法——带余除法a=q×n+r255=23*11+2255÷11=23…2规定：除数n为正数，余数r非负。a÷n=q…r-255=(-23*11)+(-2)=(-24*11)+9商数-1,余数+11-89÷7=-12…-5=-

2、13…2a=q×n+r被除数：a为整数商数：q为整数余数：r为非负整数除数：n为正整数我们在整数集Z上的除法运算:三、整除性(divisibility)当余数r=0时，a=q×n，称为“n整除a”，或“a被n整除”，记为：n

3、a可以说:“n是a的一个因子”,“a含有因子n”Z上的整除有如下基本性质：（1）若a

4、1，则a=±1（2）若a

5、b，且b

6、a，则a=±b（3）若a

7、b，且b

8、c，则a

9、c（4）若a

10、b，且a

11、c，则a

12、(mb+nc)m，n为任意整数divisor:因子，因数，约数思考：在正整数集上的性质？三、整性例1：4

13、32,

14、11

15、(-33)5

16、0,-8

17、03

18、27,-6

19、24,6

20、-24例2：5

21、(-5),-5

22、55

23、25,25

24、100=>5

25、1007

26、35,7

27、21=>7

28、(m*35+n*21)=>7

29、(35+21)=56=>7

30、(35-21)=14=>7

31、(2*35-6*21)=-56四、最大公约数（最大公因子）正整数a的因子有：1，a本身，其它因子1只能被1整除素数只能被1或自身整除不是1且非素数的正整数称为“合数”，合数除了1和自身之外，还有其它因子。若a

32、b，a

33、c，则称a是b，c的公因子；若其它公因子都能整除a（都是a的因子），a是所有公因子

34、中最大的一个，称为“最大公因子”greatestcommondivisor——gcdb与c的最大公因子记为:gcd(b,c)gcd(b,c)是能同时整除b和c的最大整数。三、最大公约数（最大公因子）例312=1*2*2*3，12的因子有：1，2，3，4，6，12140=1*2*2*5*7，12的因子有：1，2，4，5，7，10，14，20，28，35，70，14012与140的公因子有：1，2，4所以，gcd(12,140)=4麻烦！不是好方法！求gcd(12,140)五、Euclidean算法——辗转相除定理1gcd(a,0)=a证

35、明：只需规定：任何整数都是0的因子。定理2若a=qb+r,则gcd(a,b)=±gcd(b,r)证明：设d=gcd(a,b),d*=gcd(b,r),则d

36、a,d

37、b,则d

38、(a-qb)，即d

39、r，d也是b,r的公因子，所以d

40、d*。同理，d*

41、b,d*

42、r,则d*

43、(qb+r),即d*

44、ad*也是a,b的公因子，所以d*

45、d。因此，d*

46、b且d*

47、d,可知d*=±d。当a和b都是正整数时，gcd(a,b)=gcd(b,r)辗转相除算法：例4求gcd(12,140)140=11*12+8=>gcd(140,12)=gcd(12,8)1

48、2=1*8+4=>gcd(12,8)=gcd(8,4)8=2*4+0=>gcd(8,4)=gcd(4,0)=4所以，gcd(140，12)=4例5求gcd(36,10)36=3*10+6=>gcd(36,10)=gcd(10,6)10=1*6+4=>gcd(10,8)=gcd(6,4)6=1*4+2=>gcd(6,4)=gcd(4,2)所以，gcd(36，10)=24=2*2+0=>gcd(4,2)=gcd(2,0)=2例6求gcd(2740,1760)qr1r2r27401760198017609801780980780120078

49、020031802001801201802090200算法分析：r1=a;r2=brr1;r2rr1;r20r1;0r1a；r2b当r2>0时{qr1/r2;rr1-q*r2；r1r2;r2r;}gcd(a,b)=r1qqq例7求gcd(25,60)qr1r2r256002560252102510251052050gcd(25,60)=5六、扩展Euclidean算法定理3若gcd(a,b)=d，必存在整数s，t使d=s*a+t*b例8将gcd(726,393)=3表示为s*726+t*393qr1r2r172639333

50、3139333360533360331603327133276427632630303=27-4*63=27-4*(33-27)=-4*33+5*273=-4*33+5*(60-33)=5*60-9*333=5*60-9