初等数论§3同余

《初等数论§3同余》由会员分享，可在线阅读，更多相关《初等数论§3同余（88页珍藏版）》请在金锄头文库上搜索。

1、2024/7/271第三章第三章 同同 余余 同余是数论中的重要概念，同余理论是研究整数同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一问题的重要工作之一. .本章介绍同余的基本概念，剩本章介绍同余的基本概念，剩余类和完全剩余系余类和完全剩余系. . 生活中我会经常遇到与余数有关的问题，比如：生活中我会经常遇到与余数有关的问题，比如：某年级有将近某年级有将近400400名学生。有一次演出节目排队时出名学生。有一次演出节目排队时出现：如果每现：如果每8 8人站成一列则多余人站成一列则多余1 1人；如果改为每人；如果改为每9 9人人站成一列则仍多余站成一列则仍多余1 1人；结果发现现成

2、每人；结果发现现成每1010人结成一人结成一列，结果还是多余列，结果还是多余1 1人；聪名的你知道该年级共有学人；聪名的你知道该年级共有学生多少名吗？生多少名吗？2024/7/2723.13.1同余的概念及其基本性质同余的概念及其基本性质 一、问题的提出一、问题的提出1 1、今天是星期一，再过、今天是星期一，再过100100天是星期几？天是星期几？ 3、13511，13903，14589被自然数被自然数m除所得余数除所得余数 相同，问相同，问m最大值是多少？最大值是多少？ 2 2、314592653=2910 93995314592653=2910 93995的横线处漏写了一个的横线处漏写了一

3、个 数字，你能以最快的办法补出吗？数字，你能以最快的办法补出吗？2024/7/273二、同余的定义二、同余的定义注：下面的三个表示是等价的：注：下面的三个表示是等价的：2024/7/27阜阳师范学院 数科院4三、同余的性质三、同余的性质TH2设设a，b，c，d，k是整数，并且是整数，并且 a b (mod m)， c d (mod m)， 则则 a c b d (mod m)； ac bd (mod m); ak bk (mod m).注：注：TH1、TH2是最是最简单简单、常用的性、常用的性质质。2024/7/27阜阳师范学院 数科院52024/7/27阜阳师范学院 数科院6TH4 TH4

4、下面的结论成立：下面的结论成立： a b (mod m)，d m，d 0 a b (mod d)； a b (mod m)，k 0，k N ak bk (mod mk)； a b (mod mi )，1 i k a b (mod m1, m2, , mk)； a b (mod m) (a, m) = (b, m)； ac bc (mod m)，(c, m) = 1 a b (mod m);2024/7/27阜阳师范学院 数科院7 a b (mod m)，d m，d 0 a b (mod d)； a b (mod m)，k 0，k N ak bk (mod mk)； a b (mod mi )，

5、1 i k a b (mod m1, m2, , mk)； a b (mod m) (a, m) = (b, m)；2024/7/27阜阳师范学院 数科院8 ac bc (mod m)，(c, m) = 1 a b (mod m);注：若没有条件注：若没有条件(c, m) = 1，即，即为为TH2的逆命的逆命题题， 不能成立。不能成立。反例：取反例：取m=6,c=2,a=20,b=23.2024/7/27阜阳师范学院 数科院92024/7/27阜阳师范学院 数科院10四、一些整数的整除特征四、一些整数的整除特征 (1)(1) 3 3、9 9 的整除特征的整除特征各位上的数字之和能被各位上的数字

6、之和能被3 3（9 9）整除）整除例例1检查检查5874192、435693能否被能否被3（9）整除。）整除。2024/7/27阜阳师范学院 数科院11(2) 7(2) 7、1111、13 13 的整除特征的整除特征注：一般地，求注：一般地，求 被被m除的余数除的余数时时， 首先是求出正整数首先是求出正整数k，使得，使得 10k 1或或1 (mod m)， 2024/7/27阜阳师范学院 数科院12(2) 7(2) 7、1111、13 13 的整除特征的整除特征特别地，由于特别地，由于 ，所以，所以奇偶位差法奇偶位差法 例例2检查检查637693、75312289能否被能否被7（11，13）整

7、除。）整除。由由69363756，所以，所以637693能被能被7整除，但不能被整除，但不能被11，13整除，整除， 当然也可以由当然也可以由6+3-7+6-9+3=2知知637693不能被不能被11整除；整除； 由由75-312+28952，所以，所以75312289能被能被13整除，但不整除，但不能被能被7，11整除。整除。 2024/7/27阜阳师范学院 数科院132024/7/27阜阳师范学院 数科院14 求出整数求出整数k，使，使ak 1 (mod m)； 求出正整数求出正整数r，r 0是偶数，是偶数，a1, a2, , am与与b1, b2, , bm都是模都是模m的完全剩余系，的

8、完全剩余系， 则则a1 b1, a2 b2, , am bm不是模不是模m的完全剩余系。的完全剩余系。 证证 由由1, 2, , m与与a1, a2, , am都是模都是模m的完全剩余系，的完全剩余系， 如果如果a1 b1, a2 b2, , am bm是模是模m的完全剩余系，的完全剩余系， 不可能！不可能！2024/7/27阜阳师范学院 数科院39例例4 设设mi N（1 i n），），则则当当xi通通过过模模mi（1 i n） 的完全剩余系时，的完全剩余系时，x = x1 m1x2 m1m2x3 m1m2mn 1xn通通过过模模m1m2mn的完全剩余系。的完全剩余系。证证明明 对对n施行施

9、行归纳归纳法。法。当当n = 2时时，由定理，由定理4知定理知定理结论结论成立。成立。假假设设定理定理结论结论当当n = k时时成立，成立， 即当即当xi（2 i k 1）分）分别别通通过过模模mi的完全剩余系的完全剩余系时时，y = x2 m2x3 m2m3x4 m2mkxk 1通通过过模模m2m3mk 1的完全剩余系。的完全剩余系。 2024/7/27阜阳师范学院 数科院40y = x2 m2x3 m2m3x4 m2mkxk 1通通过过模模m2m3mk 1的完全剩余系。的完全剩余系。 由定理由定理4，当，当x1通通过过模模m1的完全剩余系，的完全剩余系， xi（2 i k 1）通）通过过模

10、模mi的完全剩余系的完全剩余系时时，x1 m1y = x1 m1(x2 m2x3 m2mkxk 1)= x1 m1x2 m1m2x3 m1m2mkxk 1通通过过模模m1m2mk 1的完全剩余系。的完全剩余系。 即即结论对结论对于于n = k 1也成立。也成立。 2024/7/27阜阳师范学院 数科院41三、与抽象代数的关系三、与抽象代数的关系若将模若将模m的剩余的剩余类类作作为为元素，元素，则则 同余同余剩余剩余类类的相等，的相等，同余的运算同余的运算元素元素剩余剩余类类的运算，的运算，剩余类的集合即是环。剩余类的集合即是环。 特特别别地，当地，当m为为合数合数时时，就有：，就有： 非零的剩

11、余非零的剩余类类的乘的乘积积可能可能为为零的剩余零的剩余类类，即存在零因子的环。即存在零因子的环。上述上述环环中所有与模中所有与模m互互质质的剩余的剩余类对类对乘法构成群；乘法构成群；当当m为质为质数数时时，上述的，上述的环环又可以构成一个有限域。又可以构成一个有限域。2024/7/27阜阳师范学院 数科院422024/7/27阜阳师范学院 数科院433.3 3.3 简化剩余系与欧拉函数简化剩余系与欧拉函数 一、基本概念一、基本概念定定义义1 设设R是模是模m的一个剩余的一个剩余类类，若有，若有a R，使得，使得(a, m)= 1，则则称称R是模是模m的一个的一个简简化剩余化剩余类类。即与模即

12、与模m互互质质的剩余的剩余类类。 注：若注：若R是模的是模的简简化剩余化剩余类类，则则R中的数都与中的数都与m互素。互素。例如，模例如，模4的的简简化剩余化剩余类类有两个：有两个：R1(4) = , 7 , 3, 1 , 5 , 9 , ，R3(4) = , 5 , 1 , 3 , 7 , 11 , 。2024/7/27阜阳师范学院 数科院44定定义义2 对对于正整数于正整数k，令函数，令函数 (k)的的值值等于模等于模k的所有的所有简简化剩余化剩余类类的个数，称的个数，称 (k)为为Euler函数。函数。容易容易验证验证： (2) = 1， (3) = 2， (4) = 2， (7) = 6

13、。注：注： (m)就是在就是在m的一个完全剩余系中与的一个完全剩余系中与m互素的互素的 整数的个数，且整数的个数，且 定定义义3 对对于正整数于正整数m，从模，从模m的每个的每个简简化剩余化剩余类类中中 各取一个数各取一个数xi，构成一个集合，构成一个集合x1, x2, ,x (m)， 称称为为模模m的一个的一个简简化剩余系（或化剩余系（或简简称称为简为简化系）。化系）。 2024/7/27阜阳师范学院 数科院45注：由于注：由于选选取方式的任意性，模取方式的任意性，模m的的简简化剩余系化剩余系有无穷多个。有无穷多个。例如，集合例如，集合9, 5, 3, 1是模是模8的的简简化剩余系；化剩余系

14、； 集合集合1, 3, 5, 71, 3, 5, 7也是模也是模8 8的简化剩余系的简化剩余系. . 集合集合1, 3, 5, 71, 3, 5, 7称为最小非负简化剩余系。称为最小非负简化剩余系。 2024/7/27阜阳师范学院 数科院46二、主要性质二、主要性质 定理定理1 整数集合整数集合A是模是模m的的简简化剩余系的充要条件是：化剩余系的充要条件是： A中含有中含有 (m)个整数；个整数； A中的任何两个整数中的任何两个整数对对模模m不同余；不同余； A中的每个整数都与中的每个整数都与m互素。互素。说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素

15、构成的集合，故构成的集合，故满满足条件足条件2； 由定由定义义1易知易知满满足条件足条件3；由定义由定义3 3易知满足条件易知满足条件1 1。2024/7/27阜阳师范学院 数科院47定理定理2 设设a是整数，是整数，(a, m) = 1，B = x1, x2, , x (m) 是模是模m的的简简化剩余系，化剩余系，则则集合集合 A = ax1, ax2, , ax (m) 也是模也是模m的的简简化剩余系。化剩余系。证证明明 显显然，集合然，集合A中有中有 (m)个整数。个整数。 由于由于(a, m) = 1， 对对于任意的于任意的xi（1 i (m)），xi B， 有有(axi, m) =

16、(xi, m) = 1。 故故A中的每一个数都与中的每一个数都与m互素。互素。 而且，而且，A中的任何两个不同的整数中的任何两个不同的整数对对模模m不同余。不同余。 因因为为，若有，若有x , x B，使得，使得 a x ax (mod m)，那么，那么， x x (mod m)， 于是于是x = x 。 由以上由以上结论结论及定理及定理1可知集合可知集合A是模是模m的一个的一个简简化系。化系。 2024/7/27阜阳师范学院 数科院48注：在定理注：在定理2的条件下，若的条件下，若b是整数，集合是整数，集合ax1 b, ax2 b, , ax (m) b不一定是模不一定是模m的的简简化剩余系

17、。化剩余系。 例如，取例如，取m = 4，a = 1，b = 1， 以及模以及模4的的简简化剩余系化剩余系1, 3。但但2 2，4 4不是模不是模4 4的简化剩余系。的简化剩余系。2024/7/27阜阳师范学院 数科院49定理定理3 设设m1, m2 N，(m1, m2) = 1，又，又设设分分别别是模是模m1与与m2的的简简化剩余系，化剩余系， 则则 A = m1y m2x；x X，y Y 是模是模m1m2的的简简化剩余系。化剩余系。证明证明 由第二节定理由第二节定理3 3推论可知，推论可知， 若以若以X 与与Y 分分别别表示表示 模模m1与与m2的完全剩余系，使得的完全剩余系，使得X X

18、，Y Y ， 则则A = m1y m2x；x X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。 因此只需因此只需证证明明A 中所有与中所有与m1m2互素的整数的集合互素的整数的集合R 即模即模m1m2的的简简化剩余系是集合化剩余系是集合A。 2024/7/27阜阳师范学院 数科院50若若m1y m2x R，则则(m1y m2x, m1m2) = 1， 所以所以(m1y m2x, m1) = 1， 于是于是 (m2x, m1) = 1，(x, m1) = 1，x X。同理可得到同理可得到y Y，因此，因此m1y m2x A。 这说这说明明R A。 另一方面，若另一方面，若m1y m2

19、x A，则则x X，y Y， 即即 (x, m1) = 1，(y, m2) = 1。由此及由此及(m1, m2) = 1得到得到 (m2x m1y, m1) = (m2x, m1) = 1(m2x m1y, m2) = (m1y, m2) = 1。因因为为m1与与m2互素，所以互素，所以(m2x m1y, m1m2) = 1， 于是于是m2x m1y R。因此。因此A R。 从而从而A = R。 2024/7/27阜阳师范学院 数科院51推推论论 设设m, n N，(m, n) = 1，则则 (mn) = (m) (n)。证证 由定理由定理3知，若知，若x,y分分别别通通过过m , n的的简简

20、化剩余系，化剩余系， 则则my nx通通过过mn的的简简化剩余系，化剩余系， 即有即有 my nx通通过过 (mn)个整数。个整数。 另一方面，另一方面，xnx通通过过 (m)个整数，个整数， ymy通通过过 (n)个整数个整数, 从而从而my nx通通过过 (m) (n)个整数。个整数。故有故有 (mn) = (m) (n)。注：可以推广到多个两两互质数的情形。注：可以推广到多个两两互质数的情形。2024/7/27阜阳师范学院 数科院52定理定理4 设设n是正整数，是正整数，p1, p2, , pk是它的全部素因数，是它的全部素因数， 证证 设设n的的标标准分解式是准分解式是 由定理由定理3

21、 3推论得到推论得到 对对任意的素数任意的素数p， (p )等于数列等于数列1, 2, , p 中与中与p 互素的整数的个数，互素的整数的个数， 从而定理得证。从而定理得证。2024/7/27阜阳师范学院 数科院53注：由定理注：由定理4可知，可知， (n) = 1的充要条件是的充要条件是n = 1或或2。考考虑虑有重素因子和没有重素因子的情形。有重素因子和没有重素因子的情形。 三、应用举例三、应用举例注意：有重素因子时，上述不等式中等号不成立！注意：有重素因子时，上述不等式中等号不成立！2024/7/27阜阳师范学院 数科院54例例1 设设整数整数n 2，证证明：明： 即在数列即在数列1,

22、2, , n中，与中，与n互素的整数之和是互素的整数之和是 证证 设设在在1, 2, , n中与中与n互素的互素的个数是个数是 (n)，a1, a2, , a (n)，(ai, n) = 1，1 ai n 1，1 i (n)，则则 (n ai, n) = 1，1 n ai n 1，1 i (n)，因此，集合因此，集合a1, a2, , a (n)故故 a1 a2 a (n) = (n a1) (n a2) (n a (n)，从而，从而，2(a1 a2 a (n) = n (n)，因此因此 a1 a2 a (n) 与集合与集合n a1, n a2, , n a (n)是相同的，是相同的，2024

23、/7/27阜阳师范学院 数科院55例例2 设设n N，证证明：明：1) 若若n是奇数，是奇数，则则 (4n) = 2 (n)；的充要条件是的充要条件是n = 2k，k N；的充要条件是的充要条件是n = 2k3l，k, l N；4) 若若6 n，则则 (n) 5) 若若n 1与与n 1都是素数，都是素数，n 4，则则 (n) 2024/7/27阜阳师范学院 数科院561) 若若n是奇数，是奇数，则则 (4n) = 2 (n)； (4n) = (22n)= (22) (n)= 2 (n)TH42024/7/27阜阳师范学院 数科院57的充要条件是的充要条件是n = 2k，k N；若若n = 2k

24、， 若若 (n) = 设设n = 2kn1， 由由 (n) = (2kn1) = (2k) (n1) =2k 1 (n1) 所以所以n1 = 1，即，即n = 2k；2024/7/27阜阳师范学院 数科院58的充要条件是的充要条件是n = 2k3l，k, l N；设设 n = 2k3ln1， 所以所以n1 = 1，即，即n = 2k3l；若若 n = 2k3l，则则 (n) = (2k) (3l)2024/7/27阜阳师范学院 数科院594) 若若6 n，则则 (n) 设设 n = 2k3ln1， 则则 (n) = (2k) (3l) (n1) 2024/7/27阜阳师范学院 数科院605)

25、若若n 1与与n 1都是素数，都是素数，n 4，则则 (n) 因因为为n 4，且，且n 1与与n 1都是奇素数，都是奇素数， 所以所以n是偶数，且是偶数，且n 1 3.所以所以n 1与与n 1都不等于都不等于3，所以所以3 n，由由结论结论4，也不能被也不能被3 3整除，整除，因此因此6 n。即可得到结论即可得到结论5 5。若若6 n，则则 (n) 2024/7/27阜阳师范学院 数科院61例例3 证证明：若明：若m, n N，则则 (mn) = (m, n) (m, n)；证证： 显显然然mn与与m, n有相同的素因数，有相同的素因数， 设设它它们们是是pi（1 i k），），则则由此两式及

26、由此两式及mn = (m, n)m, n即可得即可得证证。2024/7/27阜阳师范学院 数科院623.43.4欧拉定理欧拉定理 费马定理及其对循环小数的应用费马定理及其对循环小数的应用 本本节节主要通主要通过应过应用用简简化剩余系的性化剩余系的性质证质证明数明数论论中中的两个重要定理，欧拉定理和的两个重要定理，欧拉定理和费马费马定理，并定理，并说说明其在明其在理理论论和解决和解决实际问题实际问题中的中的应应用。用。2024/7/27阜阳师范学院 数科院63一、两个基本定理一、两个基本定理定理定理1 Euler 设设 m是正整数，是正整数，(a, m) = 1， 则则 a m) 1 (mod

27、m).证证明：明： 设设x1, x2, , x (m)是模是模m的一个的一个简简化剩余系，化剩余系， 则则ax1, ax2, , ax (m)也是模也是模m的的简简化剩余系，化剩余系， 所以所以 ax1ax2ax (m) x1x2 x (m) (mod m)，即即 a (m)x1x2x (m) x1x2, x (m) (mod m). 得得 (x1x2x (m), m) = 1， 所以所以 a (m) 1 (mod m). 2024/7/27阜阳师范学院 数科院64定理定理2(Fermat) 设设p是素数，是素数， a p a (mod p)。 注：注：FermatFermat定理即是欧拉定理

28、的推论。定理即是欧拉定理的推论。证证： 由于由于p是素数，是素数， 若若 (a, p) 1， 则由定理则由定理1 1得到得到 a p 1 1 (mod p) a p a (mod p) 若若(a, p) 1，则则p a， 所以所以 a p 0 a (mod p) a m) 1 (mod m)2024/7/27阜阳师范学院 数科院65二、定理的应用举例二、定理的应用举例例例1 求求313159被被7除的余数。除的余数。解：解：313159所以由欧拉定理得所以由欧拉定理得 a m) 1 (mod m)从而从而 5159= (56)2653 53 (mod 7) 53 = 25 5 4 5 6 (m

29、od 7)。即即 313159被被7除的余数除的余数为为6。2024/7/27阜阳师范学院 数科院66例例2 设设n是正整数，是正整数，则则5 1n 2n 3n 4n的充要条件是的充要条件是4 n。证证： 因因为为 (5) = 4， 由定理由定理1 1得得 a m) 1 (mod m)k4 1 (mod 5)，1 k 4。因此，因此，记记n = 4q r，0 r 3， 则则 1n 2n 3n 4n 1r 2r 3r 4r 1r 2r ( 2)r ( 1)r (mod 5). 用用 r = 0，1，2，3分分别别代入即可得出代入即可得出结论结论。2024/7/27阜阳师范学院 数科院67例例3

30、设设x1, x2, , x (m)是模是模m的的简简化剩余系，化剩余系， 则则 (x1x2x (m)2 1 (mod m).证证： 记记P = x1x2x (m)， 则则(P, m) = 1. 1 i (m)，则则y1, y2, , y (m)也是模也是模m的的简简化剩余系，化剩余系， 再由再由Euler定理得定理得证证.a m) 1 (mod m)2024/7/27阜阳师范学院 数科院68例例4 设设a，b，c，m是正整数，是正整数，m 1，(b, m) = 1， 并且并且 b a 1 (mod m)，b c 1 (mod m)， 记记d = (a, c)，则则bd 1 (mod m)。证证

31、 利用利用辗转辗转相除法可以求出整数相除法可以求出整数x，y，使得使得ax cy = d， 显显然然xy 0，y 0， 则则 1 b ax= b db cy= b d(b c) y b d (mod m)若若x 0， 则则 1 b cy= b db ax= b d(ba) x b d (mod m)。2024/7/27阜阳师范学院 数科院69例例5 设设n是正整数，是正整数，记记Fn = 证证： 容易容易验证验证，当，当n 4时时Fn是素数，是素数， 由由FermatFermat定理可知结论显然成立。定理可知结论显然成立。a p a (mod p)。 当当n 5时时，有，有n 1 2n， 其中

32、其中Q1与与Q2是整数，是整数， 2024/7/27阜阳师范学院 数科院70补充说明补充说明我我们们已已经经知道，知道，F5是合数，因此例是合数，因此例5表明，表明， Fermat定理的逆定理不成立。定理的逆定理不成立。 设设p是素数，是素数， a p a (mod p)。 即若有整数即若有整数a，(a, n) = 1，使得，使得 a n 1 1 (mod n)， 并不能保并不能保证证n是素数。是素数。 例例5 设设n是正整数，是正整数，记记Fn = FermatFermat定理定理2024/7/27阜阳师范学院 数科院71例例6 如果今天是星期一，再如果今天是星期一，再过过101010天是星

33、期几？天是星期几？即得：再即得：再过过101010天是星期五。天是星期五。2024/7/27阜阳师范学院 数科院72三、在分数与小数互化中的应用三、在分数与小数互化中的应用 有理数，即有限小数和无限循环小数，可以用有理数，即有限小数和无限循环小数，可以用分数来表示。利用欧拉定理可以解决分数、小数的分数来表示。利用欧拉定理可以解决分数、小数的转化问题。转化问题。定义定义 如果对于一个无限小数如果对于一个无限小数 则称之为循环小数，并简记为则称之为循环小数，并简记为 注：注：若找到的若找到的t是最小的，是最小的，则则称称 为为循循环节环节；t称称为为循循环节环节的的长长度；若最小的度；若最小的s0

34、， 则称该小数为纯循环小数，否则为混循环小数。则称该小数为纯循环小数，否则为混循环小数。2024/7/27阜阳师范学院 数科院73定理定理3 3 有理数有理数 能表示为能表示为纯纯循环小数循环小数 即：分母不含质因数即：分母不含质因数2 2或或5 5。2024/7/27阜阳师范学院 数科院74定理定理3 3 有理数有理数 能表示为能表示为纯纯循环小数循环小数 (b, 10) = 1 由由Euler定理可知，有正整数定理可知，有正整数k，使得，使得10k 1 (mod b)，0 k (b)，因此存在整数因此存在整数q使得使得 而且而且ak, , a1不能都等于不能都等于0，也不能都等于，也不能都

35、等于9。 = 0.akak 1a1akak 1a1 。2024/7/27阜阳师范学院 数科院75定理定理4 设设a与与b是正整数，是正整数，0 a b，(a, b) = 1， 并且并且 b = 2 5 b1，(b1, 10) = 1，b1 1， 此处此处 与与 是不全为零的正整数，是不全为零的正整数， 其中不循环的位数码个数是其中不循环的位数码个数是 = max= max . .则则 可以表示成可以表示成混混循环小数，循环小数，证明：不妨假设证明：不妨假设 = = ， 其中其中0 a1 b1，0 M 10 ， 且且(a1, b1) = (2 a Mb1, b1) = (2 a, b1) = (

36、a, b1) = 1。因此，由定理因此，由定理3， 可以表示成可以表示成纯纯循循环环小数：小数： 2024/7/27阜阳师范学院 数科院76M = m110 1 m210 2 m （0 mi 9，1 i ），）， 下面下面说说明，上式中的明，上式中的 是最小的不循是最小的不循环环位数位数码码的个数。的个数。 若不然，设又有正整数若不然，设又有正整数， 2024/7/27阜阳师范学院 数科院77由定理由定理3 3有有 其中其中 b1 ， 10 ab1 = ba 。 上式右端可以被上式右端可以被5 整除，整除， 但是但是(a, 10) = 1，(b1 , 10) = 1， 所以所以5 ， 。 这就

37、证明了不循环位数码个数不能再少了。这就证明了不循环位数码个数不能再少了。 2024/7/27阜阳师范学院 数科院78证明：证明：2024/7/27阜阳师范学院 数科院79证明：证明：2024/7/27阜阳师范学院 数科院802024/7/27阜阳师范学院 数科院812024/7/27阜阳师范学院 数科院823.53.5公开钥匙公开钥匙RSARSA体制体制 2024/7/27阜阳师范学院 数科院83 该该算法于算法于1977年由美国麻省理工学院年由美国麻省理工学院mit(massachusetts institute of technology)的的ronal rivest，adi shamir

38、和和len adleman三位年三位年轻轻教授提出，并以三教授提出，并以三人的姓氏人的姓氏rivest，shamir和和adlernan命名命名为为rsa算法。算法。该该算法利用了数算法利用了数论领论领域的一个事域的一个事实实，那就是，那就是虽虽然把然把两个大两个大质质数相乘生成一个合数是件十分容易的事情，数相乘生成一个合数是件十分容易的事情，但要把一个合数分解但要把一个合数分解为为两个两个质质数却十分困数却十分困难难。合数分。合数分解解问题问题目前仍然是数学目前仍然是数学领领域尚未解决的一大域尚未解决的一大难题难题，至，至今没有任何高效的分解方法。与今没有任何高效的分解方法。与diffie-

39、hellman算法相算法相比，比，rsa算法具有明算法具有明显显的的优优越性，因越性，因为为它无它无须须收收发发双方双方同同时时参与加密参与加密过过程，且非常适合于程，且非常适合于电电子函件系子函件系统统的加的加密。密。2024/7/27阜阳师范学院 数科院84RSARSA中的密钥中的密钥RSARSA中的加密与解密中的加密与解密2024/7/27阜阳师范学院 数科院85RSARSA中密钥中参数的选择中密钥中参数的选择2024/7/27阜阳师范学院 数科院86RSARSA中密钥中参数的选择（示例一）中密钥中参数的选择（示例一）2024/7/27阜阳师范学院 数科院87RSARSA中密钥中参数的选

40、择（示例二）中密钥中参数的选择（示例二）2024/7/27阜阳师范学院 数科院88RSARSA安全性取决于对模安全性取决于对模n n因数分解的困难性。因数分解的困难性。19991999年年8 8月，荷兰国家数学与计算机科学研究所家们月，荷兰国家数学与计算机科学研究所家们的一组科学家成功分解了的一组科学家成功分解了512bit512bit的整数，大约的整数，大约300300台台高速工作站与高速工作站与PCPC机并行运行，整个工作花了机并行运行，整个工作花了7 7个月。个月。19991999年年9 9月，以色列密码学家月，以色列密码学家Adi ShamirAdi Shamir设计了一种设计了一种名叫名叫“TWINKLETWINKLE”的因数分解设备，可以在几天内攻的因数分解设备，可以在几天内攻破破512bit512bit的的RSARSA密钥。（但要做到这一点，需要密钥。（但要做到这一点，需要300-300-400400台设备，每台设备价值台设备，每台设备价值50005000美圆）。美圆）。RSARSA算法的安全性算法的安全性