《第2章 信息安全数学基础new(数论)》由会员分享，可在线阅读，更多相关《第2章 信息安全数学基础new(数论)（10页珍藏版）》请在金锄头文库上搜索。
1、2015-3-18 3. 3. 3. 3.素数个数定理（素数个数定理（1 1 1 1）：素数的个数是无限的。）：素数的个数是无限的。 原因：原因： （1 1 1 1）N N N N（N1N1N1N1）的除）的除1 1 1 1外的最小正因数外的最小正因数q q q q是一个素数是一个素数 （2 2 2 2）如果）如果q=pq=pq=pq=pi i i i，（，（i i i i1,2,1,2,1,2,1,2,k), ,k), ,k), ,k), 且且q|Nq|Nq|Nq|N，因此，因此q|(Nq|(Nq|(Nq|(N- - - - p p p p1 1 1 1p p p p2 2 2 2, , ,
2、 , p p p pk k k k) ) ) )，所以，所以q|1q|1q|1q|1，与，与q q q q是素数矛盾。是素数矛盾。 素数个数定理及证明素数个数定理及证明 证明：反证法证明：反证法 假设正整数个数是有限的，设为假设正整数个数是有限的，设为p p p p1 1 1 1,p ,p ,p ,p 2 2 2 2, , , , , , , ,p p p pk k k k 令：令：p p p p1 1 1 1p p p p2 2 2 2p p p pk k k k+1=N (N1)+1=N (N1)+1=N (N1)+1=N (N1) 则则N N N N有一个素数有一个素数p p p p，且
3、，且p p p pp p p pi i i i（i=1,2,i=1,2,i=1,2,i=1,2,k).,k).,k).,k). 故故p p p p是上述是上述k k k k个素数外的另外一个素数。个素数外的另外一个素数。 因此与假设矛盾。因此与假设矛盾。 2015-3-18 素数定义及素数个数定理素数定义及素数个数定理 3. 3. 3. 3.素数个数定理（素数个数定理（2 2 2 2）：）： 设设 (x)(x)(x)(x)是小于是小于x x x x的素数个数，则的素数个数，则 (x) (x) (x) (x) x / x / x / x / lnxlnxlnxlnx, , , , 即即x x x
4、 x时，比值时，比值 (x) /(x / (x) /(x / (x) /(x / (x) /(x / lnxlnxlnxlnx) ) ) ) 1 1 1 1 egegegeg: : : : 可以估算可以估算100100100100位素数的个数：位素数的个数： (10(10(10(10100 100100100) - ) - ) - ) - (10(10(10(1099 999999) ) ) ) 10 10 10 10100 100100100/(ln10 /(ln10/(ln10/(ln10100 100100100) ) ) ) 10 10 10 1099 999999/(ln10 /(l
5、n10/(ln10/(ln1099 999999) ) ) ) 3.9 3.9 3.9 3.9 * * * * 1097. 1097. 1097. 1097. 2015-3-18 1. 1. 1. 1.整数的唯一分解定理定理（算术基本定理）整数的唯一分解定理定理（算术基本定理）: : : : 设设n n n nZ Z Z Z， 有分解式，有分解式， n = n = n = n = p p p p1 1 1 1e1 e1e1e1p p p p2 2 2 2e2e2e2e2. . . .p p p pm mmmem ememem，其中 ，其中p p p p1 1 1 1, , , , p p p
6、p2 2 2 2, , , , , , , p p p pm mmm Z Z Z Z+ + + +是互不相同的素数，是互不相同的素数， e1,e2,e1,e2,e1,e2,e1,e2, , , ,ememememZ Z Z Z+ + + +, , , , 并且数对并且数对(p(p(p(p1 1 1 1, e1), (p, e1), (p, e1), (p, e1), (p2 2 2 2, e2), e2), e2), e2),(p,(p,(p,(pm mmm, , , , em ememem) ) ) )由由n n n n唯一确定（即唯一确定（即 如果不考虑顺序，如果不考虑顺序，n n n n
7、的分解是唯一的）的分解是唯一的）. . . . egegegeg: 504 = 2: 504 = 2: 504 = 2: 504 = 23 3 3 33 3 3 32 2 2 27, 7, 7, 7, 1125 = 3 1125 = 3 1125 = 3 1125 = 32 2 2 25 5 5 53 3 3 3 整数的唯一分解定理整数的唯一分解定理 2015-3-18 1. 1. 1. 1.定义定义 两个整数两个整数a a a a，b b b b的最大公约数，就是能同时整除的最大公约数，就是能同时整除a a a a 和和b b b b的最大正整数，记为的最大正整数，记为 gcd(a,bgcd
8、(a,bgcd(a,bgcd(a,b) ) ) )， 或，或，( ( ( (a,ba,ba,ba,b) ) ) )。 egegegeg: gcd(5,7) = 1: gcd(5,7) = 1: gcd(5,7) = 1: gcd(5,7) = 1， gcd(24,60) = 12gcd(24,60) = 12gcd(24,60) = 12gcd(24,60) = 12， 最大公约数定义及求法最大公约数定义及求法 2. 2. 2. 2. 求最大公约数的两种方法：求最大公约数的两种方法： (1)(1)(1)(1)因数分解：因数分解： egegegeg: 1728 = 2: 1728 = 2: 17
9、28 = 2: 1728 = 26 6 6 63 3 3 32 2 2 2，4536 = 24536 = 24536 = 24536 = 23 3 3 33 3 3 34 4 4 47, 7, 7, 7, gcd(1728, 4536) = 2 gcd(1728, 4536) = 2 gcd(1728, 4536) = 2 gcd(1728, 4536) = 2 3 3 3 33 3 3 32 2 2 2 = 72 = 72= 72= 72。 2015-3-18 (2) (2) (2) (2) 欧几里得欧几里得(Euclid)(Euclid)(Euclid)(Euclid)算法算法 设设a,
10、a, a, a, b b b b N N N N, ab0, , ab0, , ab0, , ab0, 用以下方法可求出用以下方法可求出 gcd(a,bgcd(a,bgcd(a,bgcd(a,b) ) ) )。 最大公约数的欧几里得算法最大公约数的欧几里得算法 . , )gcd( ,0 , )gcd( ,0 , )gcd( ,0 , )gcd()gcd( ,0 , 11 1112 32233321 2112221 1111 nnnn nnnnnnnn rqrr ,rrrrrqrr ,rrrrrqrr ,rrrrrqrb b,ra,bbrrbqa = =+= =+= =+= =+= + 2015
11、-3-18 EuclidEuclidEuclidEuclid算法实例：求算法实例：求 gcd(132, 108).gcd(132, 108).gcd(132, 108).gcd(132, 108). . . . .12121212 , , , ,121212122 2 2 224242424 ) ) ) )12121212, , , ,4 4 4 4gcd(2gcd(2gcd(2gcd(2 , , , ,12121212242424244 4 4 4108108108108 ) ) ) )24242424gcd(108gcd(108gcd(108gcd(108 , , , ,242424241
12、081081081081 1 1 1132132132132 ) ) ) )108108108108gcd(132gcd(132gcd(132gcd(132 = = = = = = = = = = = =+ + + + = = = = = = = =+ + + + = = = =, , , , , , , , 最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续） 2015-3-18 欧几里得算法（例欧几里得算法（例1 1 1 1） 11802 482216 4822 21650 2164 50 16 50 3 162 1620 8 gcdgcdgcdgcd（11801180118011
13、80，482482482482）2 2 2 2 求：求：gcdgcdgcdgcd（1180118011801180，482482482482） 最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续） 2015-3-18 欧几里得算法（例欧几里得算法（例2 2 2 2）：求）：求gcd(12345gcd(12345gcd(12345gcd(12345，1111111111111111) 123451111 11111234 5 4 41 0 gcd 1234511111 11234 95 12342464 511 4 （，） 最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续） 2
14、015-3-18 欧几里得算法抽象欧几里得算法抽象 11 2 12 13 23 24 34 21 11 b gcd( , ) kk kk kkk k aqbr q rr rq rr rq rr rq rr rqr a br + =+ =+ =+ =+ =+ = = 规律：余数除数被除 数忽略 最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续） 2015-3-18 欧几里得算法实现欧几里得算法实现 1 01 11 12 gcd( , ): ;1 0 1 ( ,.,) :gcd( , ) m m m r mr mmm m mm m a b ra rb m whiler do q rrq r mm returnq qqr commenta br + + = 算法 最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）
