信息安全数学基础第01章.ppt

《信息安全数学基础第01章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章整数与同余第1章整数与同余整数整数的进位制表示法整数分解同余1.1整数整数的定义整除1.1整数整数的定义整数：…,-3,-2,-1,0,1,2,3,…正整数(自然数)：1,2,3,4,…奇数：…,-7,-3,-1,1,3,5,7,…偶数：…,-8,-4,-6,2,4,6,8,…1.1整数整数的定义Z：所有整数构成的集合Z＋：所有正整数构成的集合a,b,c,d,…：表示整数当几个小写英文字母在一起时，表示将这几个整数相乘，例如ab=a×b,abc=a×b×c。当n是一个大于l的正整数时，an表示由n个相同的整数a相乘所得的积。1.1整数整数的定义用记号

2、a

3、来表示整数a的绝对值，即例如

4、2

5、

6、＝

7、-2

8、＝2。1.1整数整数的定义最小整数公理（良序性）：每个正整数集的非空子集中都存在着一个最小的正整数。注：虽然正整数集合具有良序性，但是由于许多整数的子集中都不具有最小值，因而由所有整数构成的集合Z并不具有良序性。例如所有负整数构成的集合以及所有小于200的偶数构成的集合。1.1整数整数的定义在整数范围内，我们知道整数+整数=整数整数整数=整数整数×整数=整数但是整数除整数却不一定得整数，究竟什么样的整数除什么样的整数才能得到整数呢？1.1整数整除定义1.1.1：设a，b是两个给定的整数且a≠0。如果存在整数c使得b=ac，则称a整除b，记为a

9、b，有时也称a是b的因子（或因数），

10、b是a的倍数；反之，若找不到这样的整数c，则称a不整除b，记为a∤b。例如：易知3

11、6，而3∤5，同时6的因子分别为±1,±2,±3,±6。1.1整数整除定理1.1.1：若整数a，b，c满足条件a

12、b且b

13、c，则a

14、c。证明：若a

15、b且b

16、c，则由定义1.1.1知道存在整数e和f使得b=ae且c=bf，于是c=bf=(ae)f=a(ef)由于整数e与f的乘积仍然是整数，因而a

17、c。例如：由于11

18、66且66

19、198，由定理1.1.1就有11

20、198。1.1整数整除定理1.1.2：设整数a，b，c满足条件c

21、a且c

22、b，则m,nZ，都有c

23、(ma+nb)。证明：由于c

24、a且c

25、b，因而存在整

26、数e，f使得a=ce，b=cf进而ma+nb=mce+ncf=c(me+nf)由于me+nf仍然是整数，因而c

27、(ma+nb)1.1整数整除例如：由于3

28、21且3

29、33，由定理1.1.2就有3

30、(5×21-3×33)即3

31、61.1整数整除定义1.1.2：一个大于1的正整数，若只能被1和其本身整除，而不能被其他正整数整除，则称其为素数（或质数），通常记为p或p1,p2,p3,…。例如：2，3，5，7，11，13，…都是素数。注：我们约定，1不是素数。否则，一个自然数写成素数之积的形式就不唯一了，例如100=1╳1╳1╳…╳1╳2╳2╳5╳5在此约定下，一个自然数可以唯一地写成若干素数之积，这一结

32、论就是后面我们要证明的算术基本定理。1.1整数整除定义1.1.3：大于1的不是素数的自然数称为合数。例如：4，6，8，9，10，12，…都是合数。注：全体正整数可分为三类：1.2整数的进位制表示法带余除法整数的二进制表示法数值转换1.2整数的进位制表示法带余除法定理1.2.1（带余数除法）：设a是正整数，b是整数，则一定存在唯一的整数q和r，使得b=qa+r，其中0≤r

33、设存在整数q与r，以及整数q1与r1，使得b=qa+r，0≤r

34、(r1-r)由假设0≤r

35、uT且u0}则集合S（只要取满足条件k

36、一个最小值，设其最小值为：r=b-qa01.2整数的进位制表示法带余除法接下用反证法来证明rr-a（a>0）=b-qa-a=b-(q+1)a0故b-(q+1)aS而显然有b-(q+1)a0，则任一整数被a