第2章-信息安全数学基础(数论).ppt

电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院 计算系统与网络安全计算系统与网络安全Computer System and Network SecurityComputer System and Network Security2024/5/9 周四.l子夏曰：子夏曰：“贤贤易贤贤易色色；事父母，能竭其力；事君，；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。必谓之学矣。”l人际关系：父子；君臣；朋友；夫妻人际关系：父子；君臣；朋友；夫妻数论基础数论基础2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.2.整除的基本性质整除的基本性质(N 整数集整数集)(1)a(a0),a|0,a|a(同理同理 b N,1|b)(2)b|a,cb|ca(3)a|b,b|ca|c.（传递性）（传递性）(4)a|b,a|ca|(xb+yc)(x,y N)(5)b|a且且a0|b|a|(6)cb|ca,b|a1.定义：定义：设整数设整数a和和b,且且a0，如果存在整数，如果存在整数k使得使得b=ak，那么就说那么就说a整除整除a（或（或b能被能被a整除）整除），记作，记作a|b，或者说，或者说b是是a的倍数。的倍数。举例：举例：3|15,-15|60整除定义及性质整除定义及性质2024/5/9 周四.证明：证明：（1）作一个整数序列）作一个整数序列（2）反证法）反证法带余数除法：带余数除法：如果如果a，b是两个整数，其中是两个整数，其中b0，则存在两个整数，则存在两个整数q和和r，使得，使得abqr（0rb）成立，且）成立，且q和和r是唯一的。是唯一的。带余数除法带余数除法2024/5/9 周四.非负最小剩余的性质：非负最小剩余的性质：（1）=+（2）=-（3）=定义（非负最小剩余）定义（非负最小剩余）abqr（0rb）中）中r叫做非负最小剩余，常记做叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，（在不致引起混淆的情况下，b常常省略）常常省略）带余数除法带余数除法2024/5/9 周四.1.定义：定义：一个大于一个大于1的整数的整数p，只能被只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整数整除，则称整数为素数被其他整数整除，则称整数为素数(primenumber)，否，否则就叫做合数则就叫做合数(composite)。eg素数（素数（2，3，5，7，11，13等）等）合数（合数（4，6，8，9，12等）等）素数定义及素数个数定理素数定义及素数个数定理2024/5/9 周四.2.补充定理补充定理(1)：设：设a是任一大于是任一大于1的整数，则的整数，则a的的除除1外的最小正因子外的最小正因子q是素数，并且当是素数，并且当a是合数是合数时：时：素数补充定理素数补充定理2024/5/9 周四.2.补充定理补充定理(2)：若：若p是一个素数，是一个素数，a是任一整数，是任一整数，则有则有p|a或或(p,a)=1素数补充定理（续）素数补充定理（续）2024/5/9 周四.素数补充定理（续）素数补充定理（续）2.补充定理：补充定理：p为素数，且为素数，且p|ab,那么那么p|a或或p|b。更一般地，如果更一般地，如果abz能够被素数能够被素数p整除，那么整除，那么a,b,z中的某个数必能被中的某个数必能被p整除。整除。2024/5/9 周四.3.素数个数定理（素数个数定理（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，且，且ppi（i=1,2,k).故故p是上述是上述k个素数外的另外一个素数。个素数外的另外一个素数。因此与假设矛盾。因此与假设矛盾。2024/5/9 周四.素数定义及素数个数定理素数定义及素数个数定理3.素数个数定理（素数个数定理（2）：）：设设(x)是小于是小于x的素数个数，则的素数个数，则(x)x/lnx,即即x时，比值时，比值(x)/(x/lnx)1eg:可以估算可以估算100位素数的个数：位素数的个数：(10100)-(1099)10100/(ln10100)1099/(ln1099)3.9*1097.2024/5/9 周四.1.整数的唯一分解定理定理（算术基本定理）整数的唯一分解定理定理（算术基本定理）:设设nZ,有分解式有分解式,n=p1e1p2e2.pmem,其中其中p1,p2,pmZ+是互不相同的素数是互不相同的素数,e1,e2,emZ+,并且数对并且数对(p1,e1),(p2,e2),(pm,em)由由n唯一确定（即唯一确定（即如果不考虑顺序，如果不考虑顺序，n的分解是唯一的）的分解是唯一的）.eg:504=23327,1125=3253整数的唯一分解定理整数的唯一分解定理2024/5/9 周四.1.定义定义两个整数两个整数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.2024/5/9 周四.(2)欧几里得欧几里得(Euclid)算法算法设设a,b N,ab0,用以下方法可求出用以下方法可求出gcd(a,b).最大公约数的欧几里得算法最大公约数的欧几里得算法2024/5/9 周四.Euclid算法实例：求算法实例：求gcd(132,108).最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2024/5/9 周四.l欧几里得算法（例欧几里得算法（例1）gcd（1180，482）2求：求：gcd（1180，482）最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2024/5/9 周四.l欧几里得算法（例欧几里得算法（例2）：求）：求gcd(12345,1111)最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2024/5/9 周四.l欧几里得算法抽象欧几里得算法抽象规律：余数除数被除数忽略最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2024/5/9 周四.l欧几里得算法实现欧几里得算法实现最大公约数的欧几里得算法（续）最大公约数的欧几里得算法（续）2024/5/9 周四.特别特别a,b为素数时为素数时gcd(a,b)=1，存在，存在ma+nb=1.上述求上述求rn=ma+nb的方法叫做的方法叫做扩展的扩展的Euclid算法算法利用该方法我们可以求利用该方法我们可以求ax+by=d的解的解,这里这里d=(a,b)证明：根据证明：根据Euclid算法算法a=bq1+r1b=r1q2+r2r1=r2q3+r3,rn-2=rn-1qn+rngcd(a,b)=rn=rn-2-rn-1qn=ma+nb3.定理定理设设a,bZ+,则存在则存在m,nZ使得使得gcd(a,b)=ma+nb.扩展的欧几里得算法扩展的欧几里得算法2024/5/9 周四.l计算出了计算出了gcd(a,b);l但是并没有计算出两个数但是并没有计算出两个数m，n来，使得：来，使得：lma+nb=gcd(a,b)扩展的欧几里得算法的结果扩展的欧几里得算法的结果l计算出了计算出了gcd(a,b);l计算出两个数计算出两个数m，n来，使得：来，使得：lma+nb=gcd(a,b)扩展的欧几里得算法（续）扩展的欧几里得算法（续）欧几里得算法的结果欧几里得算法的结果2024/5/9 周四.利用该方法我们可以求密码学方程利用该方法我们可以求密码学方程ax+by=d的解的解,这里这里d=(a,b)例如例如:求求132x+108y=12的解的解解：解：12=gcd(132,108)12=108-4 24=108-4(132-108 1)=1084 132+4 108=5*1084*132扩展的欧几里得算法（续）扩展的欧几里得算法（续）2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.证明：证明：必要性必要性:设设ab(modm),a=mp+r,b=mq+r,0rma-b=m(p-q),m|(a-b).充分性充分性:设设m|(a-b),a=mp+r,b=mq+s,0r,sma-b=m(p-q)+(r-s)m|(r-s)0|r-s|0，C1，Cm-1是模数是模数m的剩余类，则有：的剩余类，则有：（1）每一个整数恰好包含在某一个类）每一个整数恰好包含在某一个类Cj中（中（0jm-1）（2）两个整数）两个整数x和和y属于同一个类的充要条件是属于同一个类的充要条件是xy（modm）剩余类和完全剩余系（续）剩余类和完全剩余系（续）2024/5/9 周四.定义（完全剩余系）：定义（完全剩余系）：在模数在模数m的剩余类的剩余类C1，Cm-1中各取一数中各取一数aj（j=0，1，m-1），此），此m个数个数a0，a1，am-1称为模数称为模数m的一组完全剩余系。的一组完全剩余系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）例如：例如：m3C00，3，6，9，C11，4，7，10，C22，5，8，11，则则a00，a11，a22就是模就是模m的一组完全剩余系。的一组完全剩余系。2024/5/9 周四.定理（完全剩余系）：定理（完全剩余系）：m个整数组成模数个整数组成模数m的一组完全剩余系的充要条件是的一组完全剩余系的充要条件是两两对模数两两对模数m不同余。不同余。剩余类和完全剩余系（续）剩余类和完全剩余系（续）定义（非负最小完全剩余系）定义（非负最小完全剩余系）由由0，1，2，m-1组成的剩余系称为模数组成的剩余系称为模数m的非负的非负最小完全剩余系。最小完全剩余系。2024/5/9 周四.定理（完全剩余系）：定理（完全剩余系）：设（设（k,m）1，a0，a1，am-1是模数是模数m的一组完的一组完全剩余系，则：全剩余系，则：ka0，ka1，kam-1也是模数也是模数m的一组完全剩余系。的一组完全剩余系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）2024/5/9 周四.（1）剩余类可能包含多个集合（）剩余类可能包含多个集合（即：模数即：模数m的的剩余类是多个集合）剩余类是多个集合）（2）完全剩余系专指一个集合）完全剩余系专指一个集合剩余类和完全剩余系（续）剩余类和完全剩余系（续）定义（定义（模数模数m互素的剩余类）互素的剩余类）如果一个模数如果一个模数m的剩余类里面的数与的剩余类里面的数与m互素，互素，就称之为与模数就称之为与模数m互素的剩余类。互素的剩余类。例如：例如：m3C11，4，7，10，C22，5，8，11，都是模都是模m互素的剩余类。互素的剩余类。2024/5/9 周四.定义（定义（缩系）缩系）在与模数在与模数m互素的全部剩余类中，各取一个数所组成互素的全部剩余类中，各取一个数所组成的集合叫做模数的集合叫做模数m的一组缩系。的一组缩系。剩余类和完全剩余系（续）剩余类和完全剩余系（续）例如：例如：m3C11，4，7，10，C22，5，8，11，是模是模m互素的剩余类，而互素的剩余类，而C4，5是模数是模数m的一的一组缩系。组缩系。问题：缩系含有多少个数？问题：缩系含有多少个数？2024/5/9 周四.欧拉函数的求法：欧拉函数的求法：（1）如果）如果n是素数，则是素数，则(n)=n-1（2）npq，其中，其中p，q为素数，则为素数，则(n)=(p-1)(q-1)（3）1.定义（欧拉函数）定义（欧拉函数）欧拉函数欧拉函数(n)是一个定义在正整数上的函数，是一个定义在正整数上的函数，(n)的的值等于序列值等于序列0，1，2，n1中与中与n互素的数的个数。互素的数的个数。费马小定理和欧拉定理费马小定理和欧拉定理2024/5/9 周四.定理（缩系中数的个数）定理（缩系中数的个数）模数模数m的缩系含有的缩系含有(n)个数。个数。费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）例如：例如：m3，(m)2，因而，因而C1，2含有两含有两个数。个数。定理（缩系）定理（缩系）若若a1，a2，a(m)是是(m)个与个与m互素的整数，则互素的整数，则a1，a2，a(m)是模数是模数m的一组缩系的充要条件是它们两的一组缩系的充要条件是它们两两对模数两对模数m不同余不同余。2024/5/9 周四.定理：若（定理：若（a，m）1，x通过模数通过模数m的缩系，则的缩系，则ax也通过模数也通过模数m的缩系。的缩系。费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）证明：证明：当当x通过模数通过模数m的缩系，则的缩系，则ax通过通过(m)个整数，由于个整数，由于（a，m）=1，（，（x，m）=1，因此（，因此（ax，m）=1。若若ax1ax2（modm），可知），可知x1x2（modm），与假设），与假设x通过模数通过模数m的缩系矛盾，故的缩系矛盾，故ax通过模数通过模数m的缩系。的缩系。2024/5/9 周四.(2)欧拉定理欧拉定理设设m1，如果，如果gcd(a,n)=1,则则:a(n)1modn.eg:求求7803的后三位数字的后三位数字解：解：7803（mod1000）的结果）的结果(1000)=1000(1-1/2)(1-1/5)=400，有有7803(7400)273343(mod1000)费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）2024/5/9 周四.推论（推论（Fermat小定理）小定理）:p素数素数,a是整数且不能被是整数且不能被p整除整除,则则:ap-11modp.费马小定理和欧拉定理（续）费马小定理和欧拉定理（续）例如：例如：求求253(mod11)=?由由Fermat小定理小定理:210=10241(mod11)253=(210)52315238(mod11)2024/5/9 周四.（1）通常情况下，如果）通常情况下，如果2n-11(modn),n为素数为素数,然而然而,也有例外也有例外:561=3 11 17是合数是合数,但但25601(mod561)。因此，如果。因此，如果2n-11(modn),那么那么n可能为素数。可能为素数。（2）但）但2n-1模模n不等于不等于1,那么那么n不可能为素数不可能为素数这为我们提供一种寻找素数的方法，给定一个这为我们提供一种寻找素数的方法，给定一个n,计计算算2n-1模模n是否等于是否等于1，如果不等于，如果不等于1，n为非素数，为非素数，如果等于如果等于1，还需用更复杂的方法来判断是否为素数，还需用更复杂的方法来判断是否为素数，比如：比如：(1)索洛维索洛维-斯特拉森斯特拉森(Solovay-Strassen)素性检测算法素性检测算法(2)米勒米勒-罗宾罗宾(Miller-Rabin)素性检测算法素性检测算法(3)AKS算法算法费马小定理和欧拉定理的应用费马小定理和欧拉定理的应用2024/5/9 周四.解：解：（1）由费尔马定理）由费尔马定理2100（mod1001）1（mod101）（2）243210(2100)4322102101024(mod101)=14eg:计算计算243210（mod101）欧拉定理的应用欧拉定理的应用2024/5/9 周四.7.一次同余式一次同余式(1)定义定义:设设mZ+,a,bZ,a0,我们把我们把ax+b0(modm)称为模数称为模数m的一次同余式的一次同余式.如果如果x0Z满足满足:ax0+b0(modm)则称则称xx0(modm)是同余式的解是同余式的解.eg:同余式同余式2x+10(mod3)有解有解x0=1.同余式同余式2x+10(mod4)无解无解.同余式同余式2x+10(mod5)有解有解x0=2.一次同余式一次同余式2024/5/9 周四.(2)一次同余式的解一次同余式的解 定理定理1:设设mZ+,a,bZ,a0,(a,m)=1,则同余式则同余式axb(modm)恰有一个解恰有一个解xba(m)-1(modm).eg:同余式同余式2x+10(mod5)有解有解:x0=(-1)2(5)-1423322(mod5)一次同余式（续）一次同余式（续）2024/5/9 周四.定理定理2:设设mZ+,a,bZ,a0,(a,m)=d,则同余式则同余式axb(modm)有解的充要条件是有解的充要条件是d|b.在在d|b的条件下的条件下,同余式有同余式有d个解个解.eg:同余式同余式2x3(mod4)无解无解 d=(2,4)=23.同余式同余式2x4(mod6)d=(2,6)=2|4有有2个解个解:x=2,5.一次同余式的解一次同余式的解2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.孙子算经孙子算经中记载着一道世界闻名的中记载着一道世界闻名的“孙子问题孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？七七数之剩二，问物几何？”孙子问题等同于下面这样一个问题：孙子问题等同于下面这样一个问题：已知已知x=2mod3，x=3mod5且且x=2mod7，求整数，求整数x。中国剩余定理中国剩余定理2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理中国剩余定理(孙子孙子:SunZe,公元前公元前450年年,孙子定理孙子定理)：设自然数设自然数m1,m2,mr两两互素，并记两两互素，并记M=m1m2mr，则，则同余方程组同余方程组:xb1(modm1)xb2(modm2).xbr(modmr)有唯一解：有唯一解：xb1*M1*y1+b2*M2*y2+br*Mr*yr(modM)Mi=M/mi,yi=Mi-1(modmi)(1 i r)中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.例如例如:求以下同余方程组的解：求以下同余方程组的解：x5mod7x3mod11x10mod13中国剩余定理解同余方程组中国剩余定理解同余方程组解：解：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(modm1)=143-1(mod7)=5,y2=4,y3=12.解为解为:x=b1 M1 y1+b2 M2 y2+b3 M3 y3(modM)=5 143 5+3 91 4+10 77 12(mod1001)=13907(mod1001)=894验证验证:x=894=127 7+5=5(mod7)2024/5/9 周四.中国剩余定理：中国剩余定理：除数除数余数余数最小公倍数最小公倍数衍数衍数乘率乘率各总各总答数答数m1b1m=m1m2mkM1M1M1M1b1X=MiMibi(modm)m2b2M2M2M2M2b2mkbkMkMkMkMkbk其中：其中：m=miMiMiMi=1(modm)中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.例如（孙子算经）解法：表格法例如（孙子算经）解法：表格法除数除数 余数余数最小公倍数最小公倍数衍数衍数乘率乘率各总各总答数答数323x5x7=1055x7M1=2 35x2x21406330233537x3M2=1 21x1x3723x5M3=1 15x1x2中国剩余定理求解同余方程组中国剩余定理求解同余方程组2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.中国剩余定理（续）中国剩余定理（续）2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.计算计算Xa(modn),其中其中x,a,nZ+Eg:计算计算21234(mod789)一种有效的方法：一种有效的方法：2416282562162562492324923426434236721283672559225655923725123725802102458022861234=1024+128+64+16+2（1234=(10011010010)2）21234=286 559 367 49 4481(mod789)模的幂运算模的幂运算优势：优势：模的幂运算可快速完成，并且模的幂运算可快速完成，并且不需要太大内存不需要太大内存2024/5/9 周四.模的幂运算（续）模的幂运算（续）但是，上述计算过程并不适合于计算机程序实但是，上述计算过程并不适合于计算机程序实现。为此，可以采用现。为此，可以采用“重复平方重复平方-乘乘”运算来运算来进行指数模运算。进行指数模运算。2024/5/9 周四.模的幂运算（续）模的幂运算（续）重复平方重复平方-乘算法乘算法2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.整数的次数整数的次数由欧拉定理知道：如果由欧拉定理知道：如果(a,m)1，m1，则，则a(n)1(modm)也就是说，如果也就是说，如果(a,m)1，m1，则存在一个整数，则存在一个整数满足满足:a1(modm)定义（整数的次数）：定义（整数的次数）：若若(a,m)1，m1，则使得同余式，则使得同余式a1(modm)成立的成立的最小正整数最小正整数叫做叫做a对模对模m的的次数次数。2024/5/9 周四.整数的次数（续）整数的次数（续）定理：设定理：设a对模数对模数m的次数为的次数为l，an1（modm），则），则l|n。证明：证明：如果结论不成立，则必有两个整数如果结论不成立，则必有两个整数q和和r，使得：，使得：nqlr（0rl）而而1ana(qlr)aqlarar(modm)，因此与，因此与l的定义相的定义相违背。违背。推论：设推论：设a对模数对模数m的次数为的次数为l，则，则l|(m)。2024/5/9 周四.整数次数的计算：整数次数的计算：因为因为l|(m)，因此可以通过计算以下对模数，因此可以通过计算以下对模数m的值求出。的值求出。整数的次数（续）整数的次数（续）例如：例如：m7，a2(m)62322（mod7）423（mod7）1因此因此a对模数对模数m的次数为的次数为3。2024/5/9 周四.整数次数的有效计算方法（整数次数的有效计算方法（1）：）：整数的次数（续）整数的次数（续）2024/5/9 周四.整数次数的有效计算方法（整数次数的有效计算方法（1）：）：整数的次数（续）整数的次数（续）2024/5/9 周四.整数次数的有效计算方法（整数次数的有效计算方法（2）：）：整数的次数（续）整数的次数（续）2024/5/9 周四.整数的次数（续）整数的次数（续）定理：设定理：设a对模数对模数m的的次数次数为为l，1,a,a2,，al-1对对模数模数m两两不同余。两两不同余。证明：证明：如果结论不成立，则有某对如果结论不成立，则有某对j，k（0jkl-1，使得：，使得：ajak（modm）因此：因此：ak-j1（modm）而而1k-j0,(g,m)=1,如果整数如果整数g对对m的的次数次数为为(m)，则，则g叫做叫做m的一个的一个本原根本原根（或（或原根原根）.eg:3是模是模7的的本原根本原根因为因为3(7)361(mod7)本原根定义本原根定义2024/5/9 周四.本原根定义（续）本原根定义（续）例如：例如：m7，a2(m)62322（mod7）423（mod7）1因此：因此：a对模数对模数m的次数为的次数为3(m)所以：所以：2不是不是7的本元根。的本元根。2024/5/9 周四.定理（原根）定理（原根）设整数设整数m0,(g,m)=1,则则g是是m的一个原根的充要的一个原根的充要条件是：条件是：g，g2，g(m)组成模数组成模数m的一组缩系。的一组缩系。本原根判断本原根判断定理说明：如果定理说明：如果g是是m的一个原根，则模数的一个原根，则模数m的一的一组缩系可表示为形如定理中的几何级数。组缩系可表示为形如定理中的几何级数。2024/5/9 周四.2.定理：定理：设对素数设对素数p而言，如果而言，如果g是一个是一个本原根本原根(1)如果如果n是是整数，那么整数，那么gn1(modp)当且仅当当且仅当n0(modp-1)(2)如果如果j和和k都是整数，那么都是整数，那么gjgk当且仅当当且仅当jk(modp-1)本原根有关定理本原根有关定理2024/5/9 周四.问题：是否所有的正整数都有原根？问题：是否所有的正整数都有原根？本原根有关定理（续）本原根有关定理（续）例如：例如：m12(m)623，与，与m互素的正整数包括互素的正整数包括5，7，11。52（mod12）1因此，因此，5对对12的次数是的次数是272（mod12）1因此因此7对模数对模数m的次数为的次数为2112（mod12）1因此因此11对模数对模数m的次数为的次数为2因此因此m12没有原根。没有原根。2024/5/9 周四.定理（整数存在原根的必要条件）：定理（整数存在原根的必要条件）：设设m1，若，若m有原根，则有原根，则m必为下列诸数之一：必为下列诸数之一：2，4，pl，2pl（l1，p为奇素数）。为奇素数）。本原根有关定理（续）本原根有关定理（续）定理（整数存在原根的充分条件）：定理（整数存在原根的充分条件）：设设m2，4，pl，2pl（l1，p为奇素数）时，则为奇素数）时，则m有原有原根。根。定理（整数原根个数）：定理（整数原根个数）：设设m有一个原根有一个原根g，则，则m恰有恰有(m)个对模数个对模数m不同余不同余的原根，这些原根由以下集合给出：的原根，这些原根由以下集合给出：2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.原根的判断：原根的判断：一般来说，判断一般来说，判断g是否时一个素数是否时一个素数m的原根时，的原根时，不需要逐一计算不需要逐一计算g1，g2，g(m)，而仅需要计，而仅需要计算算gt(modm），其中），其中t|(m)。本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）定理（原根的计算）：定理（原根的计算）：2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）定理（原根的计算）：定理（原根的计算）：2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）一个计算原根的算法：一个计算原根的算法：2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.本原根有关定理（续）本原根有关定理（续）2024/5/9 周四.指数指数如果整数如果整数m0有一个元根有一个元根g，g，g2，g(m)(或数或数1,g，g，g2，g(m)-1）组成模数）组成模数m的一组缩系。的一组缩系。例如，例如，3是模是模7的的本原根，因此本原根，因此：313322336344355361上述六个数刚好是模数上述六个数刚好是模数m的一组缩系。的一组缩系。2024/5/9 周四.指数（续）指数（续）定义：任一整数定义：任一整数n，（，（n，m）1，必有唯一的整，必有唯一的整数数k（0k（m），满足：），满足：ngk（modm）其中其中k叫做叫做n对模数对模数m的指数，记做的指数，记做kindgn（简（简记为记为indn）(指数也叫做指数也叫做离散对数离散对数)。2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.指数的性质：设指数的性质：设g是是m的原根，如果的原根，如果(a,m)(b,m)1：指数（续）指数（续）2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.指数（续）指数（续）2024/5/9 周四.离散对数困难问题离散对数困难问题基于离散对数困难性假设，基于离散对数困难性假设，EIGamal提出了提出了EIgamal公钥公钥密码体制。密码体制。2024/5/9 周四.离散对数困难问题（续）离散对数困难问题（续）2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.模模n逆矩阵逆矩阵定理：一个平方矩阵是模定理：一个平方矩阵是模n可逆的可逆的当且仅当当且仅当它的行它的行列式和列式和n是互素的是互素的.证明：假设证明：假设M平方矩阵在模平方矩阵在模n下下有逆矩阵有逆矩阵N,则则MNI(modn)det(MN)det(M)det(N)det(I)1(modn)因为因为det(M)可逆可逆(det(M),n)=1Eg:2 2矩阵矩阵,通常的求逆为：通常的求逆为：ab-1d-b=1/(ad-bc)cd-ca2024/5/9 周四.12假如要求假如要求(mod11)的的逆逆34因为因为ad-bc=-2,需求需求-2(mod11)的的逆，因为逆，因为5(-2)1(mod11)124-24-2911/(-2)5(mod11)34-31-3175模模n逆矩阵（续）逆矩阵（续）2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.模模n平方根平方根定义定义(二次剩余）二次剩余）设设n是一个大于是一个大于1的正整数，的正整数，aZ,a0(modn).如果同余方程如果同余方程x2a(modn)有一个解有一个解1xn-1,则称则称a是是模数模数n的的二次剩余二次剩余，而，而x称之为称之为a模模n的平方根。的平方根。如果上述方程无解，则如果上述方程无解，则a称之为模数称之为模数n的非二次剩余。的非二次剩余。2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.模模n平方根（续）平方根（续）2024/5/9 周四.第第2章章信息安全数学基础（数论）信息安全数学基础（数论）本原根本原根模的幂运算模的幂运算中国剩余定理中国剩余定理同余同余基本概念基本概念有限域有限域模模n平方根平方根模模n逆矩阵逆矩阵2024/5/9 周四.有限域有限域2024/5/9 周四.有限域（续）有限域（续）2024/5/9 周四.多项式多项式2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.多项式（续）多项式（续）2024/5/9 周四.eg:GF（23）域的构造：）域的构造：p=2,z2=0,1,不可约多项式不可约多项式m(x)=1+x2+x3,多项式多项式Fx=Z2xGF（23）=Z2x/=0，1，x,x+1,x2,x2+1,x2+x,x2+x+1有限域有限域2024/5/9 周四.参考书参考书l参考书：参考书：l杨义先等，杨义先等，信息安全理论与技术信息安全理论与技术，邮电出版社，邮电出版社lMaoWenbo，ModernCryptography:TheoryandPractice，电子工业出版社，电子工业出版社，2004lBruceSchneier,AppliedCryptography,Protocols,algorithms,andsourcecodeinC(2ndEdition)(应用应用密码学密码学协议、算法与协议、算法与C源程序，源程序，吴世忠、祝世雄、吴世忠、祝世雄、张文政等译张文政等译)lPrinciplesofComputerSecurityWm.A.Conklin,McGraw-Hill,2005l信息安全原理及应用信息安全原理及应用阙喜戎等，清华大学出版阙喜戎等，清华大学出版社，社，2003年年l其他信息安全相关学术论文其他信息安全相关学术论文2024/5/9 周四.课外阅读资料课外阅读资料lMaoWenbo，ModernCryptography:TheoryandPractice，电子工业出版社，电子工业出版社，20042024/5/9 周四.AnyQuestion?Q&A2024/5/9 周四.