资源描述：
《第2章信息安全数学基础new(数论).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章信息安全数学基础2010、072021/7/18第2章信息安全数学基础2.4模的幂运算2.3中国剩余定理2.2同余2.1基本概念2.5本原根2021/7/18第2章信息安全数学基础2.1基本概念2021/7/182.整除的基本性质(N—整数集)(1)a(a≠0),a
2、0,a
3、a(同理bN,1
4、b)(2)b
5、acb
6、ca(3)a
7、b,b
8、ca
9、c.（传递性）(4)a
10、b,a
11、ca
12、(xb+yc)(x,yN)(5)b
13、a且a≠0
14、b
15、≤
16、a
17、(6)cb
18、ca,b
19、a1.定义：设整数a和b,且a≠0，如果存在整数k使得b=ak，那么就说a整除b（或b能被a整除
20、），记作a
21、b，或者说b是a的倍数。举例：3
22、15,-15
23、60整除定义及性质2021/7/18带余数除法：如果a，b是两个整数，其中b>0，则存在两个整数q和r，使得a＝bq＋r（0≤r＜b）成立，且q和r是唯一的。带余数除法2021/7/18非负最小剩余的性质：（1）=<+>（2）=<->（3）=<>定义（非负最小剩余）a＝bq＋r（0≤r＜b）中r叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，b常常省略）带余数除法2021/7/181.定义：一个大于1的整数p，只能被1
24、或者是它本身整除，而不能被其他整数整除，则称整数为素数(primenumber)，否则就叫做合数(composite)。eg素数（2，3，5，7，11，13等）合数（4，6，8，9，12等）素数定义及素数个数定理2021/7/182.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时：素数补充定理2021/7/182.补充定理(2)：若p是一个素数，a是任一整数，则有p
25、a或(p，a)=1素数补充定理（续）2021/7/18素数补充定理（续）2.补充定理：p为素数，且p
26、ab，那么p
27、a或p
28、b。更一般地，如果ab…z能够被素数p整除，那
29、么a,b,…,z中的某个数必能被p整除。2021/7/183.素数个数定理（1）：素数的个数是无限的。原因：（1）N（N>1）的除1外的最小正因数q是一个素数（2）如果q=pi，（i＝1,2,…,k),且q
30、N，因此q
31、(N-p1p2,…..pk)，所以q
32、1，与q是素数矛盾。素数个数定理及证明证明：反证法假设正整数个数是有限的，设为p1,p2,…..,pk令：p1p2…pk+1=N(N>1)则N有一个素数p，且p≠pi（i=1,2,…,k).故p是上述k个素数外的另外一个素数。因此与假设矛盾。2021/7/18素数定义及素数个数定理3.素数个数定理（2）：设(x)是小于x的
33、素数个数，则(x)≈x/lnx,即x→∝时，比值(x)/(x/lnx)→1eg:可以估算100位素数的个数：(10100)-(1099)≈10100/(ln10100)–1099/(ln1099)≈3.9*1097.2021/7/181.整数的唯一分解定理定理（算术基本定理）:设n∈Z，有分解式，n=±p1e1p2e2...pmem，其中p1,p2,…,pm∈Z+是互不相同的素数，e1,e2,…,em∈Z+,并且数对(p1,e1),(p2,e2),…,(pm,em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）.eg:504=23327,1125=3253整数的唯一
34、分解定理2021/7/181.定义两个整数a，b的最大公约数，就是能同时整除a和b的最大正整数，记为gcd(a,b)，或，(a,b)。eg:gcd(5,7)=1，gcd(24,60)=12，最大公约数定义及求法2.求最大公约数的两种方法：(1)因数分解：eg:1728=2632，4536=23347,gcd(1728,4536)=2332=72。2021/7/18(2)欧几里得(Euclid)算法设a,bN,a>b>0,用以下方法可求出gcd(a,b)。最大公约数的欧几里得算法2021/7/18Euclid算法实例：求gcd(132,108).最大公约数的欧几里得算法（续）2
35、021/7/18欧几里得算法（例1）gcd（1180，482）＝2求：gcd（1180，482）最大公约数的欧几里得算法（续）2021/7/18欧几里得算法（例2）：求gcd(12345，1111)最大公约数的欧几里得算法（续）2021/7/18欧几里得算法抽象规律：余数－除数－被除数－忽略最大公约数的欧几里得算法（续）2021/7/18欧几里得算法实现最大公约数的欧几里得算法（续）2021/7/18特别a,b为素数时gcd(a,b)=1，存在ma+nb=1.上述求rn=ma+nb的方法叫做
