7保障与安全数论06

1,数论导引,1素数和数的互素除数(因子)的概念：设z为所有全体整数构成的集合，若b0且使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子).注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。定义：若axmodn=1，则称a与x对于模n互为逆元。用Euclid算法求乘法逆元若a和n互素，则a在模n下有逆元。,2,算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt，这里P1P2P3Pt是素数，其中i0最大公约数：若a,b,cz，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有cd。注：1*.等价的定义形式是：gcd（a,b）maxkka，kb2*若gcd（a,b）=1，称a与b是互素的。,3,模算术全体整数Z构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环。整数环z对除法运算不封闭。带余除法：az0，可找出两个唯一确定的整数q和r,使a=qm+r,00，用辗转相除法，先用b去除a，得a=q1b+r1,0=r1b;(1)如果r1=0，停止，否则再用r1去除b，得b=q2r1+r2,0=r2r1;(2)如果r2=0，停止，否则再用r2去除r1，得r1=q3r2+r3;0=r3r2;(3)等等，这样一直进行下去，可得一系列关系式：rk-3=qk-1rk-2+rk-1,0=rk-1rk-2;(k-1)rk-2=qkrk-1+rk,0r3r4rk=0是严格递降的一串非负整数，故最后总会出现余数为0的情形：rk-1=qk+1rk(k+1)所以，进行有限步必停止，此时d=rk=(a,b)定成立，这是因为1*.可见rk为a和b的公约数，只要按倒序分析自然有此结论。2*.a和b的任何一个公约数c都是rk的约数，只要按正序分析，自然可知。为证定理的后一部分，将式(1)做移项有r1=s1a+t1b（其中s1=1,t1=-q1）再将式(2)右端通过移项变为r2=s2a+t2b这样一直下去，最后得d=rk=s*a+t*b,s,tz,11,欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。即a，b的公因子集合与b，amodb的公因子集合相等，两个集合的最大值也相等。例如：gcd(55,22)=gcd(22,55mod22)=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。,欧几里得算法,12,例子：求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,13,求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。,14,计算逆元的方法有1、用欧拉推广公式解：x=(ba(n)-1)modn2、用欧几里德算法解：x=(b(a-1modn)modn通常欧几里德算法在计算逆元方面较欧拉推广更快，特别是500位范围内的数。,15,Euclid算法就是用这种方法，因gcd(a,b)=gcd(|a|,|b|)，因此可假定算法的输入是两个正整数，设为d，f，并设fd。Euclid（f,d）1.Xf;Yd；2.ifY=0thenreturnX=gcd(f,d)；3.R=XmodY；4.X=Y；5.Y=R；6.goto2。,16,求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设ba），即存在一x(x0，用辗转相除法，先用b去除a，得r0=q1r1+r2,0r2r1r1=q2r2+r3,0r3r2;等等，这样一直进行下去，可得一系列关系式：rm-2=qm-1rm-1+rm,01时，(n)等于比n小而与n互素的正整数的个数。例1(3)=(4)=(6)=2，(5)=4，(7)=6例2以n24为例，比24小而与24互素的正整数为：1，5，7，11，13，17，19，23因此，我们有(24)8。易见，若p为素数，则(p)p1。n12，(12)？,23,注：1*.若p，q都为素数且pq，此时有(pq)(p)(q)=（p1）（q1）证明（自学）：考虑zpq剩余类的集合是0，1，2，（pq-1）集合中与pq不互素的元素子集为p,2p,(q-1)p和子集q,2q,(p-1)q以及0，于是若设npq，有(n)=pq-(q-1)+(p-1)+1=(p-1)(q-1)=(p)(q)例：(21)=(3*7)=(3)(7)=2*6=12.,24,2*.设n=p1e1p2e2prer，其中p1,p2,pr为互异素数，则(n)=p1e1-1p2e2-1prer-1(p1-1)(p2-2)(pr-1)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/pr)例3：n=21=3*7，有两个素数3和7，这样，(21)=21(1-1/3)(1-1/7)=12即21中有12个整数与21是互素的:1,2,4,5，8,10，11,12，13,16，17,19n24=3*8=3*23，(24)=24(1-1/3)*(1-1/2)=8即24中有8个整数与24是互素的：1，5，7，11，13，17，19，23,25,欧拉定理（Euler）：若整数a与整数n互素，则a(n)1(modn)推论：若a与n互素，则a与a(n)-1互为逆元。例4求5关于模7的乘法逆元。解由于7是素数，(7)=7-1=6，所以5关于模7的乘法逆元为56-1mod7=55mod7=3注：1*.np时，有ap-11(modp)为Format定理！2*.易见a(n)+1a(modn)3*.若n=pq，p与q为相异素数，取0mn，若gcd(m,n)1，有m(n)+1m(modn)，也即m(p-1)(q-1)+1m(modn).4*.由(m(n)k1k(modn)知mk(n)1(modn)，进一步mk(n)+1m(modn)mk(p-1)(q-1)+1m(modn),推广欧拉定理：若ab(modr)，则对于任意幂m，有ambm(modr)am(r)1(modr)若ab(modr)，则对于任意的整数c，有acbc(modr)Xm(r)+1X(modr),27,4原根(primitiveroot),Euler定理表明,对两个互素的整数a,n,a(n)1modn定义：存在最小正整数m(n)(m|(n),使得am1modn，若对某个a,m=(n),则称a是n的一个原根对于素数p,若a是p的一个原根,则:a,a2,ap-1是(模p)各不相同的,从而构成了p的非0剩余类,即与1,2,(p-1)关于模p等价.,28,5离散对数,若a是素数p的一个原根,则对任意整数b,brmodp,其中0rp-1因此，对任意整数b和素数p，存在唯一的整数i,使得:baimodp1i(p-1)称指数i为以a为底模p的b的离散对数，记作inda,p(b).容易知道:inda,p(xy)=inda,p(x)+inda,p(y)mod(p)inda,p(xr)=ri