7保障與安全數(shù)論06

1,數(shù)論導(dǎo)引,1素數(shù)和數(shù)的互素除數(shù)(因子)的概念：設(shè)z為所有全體整數(shù)構(gòu)成的集合，若b0且使得a=mb,此時稱b整除a.記為ba,還稱b為a的除數(shù)(因子).注:若a=mb+r且01被稱為素數(shù)是指p的因子僅有1,-1,p,-p。定義：若axmodn=1，則稱a與x對于模n互為逆元。用Euclid算法求乘法逆元若a和n互素，則a在模n下有逆元。,2,算術(shù)基本定理：任何一個不等于0的正整數(shù)a都可以寫成唯一的表達式aP11P22Ptt，這里P1P2P3Pt是素數(shù)，其中i0最大公約數(shù)：若a,b,cz，如果ca，cb，稱c是a和b的公約數(shù)。正整數(shù)d稱為a和b的最大公約數(shù)，如果它滿足d是a和b的公約數(shù)。對a和b的任何一個公約數(shù)c有cd。注：1*.等價的定義形式是：gcd（a,b）maxkka，kb2*若gcd（a,b）=1，稱a與b是互素的。,3,模算術(shù)全體整數(shù)Z構(gòu)成的集合對整數(shù)的加法和乘法的兩種運算是封閉的且滿足算術(shù)運算的所有定律，此時我們稱整數(shù)集合z為整數(shù)環(huán)。整數(shù)環(huán)z對除法運算不封閉。帶余除法：az0，可找出兩個唯一確定的整數(shù)q和r,使a=qm+r,00，用輾轉(zhuǎn)相除法，先用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)等等，這樣一直進行下去，可得一系列關(guān)系式：rk-3=qk-1rk-2+rk-1,0=rk-1rk-2;(k-1)rk-2=qkrk-1+rk,0r3r4rk=0是嚴(yán)格遞降的一串非負(fù)整數(shù)，故最后總會出現(xiàn)余數(shù)為0的情形：rk-1=qk+1rk(k+1)所以，進行有限步必停止，此時d=rk=(a,b)定成立，這是因為1*.可見rk為a和b的公約數(shù)，只要按倒序分析自然有此結(jié)論。2*.a和b的任何一個公約數(shù)c都是rk的約數(shù)，只要按正序分析，自然可知。為證定理的后一部分，將式(1)做移項有r1=s1a+t1b（其中s1=1,t1=-q1）再將式(2)右端通過移項變?yōu)閞2=s2a+t2b這樣一直下去，最后得d=rk=s*a+t*b,s,tz,11,歐幾里得（Euclid）算法是數(shù)論中的一個基本技術(shù)，是求兩個正整數(shù)的最大公因子的簡化過程。而推廣的Euclid算法不僅可求兩個正整數(shù)的最大公因子，而且當(dāng)兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的乘法逆元。Euclid算法是基于下面一個基本結(jié)論：對任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a,b)=gcd(b,amodb)。即a，b的公因子集合與b，amodb的公因子集合相等，兩個集合的最大值也相等。例如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11。在求兩個數(shù)的最大公因子時，可重復(fù)使用以上結(jié)論。例如：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這兩個數(shù)的一個帶整系數(shù)的線性組合。解：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位范圍內(nèi)的數(shù)。,15,Euclid算法就是用這種方法，因gcd(a,b)=gcd(|a|,|b|)，因此可假定算法的輸入是兩個正整數(shù)，設(shè)為d，f，并設(shè)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下有乘法逆元（不妨設(shè)ba），即存在一x(x0，用輾轉(zhuǎn)相除法，先用b去除a，得r0=q1r1+r2,0r2r1r1=q2r2+r3,0r3r2;等等，這樣一直進行下去，可得一系列關(guān)系式：rm-2=qm-1rm-1+rm,01時，(n)等于比n小而與n互素的正整數(shù)的個數(shù)。例1(3)=(4)=(6)=2，(5)=4，(7)=6例2以n24為例，比24小而與24互素的正整數(shù)為：1，5，7，11，13，17，19，23因此，我們有(24)8。易見，若p為素數(shù)，則(p)p1。n12，(12)？,23,注：1*.若p，q都為素數(shù)且pq，此時有(pq)(p)(q)=（p1）（q1）證明（自學(xué)）：考慮zpq剩余類的集合是0，1，2，（pq-1）集合中與pq不互素的元素子集為p,2p,(q-1)p和子集q,2q,(p-1)q以及0，于是若設(shè)npq，有(n)=pq-(q-1)+(p-1)+1=(p-1)(q-1)=(p)(q)例：(21)=(3*7)=(3)(7)=2*6=12.,24,2*.設(shè)n=p1e1p2e2prer，其中p1,p2,pr為互異素數(shù)，則(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，有兩個素數(shù)3和7，這樣，(21)=21(1-1/3)(1-1/7)=12即21中有12個整數(shù)與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個整數(shù)與24是互素的：1，5，7，11，13，17，19，23,25,歐拉定理（Euler）：若整數(shù)a與整數(shù)n互素，則a(n)1(modn)推論：若a與n互素，則a與a(n)-1互為逆元。例4求5關(guān)于模7的乘法逆元。解由于7是素數(shù)，(7)=7-1=6，所以5關(guān)于模7的乘法逆元為56-1mod7=55mod7=3注：1*.np時，有ap-11(modp)為Format定理！2*.易見a(n)+1a(modn)3*.若n=pq，p與q為相異素數(shù)，取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)，則對于任意的整數(shù)c，有acbc(modr)Xm(r)+1X(modr),27,4原根(primitiveroot),Euler定理表明,對兩個互素的整數(shù)a,n,a(n)1modn定義：存在最小正整數(shù)m(n)(m|(n),使得am1modn，若對某個a,m=(n),則稱a是n的一個原根對于素數(shù)p,若a是p的一個原根,則:a,a2,ap-1是(模p)各不相同的,從而構(gòu)成了p的非0剩余類,即與1,2,(p-1)關(guān)于模p等價.,28,5離散對數(shù),若a是素數(shù)p的一個原根,則對任意整數(shù)b,brmodp,其中0rp-1因此，對任意整數(shù)b和素數(shù)p，存在唯一的整數(shù)i,使得:baimodp1i(p-1)稱指數(shù)i為以a為底模p的b的離散對數(shù)，記作inda,p(b).容易知道:inda,p(xy)=inda,p(x)+inda,p(y)mod(p)inda,p(xr)=ri