应用密码学_第06章_数论基础

1、v素数与互素素数与互素v费马定理和欧拉定理费马定理和欧拉定理v中国剩余定理中国剩余定理v素性检测素性检测v整数中的基本概念：素数、最大公因数（整数中的基本概念：素数、最大公因数（gcd）、）、最小公倍数（最小公倍数（lcm）、互素）、互素v算术基本定理：任一大于算术基本定理：任一大于1的整数的整数a均能唯一地表均能唯一地表示为素数幂的乘积，即示为素数幂的乘积，即 其中其中pi是素数，是素数，ttpppa21210iv业余数学家之王业余数学家之王费马费马v费马大定理：当费马大定理：当n2时，方程时，方程xn + yn = zn不存在整不存在整数解。数解。vn=2时，勾股定理、商高定理、毕达哥拉斯

2、定理时，勾股定理、商高定理、毕达哥拉斯定理“不可能将一个立方数写成两个立方数之和；或者将不可能将一个立方数写成两个立方数之和；或者将一个一个4 4次幂写成两个次幂写成两个4 4次幂之和；或者，总的来说，次幂之和；或者，总的来说，不可能将一个高于不可能将一个高于2 2次的幂写成两个同样次幂的和。次的幂写成两个同样次幂的和。”“我有一个对这个命题的十分美妙的证明，这里空白我有一个对这个命题的十分美妙的证明，这里空白太小，写不下。太小，写不下。” 16371637，费马，费马v费马自己证明了费马自己证明了n=4的情况的情况v1753年，欧拉证明了年，欧拉证明了n=3的情况的情况v1853-1856年

3、，法国科学院设立年，法国科学院设立3000法朗奖金法朗奖金1847年，柯西与拉梅之争，化解者：德国数学家年，柯西与拉梅之争，化解者：德国数学家恩斯特恩斯特 库默尔库默尔1857年，奖金给了库默尔年，奖金给了库默尔库默尔指出：算术基本定理在复数中不成立库默尔指出：算术基本定理在复数中不成立 121111112828iiiiv德国实业家保罗德国实业家保罗沃尔夫斯凯尔的工作沃尔夫斯凯尔的工作v1908年立下遗嘱：财产中的一大部分奖给任何能年立下遗嘱：财产中的一大部分奖给任何能证明费马大定理的人，奖金为证明费马大定理的人，奖金为10万马克，万马克， v截止日期：截止日期：2007年年9月月13日。日。

4、 v1997年年6月月27日，安德鲁日，安德鲁怀尔斯收到了价值怀尔斯收到了价值5万美万美元的沃尔夫斯凯尔奖金。元的沃尔夫斯凯尔奖金。 v推荐阅读：推荐阅读：v费马大定理费马大定理一个困惑了世间智者一个困惑了世间智者358年的年的谜谜，（英）西蒙，（英）西蒙辛格（辛格（SimonSingh）著，薛密）著，薛密译上海译文出版社译上海译文出版社v费马小定理：若费马小定理：若p是素数，是素数，p不整除不整除a，则，则a p-11 mod pv等价形式：等价形式：a pa mod pv例：设例：设p=23， a=2，则由，则由Fermat定理直接可得定理直接可得 222 1 mod 23证证 明明v首先

5、证明，首先证明，1ip-1时，时，p整除二项式系数整除二项式系数 显然显然p整除分子。由于整除分子。由于0ip，所以素数，所以素数p不整除所有在分不整除所有在分母中阶乘的因子。根据素数因子分解的唯一性，母中阶乘的因子。根据素数因子分解的唯一性，p不能整不能整除分母。除分母。 根据二项式定理根据二项式定理 ，由于所有二项式，由于所有二项式系数都是整数，系数都是整数， 0ip时，二项式系数是整数并且其分式时，二项式系数是整数并且其分式形式中的分子可以被形式中的分子可以被p整除，而分母不能被整除，而分母不能被p整除，所以，整除，所以，在分式化简完成后，分子中肯定存在因子在分式化简完成后，分子中肯定存

6、在因子p。!ppiipi0pip ii ppxyx yi 对对 x 归纳：首先，显然归纳：首先，显然 1p1 mod p，假设对某，假设对某个特定的整数个特定的整数 x，有，有 x p x mod p，则，则00111pip ipii pi pppxxxxii 等式右边的中间部分的所有系数整除等式右边的中间部分的所有系数整除p，因此，因此 这就证明了费马定理。这就证明了费马定理。10 11modppxxxp v欧拉函数：对于正整数欧拉函数：对于正整数n，欧拉函数，欧拉函数(n)定义为小于定义为小于n且且与与n互素的正整数个数。互素的正整数个数。v性质：性质：（1） (1)=1（2）n为素数时，

7、为素数时， (n)=n-1；（3）(2k)= 2k-1 ；（4）若）若n=pq 且且gcd (p, q)=1，则，则(n)= (p) (q)（5）若，则）若，则tataapppn2121 111211121121tataappppppntv定理：对任意整数定理：对任意整数a, n，当，当gcd(a, n)=1时，有时，有 a(n)1 mod nv等价形式：等价形式：a(n)1a mod nv推论：给定两个素数推论：给定两个素数p, q，整数，整数n=pq和和m，其中，其中 0mn，则有则有m(n)+1m(p-1)(q-1)+1m mod nv丢番图（丢番图（Diophantine，古希腊数学家

8、，约公元前，古希腊数学家，约公元前250年）年）（Chinese Remainder TheoremChinese Remainder Theorem）上帝恩赐他生命的上帝恩赐他生命的1/61/6为童年，再过生命的为童年，再过生命的1/121/12，他双颊长出了胡子，再过他双颊长出了胡子，再过1/71/7后他举行了婚礼，后他举行了婚礼，婚后婚后5 5年他有了一个儿子。唉，可怜的孩子，年他有了一个儿子。唉，可怜的孩子，只活了他父亲整个生命的一半年纪，便被冷酷只活了他父亲整个生命的一半年纪，便被冷酷的死神带走。他以研究数论寄托他的哀思，的死神带走。他以研究数论寄托他的哀思，4 4年后离开了人世。年

9、后离开了人世。 x-x/6+x/12+x/7+5+x/2+4=0 x-x/6+x/12+x/7+5+x/2+4=0v丢番图方程，整系数多项式方程：变量为整丢番图方程，整系数多项式方程：变量为整数的多项式等式。数的多项式等式。v一般形式：一般形式：cxaxaxanbnnbb212211公元公元3-53-5世纪，世纪，孙子算经孙子算经： “今有物不知其数，三三数之剩二，五五数之剩三，今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？七七数之剩二，问物几何？” 术曰：三三数之剩二，置一百四十；五五数之剩三，置术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三

10、十；并之得二百三十三；以六十三；七七数之剩二，置三十；并之得二百三十三；以二百一十减之即得。凡三三数之剩一，则置七十；五五数二百一十减之即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六之剩一，则置二十一；七七数之剩一，则置十五；一百六以上，以一百五减之即得。以上，以一百五减之即得。 程大位，算法统宗（程大位，算法统宗（15031503） 三人同行七十稀，三人同行七十稀， 五树梅花廿一枝，五树梅花廿一枝， 七子团圆正月半，七子团圆正月半， 除百零五便得知。除百零五便得知。n = 70*2+21*3+15*2 mod 105 =23v设设a, b, c 的最

11、大公约数为的最大公约数为d，则存在整数，则存在整数x, y, z，使得使得ax+by+cz=dv在方程组中，模数在方程组中，模数3、5、7互素，而互素，而3*5=15、5*7=35和和3*7=21也是互素的，故存在整数也是互素的，故存在整数x, y, z，使得使得35x+21y+15z=1v令令e1=35x, e2=21y, e3=15z，则显然有，则显然有1111mod 30mod 50mod 7eee2220mod 31mod 50mod 7eee3330mod 30mod 51mod 7eeen = e1*2+e2*3+e3*2 mod 105v由于（由于（3, 35）=1，故存在整数，

12、故存在整数a, b，使得，使得3a+35b=1v而而v故可令故可令e1=35b，而其中的，而其中的b为为35模模3的逆元。的逆元。351mod 3350mod 5350mod 7bbbv一次同余方程组的一般形式：一次同余方程组的一般形式：v如果如果m1, m2, , mk两两互素，则可利用中国剩余两两互素，则可利用中国剩余定理求解。定理求解。1122modmodmodkkxamxamxam第一步，计算第一步，计算M=m 1m 2m k，以及，以及Mi=M/mi；第二步，求出各第二步，求出各Mi 模模mi 的逆，即计算的逆，即计算Mi-1，使得，使得M iM i-11 mod mi；第三步，计算

13、第三步，计算x=M i Mi-1 a1+M kM k -1ak mod M则则 x 即即为方程组的一个解。为方程组的一个解。 除数除数mi余余数数ai最小公倍最小公倍数数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数m1a1M=m1 m2 mkM1M1-1m2a2M2M2-1mkakMkMk-1v解解“物不知其数物不知其数”的方程组的方程组(1) 计算：计算：M357105， M135，M221，M315 再求出再求出 M112， M211， M311 最后求得最后求得x23 mod 105除数除数mi余数余数ai最小公倍最小公倍数数衍数衍数Mi = M/mi乘率乘率

14、Mi-1ci各总各总ai ci答数答数32M=3*5*7=1055*725*7*270*2140+63+30=23323 mod 105537*317*3*121*3723*513*5*115*2v练习：解同余方程组练习：解同余方程组1mod 72mod 83mod 9xxx1mod 42mod 53mod 7xxxx = 498x = 498x = 17x = 17v练习：求相邻的四个整数，依次可被练习：求相邻的四个整数，依次可被22、32、52、72整除整除 vM=mM=m1 1* *m m2 2=37=37* *49=1813,(37,49)=149=1813,(37,49)=19739

15、73可用较小的两个模数可用较小的两个模数3737和和4949重构，表示为重构，表示为(11(11，42) 42) （1111* *4949* *34+4234+42* *3737* *4=1 mod 18134=1 mod 1813）678678可表示为可表示为(12(12，41)41)则则1651=973+6781651=973+678就可表示为就可表示为 (11+12)mod37,(42+41)mod49)=(23,34)(11+12)mod37,(42+41)mod49)=(23,34)则则120523=1651120523=1651* *7373就可表示为就可表示为 (23(23* *

16、36mod37,3436mod37,34* *24mod49)=(14,32)24mod49)=(14,32)v vWilson阶乘判别法阶乘判别法vwilson定理：定理：P是素数是素数 v证明：证明：（ 1，所以不可，所以不可能得到能得到(p 1)! 1 (mod p)。)(mod1)!1(ppv证明：证明：（ = ）vp=2，命题显然成立；，命题显然成立；vp=3，命题显然成立；，命题显然成立；v对于对于p5，令，令aA=2, 3, 4. p-2，则，则B=a, 2a, 3a, ., (p-1)a中不会有模中不会有模p同余的两个数。因此，同余的两个数。因此，B中元素被中元素被p除得的余数

17、形成集合除得的余数形成集合1, 2, 3,., p-1.v假设假设B中元素被中元素被p除余除余1的数是的数是a：若若=1，则则a=a，它被，它被p除余除余a，所以，所以=1不成立；不成立；若若=p-1，则，则a=(p-1)a，它被，它被p除余除余p-a,所以所以=p-1不成不成立；立；若若=a，则，则a=a*a，由于，由于a*a1(mod p)，故应有，故应有a*a-1=(a+1)(a-1)0(mod p)，这只能是，这只能是a=1或或a=p-1，与，与aA矛盾，故不成立；矛盾，故不成立；因此，因此，a且且a, A。若若a1a2, a1, a2A，且，且1a12a21(mod p），因为），因

18、为1a1，2a2B，而，而B中的元素关于中的元素关于mod p不同余，可见不同余，可见a1a2,则则12。即即A中的每一个中的每一个a均可找到与其配对的均可找到与其配对的 ，A使使a 1(mod p)。 a不同时，不同时，也相异；也相异；因此，因此，A中的偶数个（中的偶数个（p-3个）元素可以分成个）元素可以分成(p-3)/2个个二元组（二元组（a, ），每个二元组都满足），每个二元组都满足a 1(mod p)；234.(p-2)1(mod p)，p-1-1(mod p) (p-1)!-1(mod p)v更快的素性检测：仅仅能够得知更快的素性检测：仅仅能够得知n是否为合数，而不能是否为合数，而

19、不能求出其因子。求出其因子。v实际中使用的方法：先生成大的随机整数，再利用某实际中使用的方法：先生成大的随机整数，再利用某些算法来检测其素性。些算法来检测其素性。v定理：素数有无穷多个定理：素数有无穷多个 证明：用反证法证明：用反证法 假设素数个数有限，设全部的素数为假设素数个数有限，设全部的素数为p1, p2, , pn，令，令N=p1p2pn+1, 由算术基本定理，由算术基本定理，N可以分解为素数的乘可以分解为素数的乘积，故一定存在素数积，故一定存在素数p能整除能整除N。因而对某个。因而对某个pi，1in，p=pi ，从而，从而p能整除能整除N-p1p2pn=1，显然这是不可能的。，显然这

20、是不可能的。 17世纪，人们发现：世纪，人们发现：31, 331, 3331, 33 331, 333 331, 3 333 331, 33 333 331都是素数，然而都是素数，然而33 333 331=17*19 607 843v0-100之间有之间有25个素数个素数v1000 0000与与1000 0100之间只有之间只有2个素数个素数20004000600080001000020040060080010001200v素数定理是数论中一个著名的结论，它是素数定理是数论中一个著名的结论，它是18961896年年由由HadamardHadamard和和la Valle-Poussinla V

21、alle-Poussin分别独立证明分别独立证明的。根据该定理，如果在的。根据该定理，如果在0 0到到x x之间随机选取一个之间随机选取一个整数，其为素数的概率约为整数，其为素数的概率约为1/lnx 1/lnx ，因此，生成，因此，生成“可能为素数可能为素数”的大整数是可行的。的大整数是可行的。 xxxxlnlim定理（素数定理）令定理（素数定理）令(x)(x)表示比表示比x x小的素数的个数，则小的素数的个数，则 v方法一：费马定理方法一：费马定理根据费马定理，当根据费马定理，当p为素数时，对任意整数为素数时，对任意整数a，且且p不整除不整除a，有，有a p-11 mod p .(1)逆否命

22、题：若存在逆否命题：若存在a，使得，使得(1)式不成立，则式不成立，则p必必为合数为合数合数判别的充分条件合数判别的充分条件如果如果p不是素数，而不是素数，而(1)仍然成立，则称仍然成立，则称p为关于为关于基底基底a的的伪素数。伪素数。v341，91和和217是关于基底是关于基底2，3和和5的最小伪素数的最小伪素数v费马定理只是素数判定的一个必要条件。费马定理只是素数判定的一个必要条件。v对某个对某个a，如果数，如果数p使使(1)成立，则称其通过了基数成立，则称其通过了基数为为a的伪素数测试。通过若干次伪素数测试的数在的伪素数测试。通过若干次伪素数测试的数在概率上是一个素数。概率上是一个素数。

23、v如果对所有如果对所有ap，gcd(a, p)=1，p均能通过基数为均能通过基数为a的伪素数测试，却仍为合数，则称的伪素数测试，却仍为合数，则称p为为Carmichael数数。最小的三个最小的三个Carmichael数：数：561，294409，56052361Carmichael数非常稀少，在数非常稀少，在1100,000,000范围内的整范围内的整数中，只有数中，只有255个个Carmichael数。数。1992年，年，Alford，Granville和和Pomerance证明了存在无证明了存在无限多个限多个Carmichael数。数。v为了提高素数测试的准确性，可以多次随机选取为了提高素

24、数测试的准确性，可以多次随机选取小于小于n的正整数的正整数a，重复计算，重复计算an-1 mod n来判定来判定n是是否是素数。否是素数。v例如，对于例如，对于341，取，取a=3，则，则3340 mod 34156，从，从而判定而判定341不是素数。不是素数。int ExpMod(int n) /int ExpMod(int n) /计算计算a an n-1-1 mod mod n n a=Random(2, n-1); / a=Random(2, n-1); /产生产生2, n-12, n-1之间的随机整数之间的随机整数 b=1;b=1; for (i=1; i=n-1; i+) for

25、(i=1; i2，如果对，如果对n-1的每个素因子的每个素因子p，存在一个整数存在一个整数a(a1)，使得，使得且且则则n是素数是素数nanmod11napnmod11 v证明思路：证明思路：只要证明此时只要证明此时 ，也就是，也就是 | |p-1,p-p-1,p-1| ,1| ,先证先证p-1p-1| | ，反证：设反证：设 | |p-1,p-1,且且 | | ，设，设ordordp p( (a ai i)=k)=ki i则则k ki i| |p-1, kp-1, ki i|(p-1/p|(p-1/pi i) )所以所以 p pi i| |k ki i，否则否则k ki i|(p-1/p|(

26、p-1/pi i) )所以所以 | |k ki i，否则设否则设 | |k ki i(0(0jr),(p-1/pjr-1r-jr-1，所以，所以j1j1，所以，所以j=0j=0因为因为k ki i| | ，所以，所以 | | 矛盾，所以矛盾，所以p-1p-1| |再因为再因为 = 1时，时，0pa当（当（a, p）1时，时，1pa2121papappa(4)当（当（a, p）=1时，时，122papavJacobi符号的计算符号的计算v定理（定理（Gauss二次互反律）设二次互反律）设p、q为互素的奇数，为互素的奇数，则则补充知识：补充知识：JacobiJacobi符号符号21211qpqppqv引理引理1 如果如果n是奇素数，则对所有是奇素数，则对所有a，1an-1，有有v引理引理2 如果如果n是奇合数，则至多有一半满足是奇合数，则至多有一半满足1an-1 和和 gcd(a, n)=1的整数的整数a满足上式满足上式 。 12modnaann补充知识：补充知识：JacobiJacobi符号符号v开发者：开发者：Robert Solovay和和Volker Strassenv算法步骤算法步骤I 随机选取整数随机选取整数a，使得，使得 1an-1；II 如果如果a与与n