保障与安全数论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数论导引,1 素数和数的互素,除数(因子)的概念：设z为所有全体整数构成的集合，若 b0且 使得a=mb ,此时称b整除a.记为ba,还称b为a的除数(因子).,注:若a=mb+r且0r1被称为素数是指p的因子仅有1,-1,p,-p。,定义,：,若a,x mod n=1,，则称a与,x,对于模n互为逆元。,用Euclid算法求乘法逆元,若a和n互素，则a在模n下有逆元。,算术基本定理：,任何一个不等于0的正整数a都可以写成唯一的表达式,aP,1,1,P,2,2,P,t,t,，,这里P,1,P,2,P,3,P,t,是素数，其中,i,0,最大公约数：,若a,b,cz，如果ca，cb，称c是a和b的公约数。正,整数d称为a和b的最大公约数，如果它满足,d是a和b的公约数。,对a和b的任何一个公约数c有cd。,注,：1,*,.等价的定义形式是：,gcd（a,b）maxk ka，kb,2,*,若gcd（a,b）=1，称a与b是互素的,。,模 算术,全体整数,Z,构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合,z,为,整数环,。整数环,z,对除法运算不封闭。,带余除法：,az,0,，,可找出两个唯一确定的整数,q,和,r,使,a=,qm+r,0=r1）分成一些两两不交的等价类。,3,*,.,整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,mk+(m-1);kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,11,自反性,对称性,传递性,4,*,.,对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘（可交换的、可结合的、可分配的,）而且，简化运算每个中间结果的模n运算，其作用与先进行全部运算，然后再简化模n运算是一样的。,(1)a(mod m)b(mod m)mod m=(ab)(mod m),(2)a(mod m),b(mod m)mod m=a,b(mod m),(3)(a,b)(mod m)+(a,c)(mod m)mod m=(a,(b+c)(mod m),例1,15,2,mod 12=(3*3)mod 12=9,例2,通过同余式演算证明5,60,1是56的倍数，2,23,1是47的倍数。,解：注意5,3,=12513(mod56),于是有5,6,1691(mod56),对同余式的两边同时升到10次幂，即有565,60,-1。,注意2,6,=64-30(mod47),于是,2,23,=(2,6,),3,2,5,=(2,6,2,6,)2,6,2,5,900,(-30)(32)mod(47),(7)(-30)(32)(mod47),(-30)(224)(mod47),(-30)(36)(mod47),(-1080)(mod47),1(mod47),于是有 472,23,-1,求11,7,(mod13)，,11,2,=121 4(mod13)，11,4,4,2,3(mod13)，,11,7,11,4 3,2(mod13),定理,：,(消去率)对于abac（mod m）来说，若(a,m)1则bc(mod m),5,*,.,一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b,定理,：,如记(a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。,证明：略。（从ax+my=b入手）,6,*,.,整数环z模正整数m得到的剩余类集合可以记为z,m,(或z/(m)z,m,=0,1,m-1,在4中已说明z,m,对剩余类的加法，乘法是封闭的，可列出它们的加乘表。我们称z,m,为剩余类环（或同余类环）,7,*,.,在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。,例z,12,中：3*4=12=0,说明，,z,m,中的元素可分为两类，一类是零因子,，即若z,m,0存在z,m,且0，有*=0，称，都为z,m,中的零因子。,另一类是可逆元,，即若z,m,，存在z,m,使*=1，此时,互为各自的逆元，记,-1,=；,-1,=,定理：,剩余类环z,m,中元素=a为z,m,的可逆元,(a,m)=1,要证明这个定理，只需证明下列引理：,引理,：,任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,tz，使dsatb。,证明（,自己看),不妨设b0，用辗转相除法，先用b去除a，得,a=q,1,b+r,1,0=r,1,b;(1),如果r,1,=0，停止，否则再用r,1,去除b，得,b=q,2,r,1,+r,2,0=r,2,r,1,;(2),如果r,2,=0，停止，否则再用r,2,去除r,1,，得,r,1,=q,3,r,2,+r,3,;0=r,3,r,2,;(3),等等，这样一直进行下去，可得一系列关系式：,r,k-3,=q,k-1,r,k-2,+r,k-1,0=r,k-1,r,k-2,;(k-1),r,k-2,=q,k,r,k-1,+r,k,0=r,k,r,2,r,3,r,4,r,k,=0,是严格递降的一串非负整数，故最后总会,出现余数为0的情形：,r,k-1,=q,k+1,r,k,(k+1),所以，进行有限步必停止，此时d=r,k,=(a,b)定成立，这是因为,1,*,.可见r,k,为a和b的公约数，只要按倒序分析自然有此结论。,2,*,.a和b的任何一个公约数c都是r,k,的约数，只要按正序分析，自然可知。,为证定理的后一部分，将式(1)做移项有,r,1,=s,1,a+t,1,b（其中s,1,=1,t,1,=-q,1,）再将式(2)右端通过移项变为r,2,=s,2,a+t,2,b,这样一直下去，最后得d=r,k,=s*a+t*b,s,tz,欧几里得（Euclid）算法,是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。,Euclid算法是基于下面一个基本结论：,对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,a mod b)。即a，b的公因子集合与b，a mod b的公因子集合相等，两个集合的最大值也相等。,例如：gcd(55,22)=gcd(22,55 mod 22)=gcd(22,11)=gcd(11,0)=11。,在求两个数的最大公因子时，可重复使用以上结论。,例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6,gcd(11,10)=gcd(10,1)=gcd(1,0)=1。,欧几里得算法,例子,：求gcd(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。,解：252=1*180+72(1),180=2*72+36 (2),72=2*36(3),得gcd(180,252)=36，同时有,72=252-1*180 (1,),由(2)得36=180-2*72 (2,)将(1,)代入(2,)，即得 36=180-2*(252-180)=3*180-2*252,求gcd(1970,1066)=2,求gcd(1970,1066)。,1970=11066+904,gcd(1066,904),1066=1904+162,gcd(904,162),904=5162+94,gcd(162,94),162=194+68,gcd(94,68),94=168+26,gcd(68,26),68=226+16,gcd(26,16),26=116+10,gcd(16,10),16=110+6,gcd(10,6),10=16+4,gcd(6,4),6=14+2,gcd(4,2),4=22+0,gcd(2,0),因此gcd(1970,1066)=2。,计算逆元的方法有,1、用欧拉推广公式解：,x,=(ba,(n)-1,)modn,2、用欧几里德算法解：,x,=(b(a,-1,modn)modn,通常欧几里德算法在计算逆元方面较欧拉推广更快，特别是500位范围内的数。,Euclid算法就是用这种方法，因gcd(a,b)=gcd(|a|,|b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f d。,Euclid（f,d）,1.Xf;Yd；,2.if Y=0 then return X=gcd(f,d)；,3.R=X mod Y；,4.X=Y；,5.Y=R；,6.goto 2。,求乘法逆元,如果gcd(a,b)=1，则b在mod a下有乘法逆元（不妨设ba），即存在一x(x0，用辗转相除法，先用b去除a，得 r,0,=q,1,r,1,+r,2,0r,2,r,1,r,1,=q,2,r,2,+r,3,0r,3,r,2,;,等等，这样一直进行下去，可得一系列关系式：,r,m-2,=q,m-1,r,m-1,+r,m,0r,m,d）,1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);,2.if Y3=0 then return X3=gcd(f,d)；no inverse;,3.if Y3=1 then return Y3=gcd(f,d)；Y2=d-1 mod f;,4.Q=X3Y3；,5.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);,6.(X1,X2,X3)(Y1,Y2,Y3);,7.(Y1,Y2,Y3)(T1,T2,T3);,8.goto 2。,算法中的变量有以下关系：,fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3,在算法EUCLID(f,d)中，X等于前一轮循环中的Y，Y等于前一轮循环中的X mod Y。而在算法Extended Euclid(f,d)中，X3等于前一轮循环中的Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一轮循环中的Y3除X3的余数，即X3 mod Y3，可见Extended Euclid(f,d)中的X3、Y3与Euclid(f,d)中的X、Y作用相同，因此可正确产生gcd(f,d)。,如果gcd(f,d)=1，则在最后一轮循环中Y3=0，X3=1，因此在前一轮循环中Y3=1。由Y3=1可得:fY1+dY2=Y3，fY1+dY2=1，dY2=1+(-Y1)f，dY21 mod f，所以Y2d,-1,mod f。,例 用扩展Euclidean算法计算28,-1,mod,75,解：75=2*28+19 （1）,28=,1*19+9 （2）,19=2*9+1 （3）,逆推19=75-2*28 （4）,9=28-1*19 （5）,1=19-2*9 （6）,把（4）、（5）代入（6）得,1=3*75-8*28,因而28,-1,mod,75=-8,mod,75=67,作业：编程计算17,-1,mod101，,357,-1,mod 1234。,17,-1,mod101 6,357,-1,mod 1234,Gcd(550,1759)=1,550关于模1759的乘法逆元是355，即550*350 1mod1759,3 Format定理和Euler定理,Format定理,：如果p是素数并且a是正整数,p,a(a不能被p整除，,即a不是p的倍数,),，那么，a,p-1,1(mod p),或者：若p是素数，则a,p,mod p=a,例：若 4,6,mod 7=4096 mod 7=1,则,4,7,mod 7=16384 mod 7=4,注：易见对gcd（a，p）1 有a,p,a(modp),Euler 函数,欧拉函数(n)(Euler函数(n)：,当n1 时，(1)1；当n1时