信息安全数学基础new(数论).pptVIP

2019/4/30,第2章 信息安全数学基础,2010、07,2019/4/30,第2章 信息安全数学基础,2.4 模的幂运算,2.3 中国剩余定理,2.2 同余,2.1 基本概念,2.5 本 原 根,2019/4/30,第2章 信息安全数学基础,2.1 基本概念,2019/4/30,2.整除的基本性质( 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,yN) (5) b|a 且a0 |b|a| (6) cb|ca, b|a,1.定义： 设整数a和b,且a 0，如果存在整数k使得b=ak， 那么就说a整除b（或b能被a整除），记作a|b，或者说b是a的倍数。 举例：3|15, -15|60,整除定义及性质,2019/4/30,带余数除法： 如果a，b是两个整数，其中b0，则存在两个整数q和r，使得abqr（0rb）成立，且q和r是唯一的。,带余数除法,2019/4/30,非负最小剩余的性质： （1） = + （2） = - （3） = ,定义（非负最小剩余） abqr（0rb）中r叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，b常常省略）,带余数除法,2019/4/30,1.定义： 一个大于1的整数p，只能被1或者是它本身整除，而不能被其他整数整除，则称整数为素数(prime number)，否则就叫做合数(composite)。 eg 素数（2，3，5，7，11，13等） 合数（4，6，8，9，12等）,素数定义及素数个数定理,2019/4/30,2.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时：,素数补充定理,2019/4/30,2.补充定理(2)： 若p是一个素数，a是任一整数，则有p|a 或 (p，a)=1,素数补充定理（续）,2019/4/30,素数补充定理（续）,2.补充定理： p为素数，且p|ab，那么p|a或p|b。 更一般地，如果abz能够被素数p整除，那么a,b,z中的某个数必能被p整除。,2019/4/30,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个素数外的另外一个素数。 因此与假设矛盾。,2019/4/30,素数定义及素数个数定理,3.素数个数定理（2）： 设(x)是小于x的素数个数，则 (x) x / lnx, 即x时，比值(x) /(x / lnx) 1 eg: 可以估算100位素数的个数： (10100) - (1099) 10100/(ln10100) 1099/(ln1099) 3.9 * 1097.,2019/4/30,1.整数的唯一分解定理定理（算术基本定理）: 设nZ， 有分解式， n = p1e1p2e2.pmem，其中p1, p2, pmZ+是互不相同的素数， e1,e2,emZ+, 并且数对(p1, e1), (p2, e2),(pm, em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）.,eg: 504 = 23327, 1125 = 3253,整数的唯一分解定理,2019/4/30,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。,2019/4/30,(2) 欧几里得(Euclid)算法 设a, bN, ab0, 用以下方法可求出 gcd(a,b)。,最大公约数的欧几里得算法,2019/4/30,Euclid算法实例：求 gcd(132, 108).,最大公约数的欧几里得算法（续）,2019/4/30,欧几里得算法（例1）,gcd（1180，482）2,求：gcd（1180，482）,最大公约数的欧几里得算法（续）,2019/4/30,欧几里得算法（例2）：求gcd(12345，1111),最大公约数的欧几里得算法（续）,2019/4/30,欧几里得算法抽象,规律：余数除数被除数忽略,最大公约数的欧几里得算法（续）,2019/4/30,欧几里得算法实现,最大公约数的欧几里得算法（续）,2019/4/30,特别a, b为素数时gcd(a,b)=1，存在 ma+nb=1. 上述求 rn = ma+nb的方法叫做扩展的Euclid算法 利用该方法我们可以求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+nb,3.定理 设a, bZ+, 则存在m, nZ使得gcd(a,b)=ma+nb.,扩展的欧几里得算法,2019/4/30,计算出了gcd(a,b); 但是并没有计算出两个数m，n来，使得： ma+nb=gcd(a,b),扩展的欧几里得算法的结果,计算出了gcd(a,b); 计算出两个数m，n来，使得： ma+nb=gcd(a,b),扩展的欧几里得算法（续）,欧几里得算法的结果,2019/4/30,利用该方法我们可以求密码学方程ax+by=d的解，这里d= (a,b),例如: 求132x+108y = 12的解,解： 12=gcd(132,108) 12 = 108 - 424 = 108 - 4 (132-108 1) = 108 4 132 +4 108 =5*108 4*132,扩展的欧几里得算法（续）,2019/4/30,第2章 信息安全数学基础,2.2 同 余,2019/4/30,证明： 必要性: 设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|m, r=s, ab (mod m). 证毕,2.定理 设 a，bZ，mZ+， 则 ab (mod m) m|(a-b).,1.定义 设a，bZ， mZ+， 如果a和b被m除所得余数相同，则称a和b关于模数m同余，记为ab (mod m).,同余,2019/4/30,4.模运算的性质 设mZ+, ab (mod m), xy (mod m), 则有 (1) a+xb+y (mod m) （加法） (2) a-x b-y (mod m) （减法） (3) ax by (mod m) （乘法）,3.同余的性质 设a,bZ, mZ+ (1) 自反性：aZ aa (mod m). (2) 对称性：ab (mod m) ba (mod m). (3) 传递性：ab，bc (mod m) ac (mod m).,同余及模运算性质,2019/4/30,例1： 求解2x73（mod 17） 解：2x37 2x4 x2 x15（mod 17）,4.模运算的性质 （4）除法：相对复杂 如果：12x24，那么：3x8 如果：12x24（mod 3），那么：3x8（mod 3）？ 定理：设整数a，b，c，n（n0），gcd(a，n)1，如果abac（mod n），则bc（mod n）。,计算成立的原因：gcd（2，17）1,模运算的除法运算及其性质,2019/4/30,例2： 求解5x613（mod 11） 解：5x136 5x7（mod 11） x=7/5 ? 注意到：7182940（mod 11） 所以： 5x7（mod 11） 5x40（mod 11） x8（mod 11）,计算成立的原因：gcd（5，11）1,模运算的除法运算及其性质（续）,2019/4/30,5.模m的乘法逆元 定义：设mZ+， x， yZ， 如果xy1 (mod m), 则称y是x的模m乘法逆元，记为: y=x-1,乘法逆元,例1： 2 31 (mod 5) 3是2的模5乘法逆元, 2是3的模5乘法逆元. 2 81 (mod 5) 8是2的模5乘法逆元. 注意：模m乘法逆元不唯一！ 但是，如果求一个与模数互素的数的乘法逆元，则是唯一的。,2019/4/30,欧几里德算法与乘法逆元 如果算法gcd（a，b）输出rm1，则b有乘法逆元 如果求出了ma+nb=1中的整数m，n，则可以求出b（mod a）的乘法逆元。 欧几里得算法没有给出b的乘法逆元b1 如何求b1 ？ 扩展的欧几里德算法,扩展欧几里德算法与乘法逆元,2019/4/30,扩展欧几里德算法与乘法逆元（续）,2019/4/30,例：求 28 mod 75的乘法逆元(a=75,b=28),扩展欧几里德算法与乘法逆元（续）,2019/4/30,例：求 11 mod 26的乘法逆元(a=26,b=11),解： 26 = 11*2 + 4 11 = 4*2 + 3 4 = 3*1 + 1,所以：3r0-7r1=1,所以：11的逆元为19。,2019/4/30,扩展欧几里德算法,2019/4/30,第2章 信息安全数学基础,2.3 中国剩余定理,2019/4/30,孙子算经中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 孙子问题等同于下面这样一个问题： 已知 x=2mod3，x=3mod5且x=2mod7，求整数x。,中国剩余定理,2019/4/30,中国剩余定理（续）,2019/4/30,中国剩余定理（续）,2019/4/30,中国剩余定理（续）,2019/4/30,中国剩余定理(孙子: 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),中国剩余定理（续）,2019/4/30,例如:求以下同余方程组的解： x 5 mod 7 x 3 mod 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 1001) = 894 验证: x = 894 = 127 7+5 = 5 (mod 7),7=143*1-136 143=136*1+7 136=7*19+3 7=3*2+1 所以：41r0-2r1=1 -2*143 = 1 mod 7,2019/4/30,其中： m=miMi MiMi=1 (mod m),中国剩余定理（续）,中国剩余定理：,2019/4/30,中国剩余定理（续）,3=35*(-1)+32 35=32*1+3 32=3*10+2 3=2*1+1 所以：-12r0-r1=1,2019/4/30,例如 孙子算经:“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 解法：表格法 x b1*M1*y1+b2*M2*y2+br*Mr*yr (mod M) M=m1m2mr Mi = M/mi yi=Mi-1 =Mi mod mi,中国剩余定理求解同余方程组,2019/4/30,练习1,解同余方程：6x=7 mod 23,答：X=5 mod 23,2019/4/30,练习2：,解同余方程：81x3+24x2+5x+23=0 mod 7,练习3： 解同余方程: 3x2+11x-20=0 mod 105,2019/4/30,中国剩余定理（续）,2019/4/30,中国剩余定理（续）,2019/4/30,中国剩余定理（续）,2019/4/30,第2章 信息安全数学基础,2.4 模的幂运算,2019/4/30,计算Xa ( mod n) ,其中 x, a, n Z+ Eg: 计算21234 (mod 789) 一种有效的方法： 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),模的幂运算,优势： 模的幂运算可快速完成，并且不需要太大内存,2019/4/30,模的幂运算（续）,但是，上述计算过程并不适合于计算机程序实现。为此，可以采用“重复平方-乘”运算来进行指数模运算。,2019/4/30,模的幂运算（续）,重复平方-乘算法,2019/4/30,请用平方-乘算法计算： （1） 3460 mod 51 （2） 34589 mod 101,2019/4/30,第2章 信息安全数学基础,2.5 本 原 根,2019/4/30,整数的次数,由欧拉定理知道：如果(a, m)1，m1，则a(n) 1(mod m) 也就是说，如果(a, m)1，m1，则存在一个整数满足: a 1(mod m),定义（整数的次数）： 若(a, m)1，m1，则使得同余式 a 1(mod m) 成立的最小正整数叫做a对模m的次数。,2019/4/30,整数的次数（续）,定理：设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)。,2019/4/30,整数次数的计算： 因为l|(m)，因此可以通过计算以下对模数m的值求出。,整数的次数（续）,例如：m7，a2 (m)623 22（mod 7）4 23（mod 7）1 因此a对模数m的次数为3。,2019/4/30,整数次数的有效计算方法（1）：,整数的次数（续）,2019/4/30,整数次数的有效计算方法（1）：,整数的次数（续）,2019/4/30,整数次数的有效计算方法（2）：,整数的次数（续）,2019/4/30,整数的次数（续）,定理：设a对模数m的次数为l，1,a, a2,，al-1对模数m两两不同余。,证明： 如果结论不成立，则有某对j，k（0jkl-1，使得： aj ak（mod m） 因此： ak-j 1（mod m） 而1k-jl-1，因此与l的定义相违背。,2019/4/30,一般说来，当p为素数时，模p本原根是一个数，它的幂构成模p的同余类，且存在(p-1) 个模p的本原根。 例如： 3是模7的本原根，3(mod7)的幂运算： 31 3 32 2 33 6 34 4 35 5 36 1,定义（原根） 设整数m0,(g,m)=1, 如果整数g对m的次数为(m) ，则g叫做m的一个本原根（或原根）. eg: 3是模7的本原根 因为3 (7) 36 1(mod 7),本原根定义,2019/4/30,本原根定义（续）,例如：m7，a2 (m)623 22（mod 7）4 23（mod 7）1 因此： a对模数m的次数为3 (m) 所以： 2不是7的本元根。,2 (7) mod 7 =1,2019/4/30,定理（原根） 设整数m0,(g,m)=1,则g是m的一个原根的充要条件是： g，g2，g(m)组成模数m的一组缩系。,本原根判断,定理说明：如果g是m的一个原根，则模数m的一组缩系可表示为形如定理中的几何级数。,2019/4/30,2.定理： 设对素数p而言，如果g是一个本原根 (1)如果n是整数，那么gn 1(mod p)当且仅当 n0(mod p-1) (2)如果j和k都是整数，那么gj gk当且仅当j k(mod p-1),本原根有关定理,2019/4/30,问题：是否所有的正整数都有原根？,本原根有关定理（续）,例如：m12 (m)623，与m互素的正整数包括5，7，11。 52（mod 12）1 因此，5对12的次数是2 72（mod 12）1 因此7对模数m的次数为2 112（mod 12）1 因此11对模数m的次数为2 因此m12没有原根。,2019/4/30,定理（整数存在原根的必要条件）： 设m1，若m有原根，则m必为下列诸数之一：2，4，pl，2pl（l1，p为奇素数）。,本原根有关定理（续）,定理（整数存在原根的充分条件）： 设m2，4，pl，2pl（l1，p为奇素数）时，则m有原根。,定理（整数原根个数）： 设m有一个原根g，则m恰有(m)个对模数m不同余的原根，这些原根由以下集合给出：,2019/4/30,本原根有关定理（续）,2019/4/30,原根的判断： 一般来说，判断g是否时一个素数m的原根时，不需要逐一计算g1，g2，g(m)，而仅需要计算gt(modm），其中t|(m)。,本原根有关定理（续）,2019/4/30,本原根有关定理（续）,2019/4/30,本原根有关定理（续）,定理（原根的计算）：,2019/4/30,本原根有关定理（续）,2019