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

2020/4/26,.,电子科技大学计算机科学与工程学院,计算系统与网络安全ComputerSystemandNetworkSecurity,2020/4/26,.,子夏曰：“贤贤易色；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。”人际关系：父子；君臣；朋友；夫妻,数论基础,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,2.整除的基本性质(N整数集)(1)a(a0),a|0,a|a(同理bN,1|b)(2)b|a,cb|ca(3)a|b,b|ca|c.（传递性）(4)a|b,a|ca|(xb+yc)(x,yN)(5)b|a且a0|b|a|(6)cb|ca,b|a,1.定义：设整数a和b,且a0，如果存在整数k使得b=ak，那么就说a整除a（或b能被a整除），记作a|b，或者说b是a的倍数。举例：3|15,-15|60,整除定义及性质,2020/4/26,.,证明：（1）作一个整数序列（2）反证法,带余数除法：如果a，b是两个整数，其中b0，则存在两个整数q和r，使得abqr（0rb）成立，且q和r是唯一的。,带余数除法,2020/4/26,.,非负最小剩余的性质：（1）=+（2）=-（3）=,定义（非负最小剩余）abqr（0rb）中r叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，b常常省略）,带余数除法,2020/4/26,.,1.定义：一个大于1的整数p，只能被1或者是它本身整除,而不能被其他整数整除，则称整数为素数(primenumber)，否则就叫做合数(composite)。eg素数（2，3，5，7，11，13等）合数（4，6，8，9，12等）,素数定义及素数个数定理,2020/4/26,.,2.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时：,素数补充定理,2020/4/26,.,2.补充定理(2)：若p是一个素数，a是任一整数，则有p|a或(p,a)=1,素数补充定理（续）,2020/4/26,.,素数补充定理（续）,2.补充定理：p为素数，且p|ab,那么p|a或p|b。更一般地，如果abz能够被素数p整除，那么a,b,z中的某个数必能被p整除。,2020/4/26,.,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个素数外的另外一个素数。因此与假设矛盾。,2020/4/26,.,素数定义及素数个数定理,3.素数个数定理（2）：设(x)是小于x的素数个数，则(x)x/lnx,即x时，比值(x)/(x/lnx)1eg:可以估算100位素数的个数：(10100)-(1099)10100/(ln10100)1099/(ln1099)3.9*1097.,2020/4/26,.,1.整数的唯一分解定理定理（算术基本定理）:设nZ,有分解式,n=p1e1p2e2.pmem,其中p1,p2,pmZ+是互不相同的素数,e1,e2,emZ+,并且数对(p1,e1),(p2,e2),(pm,em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）.,eg:504=23327,1125=3253,整数的唯一分解定理,2020/4/26,.,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.,2020/4/26,.,(2)欧几里得(Euclid)算法设a,bN,ab0,用以下方法可求出gcd(a,b).,最大公约数的欧几里得算法,2020/4/26,.,Euclid算法实例：求gcd(132,108).,最大公约数的欧几里得算法（续）,2020/4/26,.,欧几里得算法（例1）,gcd（1180，482）2,求：gcd（1180，482）,最大公约数的欧几里得算法（续）,2020/4/26,.,欧几里得算法（例2）：求gcd(12345,1111),最大公约数的欧几里得算法（续）,2020/4/26,.,欧几里得算法抽象,规律：余数除数被除数忽略,最大公约数的欧几里得算法（续）,2020/4/26,.,欧几里得算法实现,最大公约数的欧几里得算法（续）,2020/4/26,.,特别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+nb,3.定理设a,bZ+,则存在m,nZ使得gcd(a,b)=ma+nb.,扩展的欧几里得算法,2020/4/26,.,计算出了gcd(a,b);但是并没有计算出两个数m，n来，使得：ma+nb=gcd(a,b),扩展的欧几里得算法的结果,计算出了gcd(a,b);计算出两个数m，n来，使得：ma+nb=gcd(a,b),扩展的欧几里得算法（续）,欧几里得算法的结果,2020/4/26,.,利用该方法我们可以求密码学方程ax+by=d的解,这里d=(a,b),例如:求132x+108y=12的解,解：12=gcd(132,108)12=108-424=108-4(132-1081)=1084132+4108=5*1084*132,扩展的欧几里得算法（续）,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,证明：必要性:设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,s1，如果gcd(a,n)=1,则:a(n)1modn.,eg:求7803的后三位数字解：7803（mod1000）的结果(1000)=1000(1-1/2)(1-1/5)=400，有7803(7400)273343(mod1000),费马小定理和欧拉定理（续）,2020/4/26,.,推论（Fermat小定理）:p素数,a是整数且不能被p整除,则:ap-11modp.,费马小定理和欧拉定理（续）,例如：求253(mod11)=?由Fermat小定理:210=10241(mod11)253=(210)52315238(mod11),2020/4/26,.,（1）通常情况下，如果2n-11(modn),n为素数,然而,也有例外:561=31117是合数,但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算法,费马小定理和欧拉定理的应用,2020/4/26,.,解：（1）由费尔马定理2100（mod1001）1（mod101）（2）243210(2100)4322102101024(mod101)=14,eg:计算243210（mod101）,欧拉定理的应用,2020/4/26,.,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.,一次同余式,2020/4/26,.,(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),一次同余式（续）,2020/4/26,.,定理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.,一次同余式的解,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,孙子算经中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”孙子问题等同于下面这样一个问题：已知x=2mod3，x=3mod5且x=2mod7，求整数x。,中国剩余定理,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,中国剩余定理(孙子: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)(1ir),中国剩余定理（续）,2020/4/26,.,例如:求以下同余方程组的解：x5mod7x3mod11x10mod13,中国剩余定理解同余方程组,解：r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10;模M=m1m2m3=1001,M1=M/m1=m2m3=143,M2=91,M3=77.y1=M1-1(modm1)=143-1(mod7)=5,y2=4,y3=12.解为:x=b1M1y1+b2M2y2+b3M3y3(modM)=51435+3914+107712(mod1001)=13907(mod1001)=894验证:x=894=1277+5=5(mod7),2020/4/26,.,中国剩余定理：,其中：m=miMiMiMi=1(modm),中国剩余定理（续）,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,例如（孙子算经）解法：表格法,中国剩余定理求解同余方程组,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,中国剩余定理（续）,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,计算Xa(modn),其中x,a,nZ+Eg:计算21234(mod789)一种有效的方法：2416282562162562492324923426434236721283672559225655923725123725802102458022861234=1024+128+64+16+2（1234=(10011010010)2）21234=286559367494481(mod789),模的幂运算,优势：模的幂运算可快速完成，并且不需要太大内存,2020/4/26,.,模的幂运算（续）,但是，上述计算过程并不适合于计算机程序实现。为此，可以采用“重复平方-乘”运算来进行指数模运算。,2020/4/26,.,模的幂运算（续）,重复平方-乘算法,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,整数的次数,由欧拉定理知道：如果(a,m)1，m1，则a(n)1(modm)也就是说，如果(a,m)1，m1，则存在一个整数满足:a1(modm),定义（整数的次数）：若(a,m)1，m1，则使得同余式a1(modm)成立的最小正整数叫做a对模m的次数。,2020/4/26,.,整数的次数（续）,定理：设a对模数m的次数为l，an1（modm），则l|n。,证明：如果结论不成立，则必有两个整数q和r，使得：nqlr（0rl）而1ana(qlr)aqlarar(modm)，因此与l的定义相违背。,推论：设a对模数m的次数为l，则l|(m)。,2020/4/26,.,整数次数的计算：因为l|(m)，因此可以通过计算以下对模数m的值求出。,整数的次数（续）,例如：m7，a2(m)62322（mod7）423（mod7）1因此a对模数m的次数为3。,2020/4/26,.,整数次数的有效计算方法（1）：,整数的次数（续）,2020/4/26,.,整数次数的有效计算方法（1）：,整数的次数（续）,2020/4/26,.,整数次数的有效计算方法（2）：,整数的次数（续）,2020/4/26,.,整数的次数（续）,定理：设a对模数m的次数为l，1,a,a2,，al-1对模数m两两不同余。,证明：如果结论不成立，则有某对j，k（0jkl-1，使得：ajak（modm）因此：ak-j1（modm）而10,(g,m)=1,则g是m的一个原根的充要条件是：g，g2，g(m)组成模数m的一组缩系。,本原根判断,定理说明：如果g是m的一个原根，则模数m的一组缩系可表示为形如定理中的几何级数。,2020/4/26,.,2.定理：设对素数p而言，如果g是一个本原根(1)如果n是整数，那么gn1(modp)当且仅当n0(modp-1)(2)如果j和k都是整数，那么gjgk当且仅当jk(modp-1),本原根有关定理,2020/4/26,.,问题：是否所有的正整数都有原根？,本原根有关定理（续）,例如：m12(m)623，与m互素的正整数包括5，7，11。52（mod12）1因此，5对12的次数是272（mod12）1因此7对模数m的次数为2112（mod12）1因此11对模数m的次数为2因此m12没有原根。,2020/4/26,.,定理（整数存在原根的必要条件）：设m1，若m有原根，则m必为下列诸数之一：2，4，pl，2pl（l1，p为奇素数）。,本原根有关定理（续）,定理（整数存在原根的充分条件）：设m2，4，pl，2pl（l1，p为奇素数）时，则m有原根。,定理（整数原根个数）：设m有一个原根g，则m恰有(m)个对模数m不同余的原根，这些原根由以下集合给出：,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,原根的判断：一般来说，判断g是否时一个素数m的原根时，不需要逐一计算g1，g2，g(m)，而仅需要计算gt(modm），其中t|(m)。,本原根有关定理（续）,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,本原根有关定理（续）,定理（原根的计算）：,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,本原根有关定理（续）,定理（原根的计算）：,2020/4/26,.,本原根有关定理（续）,一个计算原根的算法：,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,本原根有关定理（续）,2020/4/26,.,指数,如果整数m0有一个元根g，g，g2，g(m)(或数1,g，g，g2，g(m)-1）组成模数m的一组缩系。,例如，3是模7的本原根，因此：313322336344355361上述六个数刚好是模数m的一组缩系。,2020/4/26,.,指数（续）,定义：任一整数n，（n，m）1，必有唯一的整数k（0k（m），满足：ngk（modm）其中k叫做n对模数m的指数，记做kindgn（简记为indn）(指数也叫做离散对数)。,2020/4/26,.,指数（续）,2020/4/26,.,指数（续）,2020/4/26,.,指数（续）,2020/4/26,.,指数的性质：设g是m的原根，如果(a,m)(b,m)1：,指数（续）,2020/4/26,.,指数（续）,2020/4/26,.,指数（续）,2020/4/26,.,指数（续）,2020/4/26,.,离散对数困难问题,基于离散对数困难性假设，EIGamal提出了EIgamal公钥密码体制。,2020/4/26,.,离散对数困难问题（续）,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,模n逆矩阵,定理：一个平方矩阵是模n可逆的当且仅当它的行列式和n是互素的.证明：假设M平方矩阵在模n下有逆矩阵N,则MNI(modn)det(MN)det(M)det(N)det(I)1(modn)因为det(M)可逆(det(M),n)=1Eg:22矩阵,通常的求逆为：ab-1d-b=1/(ad-bc)cd-ca,2020/4/26,.,12假如要求(mod11)的逆34因为ad-bc=-2,需求-2(mod11)的逆，因为5(-2)1(mod11)124-24-2911/(-2)5(mod11)34-31-3175,模n逆矩阵（续）,2020/4/26,.,第2章信息安全数学基础（数论）,2020/4/26,.,模n平方根,定义(二次剩余）设n是一个大于1的正整数，aZ,a0(modn).如果同余方程x2a(modn)有一个解1xn-1,则称a是模数n的二次剩余，而x称之为a模n的平方根。如果上述方程无解，则a称之为模数n的非二次剩余。,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,.,模n平方根（续）,2020/4/26,