1、2022-1-22电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院 计算系统与网络安全计算系统与网络安全Computer System and Network SecurityComputer System and Network Security2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）2022-1-22l子夏曰：子夏曰：“贤贤易贤贤易色色；事父母，能竭其力；事君，；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾能致其身；与朋友交，言而有信。
2、虽日未学，吾必谓之学矣。必谓之学矣。”l人际关系：父子；君臣；朋友；夫妻人际关系：父子；君臣；朋友；夫妻数论基础数论基础2022-1-222.整除的基本性质整除的基本性质( N 整数集整数集) (1) a(a0), a|0,a|a (同理同理 b N,1|b) (2) b|a, cb|ca (3) a|b, b|c a|c.（传递性）（传递性） (4) a|b, a|c a|(xb+yc) (x,y N) (5) b|a 且且a0 |b|a| (6) cb|ca, b|a1.定义：定义： 设整数设整数a和和b,且且a 0，如果存在整数，如果存在整数k使得使得b=ak， 那么就说那么就说a整除整
3、除a（或（或b能被能被a整除）整除），记作，记作a|b，或者说，或者说b是是a的倍数。的倍数。 举例：举例：3|15,-15|60整除定义及性质整除定义及性质2022-1-22证明：证明：（1）作一个整数序列）作一个整数序列（2）反证法）反证法带余数除法：带余数除法： 如果如果a，b是两个整数，其中是两个整数，其中b0，则存在两个整数，则存在两个整数q和和r，使得，使得abqr（0rb）成立，且）成立，且q和和r是唯一的。是唯一的。带余数除法带余数除法2022-1-22非负最小剩余的性质：非负最小剩余的性质：（1） = + （2） = - （3） = 定义（非负最小剩余）定义（非负最小剩余）
4、abqr（0rb）中）中r叫做非负最小剩余，常记做叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，（在不致引起混淆的情况下，b常常省略）常常省略）带余数除法带余数除法2022-1-221.定义：定义： 一个大于一个大于1的整数的整数p，只能被只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整数整除，则称整数为素数被其他整数整除，则称整数为素数(prime number)，否，否则就叫做合数则就叫做合数(composite)。 eg 素数（素数（2，3，5，7，11，13等）等） 合数（合数（4，6，8，9，12等）等） 素数定义及素数个数定理素数定义及素数个数定理2022-
5、1-222.补充定理补充定理(1)：设：设a是任一大于是任一大于1的整数，则的整数，则a的的除除1外的最小正因子外的最小正因子q是素数，并且当是素数，并且当a是合数是合数时：时：素数补充定理素数补充定理qa2022-1-222.补充定理补充定理(2)：若：若p是一个素数，是一个素数，a是任一整数，是任一整数，则有则有p|a或或(p,a)=1素数补充定理（续）素数补充定理（续）2022-1-22素数补充定理（续）素数补充定理（续）2.补充定理：补充定理： p为素数，且为素数，且p|ab,那么那么p|a或或p|b。 更一般地，如果更一般地，如果abz能够被素数能够被素数p整除，那么整除，那么a,b
6、,z中的某个数必能被中的某个数必能被p整除。整除。2022-1-223.素数个数定理（素数个数定理（1）：）： 素数的个数是无限的素数的个数是无限的原因：原因：（1）N（N1）的除）的除1外的最小正因数外的最小正因数q是一个素数是一个素数（2）如果）如果q=pi，（，（i1,2,k), 且且q|N，因此，因此q|(N- p1p2,.pk)，所以，所以q|1，与，与q是素数矛盾。是素数矛盾。素数个数定理及证明素数个数定理及证明证明：反证法证明：反证法假设正整数个数是有限的，设为假设正整数个数是有限的，设为p1,p2,.,pk令：令：p1p2pk+1=N (N1)则则N有一个素数有一个素数p，且，
7、且ppi（i=1,2,k).故故p是上述是上述k个素数外的另外一个素数。个素数外的另外一个素数。因此与假设矛盾。因此与假设矛盾。2022-1-22素数定义及素数个数定理素数定义及素数个数定理3.素数个数定理（素数个数定理（2）：）： 设设 (x)是小于是小于x的素数个数，则的素数个数，则 (x) x / lnx, 即即x时，比值时，比值 (x) /(x / lnx) 1 eg:可以估算可以估算100位素数的个数：位素数的个数： (10100) - (1099) 10100/(ln10100) 1099/(ln1099) 3.9 * 1097.2022-1-221.整数的唯一分解定理定理（算术基
8、本定理）整数的唯一分解定理定理（算术基本定理）: 设设nZ, 有分解式有分解式, n = p1e1p2e2.pmem,其中其中p1, p2, pmZ+是互不相同的素数是互不相同的素数, e1,e2,emZ+, 并且数对并且数对(p1, e1), (p2, e2),(pm, em)由由n唯一确定（即唯一确定（即如果不考虑顺序，如果不考虑顺序，n的分解是唯一的）的分解是唯一的）.eg: 504=23327, 1125 = 3253整数的唯一分解定理整数的唯一分解定理2022-1-221.定义定义 两个整数两个整数a,b的最大公约数，就是能同时整除的最大公约数，就是能同时整除a和和b的最的最大正整数
9、大正整数,记为记为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.2022-1-22(2)欧几里得欧几里得(Euclid)算法算法 设设a, b N, ab0, 用以下方法可求出用以下方法可求出 gcd(a,b).最大公约数的欧几里得算法最大公约数的欧几里得算法. ,)gcd( ,0 , . )gcd( ,
10、0 ,)gcd( ,0 ,)gcd()gcd( ,0 ,1111123223332121122211111nnnnnnnnnnnnrqrr,rrrrrqrr,rrrrrqrr,rrrrrqrbb,ra,bbrrbqa2022-1-22Euclid算法实例：求算法实例：求 gcd(132, 108).12 ,12224)12,4gcd(2 ,12244108)24gcd(108 ,241081132)108gcd(132 ,最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2022-1-22l欧几里得算法（例欧几里得算法（例1）11802 4822164822 216502164 50
11、 1650 3 16216208gcd（1180，482）2求：求：gcd（1180，482）最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2022-1-22l欧几里得算法（例欧几里得算法（例2）：求）：求gcd(12345,1111)123451111111112345441 0gcd 12345111111123495123424645114（，）最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2022-1-22l欧几里得算法抽象欧几里得算法抽象112 1213 2324 342111b.gcd( , )kk kkkkkkaqbrq rrrq rrrq rrrq
12、rrrqra br规律：余数除数被除数忽略最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2022-1-22l欧几里得算法实现欧几里得算法实现1011112gcd( , ):;101(,.,):gcd( , )mmmrmrmmm mmmma bra rb mwhilerdoqrrq rmmreturnq qqrcommenta br算法最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2022-1-22特别特别a, b为素数时为素数时gcd(a,b)=1，存在，存在 ma+nb=1. 上述求上述求 rn = ma+nb的方法叫做的方法叫做扩展的扩展的Euclid算法算法
13、利用该方法我们可以求利用该方法我们可以求ax+by=d的解的解,这里这里d= (a,b) 证明：根据证明：根据Euclid算法算法 a=bq1+r1 b=r1q2+r2 r1=r2q3+r3 , rn-2 = rn-1qn+rn gcd(a,b)= r n = rn-2 - rn-1qn = = ma+nb3.定理定理 设设a, bZ+, 则存在则存在m, nZ使得使得gcd(a,b)=ma+nb. 扩展的欧几里得算法扩展的欧几里得算法2022-1-22l计算出了计算出了gcd(a,b);l但是并没有计算出两个数但是并没有计算出两个数m，n来，使得：来，使得：lma+nb=gcd(a,b)扩展
14、的欧几里得算法的结果扩展的欧几里得算法的结果l计算出了计算出了gcd(a,b);l计算出两个数计算出两个数m，n来，使得：来，使得：lma+nb=gcd(a,b)扩展的欧几里得算法（续）扩展的欧几里得算法（续）欧几里得算法的结果欧几里得算法的结果2022-1-22利用该方法我们可以求密码学方程利用该方法我们可以求密码学方程ax+by=d的的解解,这里这里d= (a,b)例如例如: 求求132x+108y = 12的解的解 解：解： 12=gcd(132,108) 12 = 108-4 24 = 108-4 (132-108 1) = 108 4 132 +4 108 =5*108 4*132扩
15、展的欧几里得算法（续）扩展的欧几里得算法（续）2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）2022-1-22证明：证明：必要性必要性:设设ab (mod m), a=mp+r, b=mq+r, 0rm a-b=m(p-q), m|(a-b).充分性充分性:设设m|(a-b), a=mp+r, b=mq+s, 0r, sm a-b=m(p-q)+(r-s) m|(r-s) 0|r-s|0， C1，Cm-1是模数是模数m的剩余类，则有：的剩余类，则有：（1）每一个整数恰好包含在某一个类）每一个整数恰好包含在某一个类Cj中（中（0jm-1）（2）两个整数）两个整数x
16、和和y属于同一个类的充要条件是属于同一个类的充要条件是xy（mod m）剩余类和完全剩余系（续）剩余类和完全剩余系（续）2022-1-22定义（完全剩余系）：定义（完全剩余系）： 在模数在模数m的剩余类的剩余类 C1，Cm-1中各取一数中各取一数aj（j=0，1，m-1），此），此m个数个数a0，a1，am-1称为模数称为模数m的一组完全剩余系。的一组完全剩余系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）例如：例如：m3 C00，3，6，9， C11，4，7，10， C2 2，5，8，11，则则a00，a11，a22就是模就是模m的一组完全剩余系。的一组完全剩余系。2022-1-22定理
17、（完全剩余系）：定理（完全剩余系）： m个整数组成模数个整数组成模数m的一组完全剩余系的充要条件是的一组完全剩余系的充要条件是两两对模数两两对模数m不同余。不同余。剩余类和完全剩余系（续）剩余类和完全剩余系（续）定义（非负最小完全剩余系）定义（非负最小完全剩余系） 由由0， 1，2，m-1组成的剩余系称为模数组成的剩余系称为模数m的非的非负最小完全剩余系。负最小完全剩余系。2022-1-22定理（完全剩余系）：定理（完全剩余系）： 设（设（k, m）1，a0，a1，am-1是模数是模数m的一组完的一组完全剩余系，则：全剩余系，则： ka0， ka1，kam-1也是模数也是模数m的一组完全剩余系
18、。的一组完全剩余系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）2022-1-22（1）剩余类可能包含多个集合（）剩余类可能包含多个集合（ 即：模数即：模数m的的剩余类是多个集合）剩余类是多个集合）（2）完全剩余系专指一个集合）完全剩余系专指一个集合剩余类和完全剩余系（续）剩余类和完全剩余系（续）定义（定义（模数模数m互素的剩余类）互素的剩余类） 如果一个模数如果一个模数m的剩余类里面的数与的剩余类里面的数与m互素，互素，就称之为与模数就称之为与模数m互素的剩余类。互素的剩余类。例如：例如：m3 C11，4，7，10， C2 2，5，8，11，都是模都是模m互素的剩余类。互素的剩余类。20
19、22-1-22定义（定义（缩系）缩系） 在与模数在与模数m互素的全部剩余类中，各取一个数所组成互素的全部剩余类中，各取一个数所组成的集合叫做模数的集合叫做模数m的一组缩系。的一组缩系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）例如：例如：m3 C11，4，7，10， C2 2，5，8，11，是模是模m互素的剩余类，而互素的剩余类，而C 4，5是模数是模数m的一的一组缩系。组缩系。问题：缩系含有多少个数？问题：缩系含有多少个数？2022-1-22欧拉函数的求法：欧拉函数的求法： （1）如果）如果n是素数，则是素数，则?(n)=n-1 （2）npq，其中，其中p，q为素数，则为素数，则?(n
20、)=(p-1)(q-1) （3）1.定义（欧拉函数）定义（欧拉函数） 欧拉函数欧拉函数?(n)是一个定义在正整数上的函数，是一个定义在正整数上的函数， ?(n) 的的值等于序列值等于序列0，1，2，n1中与中与n互素的数的个数。互素的数的个数。费马小定理和欧拉定理费马小定理和欧拉定理12111( )(1)(1).(1)ipppnnin.12iqqq12i12如果 ppp （p ，p，p 为素数），则：2022-1-22定理（缩系中数的个数）定理（缩系中数的个数） 模数模数m的缩系含有的缩系含有?(n)个数。个数。费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）例如：例如： m3， ?(m)
21、2，因而，因而C 1，2含有两含有两个数。个数。定理（缩系）定理（缩系） 若若a1，a2，a ?(m)是是?(m)个与个与m互素的整数，则互素的整数，则a1，a2，a?(m)是模数是模数m的一组缩系的充要条件是它们两的一组缩系的充要条件是它们两两对模数两对模数m不同余不同余。2022-1-22定理：若（定理：若（a，m）1，x通过模数通过模数m的缩系，的缩系，则则ax也通过模数也通过模数m的缩系。的缩系。费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）证明：证明： 当当x通过模数通过模数m的缩系，则的缩系，则ax通过通过?(m)个整数，由于个整数，由于（a，m）=1，（，（x，m）=1，因
22、此（，因此（ax，m）=1。 若若ax1ax2（mod m），可知），可知x1x2（mod m），与假设），与假设x通过模数通过模数m的缩系矛盾，故的缩系矛盾，故ax通过模数通过模数m的缩系。的缩系。2022-1-22(2)欧拉定理欧拉定理 设设m1，如果，如果gcd(a, n) = 1,则则:a?(n) 1mod n. eg: 求求7803的后三位数字的后三位数字 解：解： 7803（mod 1000）的结果）的结果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)费马小定理和欧拉定理（续）费马小定理和欧拉
23、定理（续）2022-1-22推论（推论（ Fermat小定理）小定理）: p素数素数,a是整数且不能被是整数且不能被p整除整除,则则:a p-1 1 mod p. 费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 2022-1-22 （1）通常情况下，如果）通常情况下，如果2n-1 1 (mod n),n为素数为素数,然而然而,也有例外也有例外: 561 = 3 11 17是合数是合数,但但2560 1
24、 (mod 561)。因此，如果。因此，如果2n-1 1 (mod n),那么那么n可能为素数。可能为素数。 （2）但）但2n-1 模模n 不等于不等于 1,那么那么n不可能为素数不可能为素数 这为我们提供一种寻找素数的方法，给定一个这为我们提供一种寻找素数的方法，给定一个n, 计计算算2n-1 模模n 是否等于是否等于 1，如果不等于，如果不等于1， n为非素数，为非素数，如果等于如果等于1，还需用更复杂的方法来判断是否为素数，还需用更复杂的方法来判断是否为素数，比如：比如： (1)索洛维索洛维-斯特拉森斯特拉森(Solovay-Strassen)素性检测算法素性检测算法 (2)米勒米勒-罗
25、宾罗宾(Miller-Rabin)素性检测算法素性检测算法 (3) AKS算法算法费马小定理和欧拉定理的应用费马小定理和欧拉定理的应用2022-1-22 解：解：（1）由费尔马定理）由费尔马定理2100（mod 1001）1（mod 101）（2）243210 (2100) 432210 210 1024 (mod 101)=14eg: 计算计算243210 （mod 101）欧拉定理的应用欧拉定理的应用2022-1-227.一次同余式一次同余式 (1)定义定义: 设设mZ+, a, bZ, a0, 我们把我们把 ax+b0 (mod m) 称为模数称为模数m的一次同余式的一次同余式. 如果如
26、果x0Z满足满足: ax0+b0 (mod m) 则称则称xx0 (mod m)是同余式的解是同余式的解.eg : 同余式同余式2x+1 0 (mod 3) 有解有解x0=1. 同余式同余式2x+1 0 (mod 4) 无解无解. 同余式同余式2x+1 0 (mod 5) 有解有解x0=2.一次同余式一次同余式2022-1-22(2)一次同余式的解一次同余式的解 定理定理1: 设设mZ+, a, bZ, a0, (a, m)=1, 则同余式则同余式 axb (mod m)恰有一个解恰有一个解xba ?(m)-1 (mod m). eg:同余式同余式2x+10 (mod 5) 有解有解: x0=
27、(-1)2 ?(5)-1 423 322 (mod 5) 一次同余式（续）一次同余式（续）2022-1-22 定理定理2: 设设mZ+, a, bZ, a0, (a, m)=d, 则同余式则同余式axb(mod m) 有解的充要条件是有解的充要条件是d|b. 在在d|b的条件下的条件下, 同余式有同余式有d个解个解. eg: 同余式同余式2x 3 (mod 4)无解无解 d=(2,4)=23. 同余式同余式2x 4 (mod 6) d=(2,6)=2|4 有有2个解个解: x=2, 5. 一次同余式的解一次同余式的解2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）
28、2022-1-22孙子算经孙子算经中记载着一道世界闻名的中记载着一道世界闻名的“孙子问题孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？七七数之剩二，问物几何？”孙子问题等同于下面这样一个问题：孙子问题等同于下面这样一个问题： 已知已知 x=2mod3，x=3mod5且且x=2mod7，求整数，求整数x。中国剩余定理中国剩余定理2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理
29、中国剩余定理(孙子孙子: Sun Ze, 公元前公元前450年年,孙子定理孙子定理)： 设自然数设自然数m1,m2,mr两两互素，并记两两互素，并记M=m1m2mr，则，则同余方程组同余方程组: x b1(mod m1) x b2(mod m2) . . x br(mod mr) 有唯一解：有唯一解： x b1*M1*y1+b2*M2*y2+br*Mr*yr (mod M) Mi = M/mi ,yi = Mi-1 (mod mi) (1 i r) 中国剩余定理（续）中国剩余定理（续）2022-1-22例如例如:求以下同余方程组的解：求以下同余方程组的解： x 5 mod 7 x 3 mod
30、11 x 10 mod 13中国剩余定理解同余方程组中国剩余定理解同余方程组解：解： r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10; 模模M = m1 m2 m3 = 1001, M1 =M/ m1 = m2 m3 = 143, M2 =91, M3 =77. y1 = M1-1(mod m1) = 143-1(mod 7) = 5, y2=4, y3=12. 解为解为: x = b1 M1 y1 + b2 M2 y2 + b3 M3 y3 (mod M) = 5 143 5 + 3 91 4 + 10 77 12 (mod 1001) =13907 (mod 10
31、01) = 894验证验证: x = 894 = 127 7+5 = 5 (mod 7) 2022-1-22中国剩余定理：中国剩余定理： 除数除数余数余数最小公倍数最小公倍数衍数衍数乘率乘率各总各总答数答数m1b1m=m1m2mkM1M1M1M1b1X=MiMibi (mod m)m2b2M2M2M2M2b2mkbkMkMkMkMkbk其中：其中：m=miMiMiMi=1 (mod m)中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22例如（孙子算经）解法：表格法例如（孙子算经）解法：表格法除数除数 余数余数最小公倍数最小公倍数衍数衍数
32、乘率乘率各总各总答数答数323x5x7=1055x7M1=2 35x2x21406330233537x3M2=1 21x1x3723x5M3=1 15x1x2中国剩余定理求解同余方程组中国剩余定理求解同余方程组2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22中国剩余定理（续）中国剩余定理（续）2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）2022-1-22计算计算Xa ( mod n) ,其中其中 x, a, n Z+ Eg:计算计算21234 (mod 789) 一种有效的方法：一种
33、有效的方法： 24 16 28 256 216 2562 49 232 492 34 264 342 367 2128 3672 559 2256 5592 37 2512 372 580 21024 5802 286 1234 = 1024+128+64+16+2 （1234 = (10011010010)2） 21234 = 286 559 367 49 4 481 (mod 789)模的幂运算模的幂运算优势：优势：模的幂运算可快速完成，并且模的幂运算可快速完成，并且不需要太大内存不需要太大内存2022-1-22模的幂运算（续）模的幂运算（续）22/ 2 (2-1) / 2 (yyyyyy
34、y表 示 除 以 取 整 ， 即 ：是 偶 数（是 奇 数 ）但是，上述计算过程并不适合于计算机程序实但是，上述计算过程并不适合于计算机程序实现。为此，可以采用现。为此，可以采用“重复平方重复平方-乘乘”运算来运算来进行指数模运算。进行指数模运算。2222() () (yyyxyxxxy因 此 ：是 偶 数是 奇 数 ）2022-1-22模的幂运算（续）模的幂运算（续）重复平方重复平方-乘算法乘算法 求模指数运算的重复平方-乘算法 输入：整数 x，y，n：x0，y?0，n1 输出：(mod )yxn 算法描述： 00 mod_exp(x,y, n) 01 if y=0 return(1) 02
35、 if y (mod 2)=0 return(mod_exp(x2(mod n), y2, n)（mod n） 03 return(xmod_exp(x2(mod n), y2, n)(mod n) 2022-1-22第第2章章 信息安全数学基础（数论）信息安全数学基础（数论）2022-1-22整数的次数整数的次数由欧拉定理知道：如果由欧拉定理知道：如果(a, m)1，m1，则，则a?(n) 1(mod m)也就是说，如果也就是说，如果(a, m)1，m1，则存在一个整数，则存在一个整数满足满足:a 1(mod m)定义（整数的次数）：定义（整数的次数）： 若若(a, m)1，m1，则使得同余
36、式，则使得同余式 a 1(mod m)成立的成立的最小正整数最小正整数叫做叫做a对模对模m的的次数次数。2022-1-22整数的次数（续）整数的次数（续）定理：设定理：设a对模数对模数m的次数为的次数为l，an1（mod m），则），则l|n。证明：证明： 如果结论不成立，则必有两个整数如果结论不成立，则必有两个整数q和和r，使得：，使得： nqlr（0rl） 而而1 an a(qlr) aqlar ar (mod m)，因此与，因此与l的定义相的定义相违背。违背。 推论：设推论：设a对模数对模数m的次数为的次数为l，则，则l|?(m)。2022-1-22整数次数的计算：整数次数的计算： 因为
37、因为l|?(m)，因此可以通过计算以下对模数，因此可以通过计算以下对模数m的值求出。的值求出。整数的次数（续）整数的次数（续）例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此因此a对模数对模数m的次数为的次数为3。s1212s,.dd .dmdddaaa， （其中，是 （）的诸因子）2022-1-22整数次数的有效计算方法（整数次数的有效计算方法（1）：）：整数的次数（续）整数的次数（续）1212.killlklimpppmp如果是的标准分解式，整数a对模数m的次数等于整数a对模数的诸次数的最小公倍数。1212a1,2,.,),.,0|(1,2,.,),.,iii
38、liiklddilddiikfpikdfffapamdmdddamapfdikdfff证 明 ： 设表 示 对 模 数（1(mod )1(mod )如 果不 是 模 数的 次 数 ， 则 设 其 次 数 为1(mod )1(mod )与是的 最 小 公 倍 数 矛 盾 。2022-1-22整数次数的有效计算方法（整数次数的有效计算方法（1）：）：整数的次数（续）整数的次数（续）amam例如：设 2， 45，求 对 的次数。解 ：45 5 92对 模 数 5的 次 数 是 42对 模 数 9的 次 数 是 6因 此 2对 模 数 45的 次 数 为 ：4,6=12。2022-1-22整数次数的有
39、效计算方法（整数次数的有效计算方法（2）：）：整数的次数（续）整数的次数（续）211212|1 2 jjfijjjjjjpapffffpfpafjifpfji定理（次数的求法之二）设 是一个素数， 对模数的次数是，则：=或=；又设，则有：10102apaf例如：设 7， 2，求 对模数的次数。122410410127148,2| 4822128fff解 ：， 所 以 ：2022-1-22整数的次数（续）整数的次数（续）定理：设定理：设a对模数对模数m的的次数次数为为l，1,a, a2,，al-1对对模数模数m两两不同余。两两不同余。证明：证明： 如果结论不成立，则有某对如果结论不成立，则有某对
40、j，k（0jkl-1，使得：，使得： aj ak（mod m） 因此：因此： ak-j 1（mod m） 而而1k-j0,(g,m)=1, 如果整数如果整数g对对m的的次数次数为为?(m) ，则，则g叫做叫做m的一个的一个本原根本原根（或（或原根原根）. eg: 3是模是模7的的本原根本原根 因为因为3 ?(7) 36 1(mod 7) 本原根定义本原根定义2022-1-22本原根定义（续）本原根定义（续）例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此：因此： a对模数对模数m的次数为的次数为3 (m) 所以：所以： 2不是不是7的本元根。的本元根。2022-1
41、-22定理（原根）定理（原根） 设整数设整数m0,(g,m)=1,则则g是是m的一个原根的充要的一个原根的充要条件是：条件是： g，g2，g?(m)组成模数组成模数m的一组缩系。的一组缩系。本原根判断本原根判断定理说明：如果定理说明：如果g是是m的一个原根，则模数的一个原根，则模数m的一的一组缩系可表示为形如定理中的几何级数。组缩系可表示为形如定理中的几何级数。2022-1-222.定理：定理： 设对素数设对素数p而言，如果而言，如果g是一个是一个本原根本原根 (1)如果如果n是是整数，那么整数，那么gn 1(mod p)当且仅当当且仅当 n0(mod p-1) (2)如果如果j和和k都是整数
42、，那么都是整数，那么gj gk当且仅当当且仅当j k(mod p-1)本原根有关定理本原根有关定理2022-1-22问题：是否所有的正整数都有原根？问题：是否所有的正整数都有原根？本原根有关定理（续）本原根有关定理（续）例如：例如：m12(m)623，与，与m互素的正整数包括互素的正整数包括5，7，11。52（mod 12）1因此，因此，5对对12的次数是的次数是272（mod 12）1因此因此7对模数对模数m的次数为的次数为2112（mod 12）1因此因此11对模数对模数m的次数为的次数为2因此因此m12没有原根。没有原根。2022-1-22定理（整数存在原根的必要条件）：定理（整数存在原
43、根的必要条件）： 设设m1，若，若m有原根，则有原根，则m必为下列诸数之一：必为下列诸数之一：2，4，pl，2pl（l1，p为奇素数）。为奇素数）。本原根有关定理（续）本原根有关定理（续）定理（整数存在原根的充分条件）：定理（整数存在原根的充分条件）： 设设m2，4，pl，2pl（l1，p为奇素数）时，则为奇素数）时，则m有原有原根。根。定理（整数原根个数）：定理（整数原根个数）： 设设m有一个原根有一个原根g，则，则m恰有恰有?(?(m)个对模数个对模数m不同余不同余的原根，这些原根由以下集合给出：的原根，这些原根由以下集合给出：|1( ),( , ( ) 1tSgtmtm 2022-1-2
44、2本原根有关定理（续）本原根有关定理（续） 17gmmmmm1( ),( , ( ) 13 mod733 mod75mtmtm 例如，已知 3是 7的一个原根，求 的所有元根。解：（ ）62 3（ ）（6）2因此 有两个元根。满足条件的t=1,5即 有两个元根，分别为3和52022-1-22原根的判断：原根的判断： 一般来说，判断一般来说，判断g是否时一个素数是否时一个素数m的原根时，的原根时，不需要逐一计算不需要逐一计算g1，g2，g?(m)，而仅需要，而仅需要计算计算gt(modm），其中），其中t|?(m)。本原根有关定理（续）本原根有关定理（续）2022-1-22本原根有关定理（续）本
45、原根有关定理（续） 23gmm4 mod74 mod7)24 mod7) 14 mod71m16例如，判断 4是否是 7的一个原根解：（ ）62 3满足条件t| (m)的t=1,2,3,6（）4（）因此4不是 的本元根。2022-1-22本原根有关定理（续）本原根有关定理（续）定理（原根的计算）：定理（原根的计算）： 12( )2.11(mod )(1,2,., )ismqmmqqqgmgmgm is设，（ ）的所有不同的素因子是 ， ， ，（ ， ），则 是 的一个原根的充要条件是： 3121220812412525)20,812mod4140112mod411811241gmmqqmmqq
46、m例如，证明 是 的原根。证明：（ ），（）（）由定理是 的一个原根。2022-1-22本原根有关定理（续）本原根有关定理（续） 12gm6 2 32,33;2mod7mod763 m 7mqqmm1223例如，判断 3是否是 7的原根。解：（ ）所以（ ）（ ）qq3 （）2 13 （）1因此 是 的原根。2022-1-22本原根有关定理（续）本原根有关定理（续） 12gmm2,33;2mod7mod7m=7qqmm1223例如，判断 4是否是 7的一个原根解：（ ）62 3所以（ ）（ ）qq4 （）2 14 （）1因此4不是的本元根。2022-1-22本原根有关定理（续）本原根有关定理（
47、续）定理（原根的计算）：定理（原根的计算）： 1 ,1,2,.,papd dpd设 对模数奇素数 的次数是（），则：a都不是 的原根。 12.1,12.dadpdddpadpd证明：因为 （ ， ， ）对模数 的次数为，而（ ， ）所以 （ ， ， ）都不是 的原根。（ ， ）2022-1-22本原根有关定理（续）本原根有关定理（续）一个计算原根的算法：一个计算原根的算法： 2112.1221112, 2,., 2(3)1111dppppaapddppdpp （）列出数， ， ， （）取 ，计算 对 的次数 ，如果 ，2就是 的原根，算法结束；如果，在步骤中列出的数中除去以下各数：在步骤（）列
48、出的数中再取一个，重复步骤（），直到步骤（）缩列出的数仅剩下（ ）个。2022-1-2241例如：求出 的原根。本原根有关定理（续）本原根有关定理（续）1解：（ ）列出1，2，3，.，40 （1）（2）取2，因为2对模数41的次数为20，因此（1）式中除去以下各数：2，4，8，16，32，23，5，10，20，40，39，37，33，25，9，18，36，31，21，1得到：3，6，7，11，12，13，14，15，17，19，22，24，26，27，28，29，30，34，35，382022-1-22本原根有关定理（续）本原根有关定理（续） 41例如：求出 的原根。解(续）：（3）取3，因为
49、3对模数41的次数为8，因此在（1）式中除去以下各数：3，9，27，40，38，32，14，1其中1，9，32，40在第一次已经除去，得到：6，7，11，12，13，15，17，19，22，24，26，28，29，30，34，35这剩下的（40）16个数就是41的原根。2022-1-22指数指数如果整数如果整数m0有一个元根有一个元根g，g，g2，g?(m)(或数或数1,g，g，g2，g?(m)-1）组成模数）组成模数m的一组缩系。的一组缩系。例如，例如， 3是模是模7的的本原根，因此本原根，因此： 31 3 32 2 33 6 34 4 35 5 36 1 上述六个数刚好是模数上述六个数刚好
50、是模数m的一组缩系。的一组缩系。2022-1-22指数（续）指数（续）定义：任一整数定义：任一整数n，（，（n，m）1，必有唯一的整，必有唯一的整数数k（0k ?（m），满足：），满足： ngk（mod m） 其中其中k叫做叫做n对模数对模数m的指数，记做的指数，记做kindgn（简（简记为记为ind n） (指数也叫做指数也叫做离散对数离散对数)。2022-1-22xg mod m (mod )xngm对于已知元根g和模数m，求任意整数n的离散对数k,可以通过得到：指数（续）指数（续）2022-1-22( )(13) 12(1,2,.,12)(0( ) 2 (mod13)iiikimn ik
