1、1l學習要點：了解數論、群論、有限域理論的基本概念了解模運算的基本方法了解歐幾里德算法、費馬定理、歐拉定理、中國剩余定理了解群的性質了解有限域中的計算方法21、除數(因子)的概念：設z為由全體整數而構成的集合，若 b0且 使得a=mb,此時稱b整除a.記為b a,還稱b為a的除數除數(因子因子).注注:若a=mb+r且0r1被稱為質數是指p的因子僅有1,-1,p,-p。Zmba,|ba3算術基本定理算術基本定理： 任何一個不等于任何一個不等于0的正整數的正整數a都可以寫成唯一的表達式都可以寫成唯一的表達式aP11P22Ptt，這里這里P1P2P3Pt是質數，其中是質數，其中i0最大公約數：最大

2、公約數： 若若a,b,cz，如果，如果c a，c b，稱，稱c是是a和和b的的公約數公約數。正。正整數整數d稱為稱為a和和b的的最大公約數最大公約數，如果它滿足，如果它滿足ld是是a和和b的公約數。的公約數。l對對a和和b的任何一個公約數的任何一個公約數c有有c d。注注：1*. 等價的定義形式是：等價的定義形式是： gcd（a,b）maxk k a且且k b 2*若若gcd（a,b）=1，稱，稱a與與b是是互素互素的的。4帶余除法帶余除法： az,0，可找出兩個唯一確定的整數，可找出兩個唯一確定的整數q和和r,使使a=qm+r, 0=r1）分成一些兩兩不交的等價類。63*. 對于某個固定模對

3、于某個固定模m的同余式可以象普通的等式那樣的同余式可以象普通的等式那樣相相加加、相減相減和和相乘，可結合相乘，可結合：(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)modm+(a*c)modm=a*(b+c)modm例子.通過同余式演算證明：（1）5601是56的倍數（2）2231是47的倍數。解： 注意53=12513(mod56) 于是有561691(mod56) 對同余式的兩邊同時升到10次冪， 即有56 560-1。7同理, 注意到26=6417(mod47),于是223=

4、(26)325=(26 26)26 25 289*(17)*(32) mod47 7*17*32 (mod47) 25*32(mod47) 1(mod47) 于是有 47 223-1定理定理：(消去律)對于abac（mod m）來說，若gcd(a,m)1則bc(mod m)89l例如1：附加條件不滿足的情況l63=182mod8l67=422mod8l但37mod8l例如2：附加條件滿足的情況53157mod8l511=557mod8l311mod810原因：模m的乘法運算返回的結果是0到m-1之間的數，如果乘數a和模數m有除1以外的共同因子時將不會產生完整的余數集合。Z801234567乘以

5、606121824303642模8后的 余數06420642Z801234567乘 以505101520253035模8后 的余數0527416311121314lExtended EUCLID(d,f)：l1）(X1,X2,X3) (1,0,f)；(Y1,Y2,Y3)(0,1,d)l2）如果Y3=0返回X3=gcd(d,f)；無逆元l3）如果Y3=1返回Y3=gcd(d,f)；Y2=d-1modfl4）Q=max_int(X3/Y3)l5）(T1,T2,T3) (X1-QY1,X2-QY2,X3-QY3)l6）(X1,X2,X3) (Y1,Y2,Y3)l7）(Y1,Y2,Y3) (T1,T2

6、,T3)l8）回到 2）15QX1X2X3Y1（T1）Y2（T2）Y3(T3)-101170120501201-51711-517-1635-1636-35216-352-7411=gcd16 Format定理定理：如果p是質數并且a是不能被p整除的正整數,那么，ap-11(mod p) Format定理的另一種形式：對gcd（a，p）1 有apa(modp)17a=7,p=19,求ap-1modp解：72=4911mod1974121mod197mod197849mod1911mod19716121mod197mod19ap-1=718=71672711mod191mod19181920l比

7、24小而與24 互素的正整數為：1、5、7、11、13、17、19、23。故 l這12個數是：1,2,4,5,8,10,11,13,16,17,19,208)24(12) 17)(13()7()3()21(2122歐拉定理（歐拉定理（Euler）（文字表述）：）（文字表述）：若整數若整數a與整數與整數n互素，則互素，則a (n)1(mod n)注：1*. np時，有ap-11(mod p)為Format定理！2*.易見a (n)+1a(mod n)23lam=1modn，如果，如果a與與n互素，則至少有一互素，則至少有一個整數個整數m（如（如m=phi(n)）滿足這一方程，）滿足這一方程，稱滿

8、足方程的最小正整數稱滿足方程的最小正整數m為模為模n下下a的的階階。l如果如果a的階的階m=phi（n ），則稱），則稱a為為n的的本本原元原元。 本原元并不一定唯一本原元并不一定唯一并非所有的整數都有本原元，只有以下形式并非所有的整數都有本原元，只有以下形式的整數才有本原元：的整數才有本原元：2,4,pa,2pa（a為整數，為整數，p為奇質數）為奇質數） 24ln19，a3，在mod19下的冪分別為3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。即3的階為18phi(19)，所以3為19的本原元。 25例子：（孫子算經）今有物不知其數。三三數之余二；

9、五五數之余三；七七數之余二。問物幾何？2(mod 3)3(mod 5)2(mod 7)xxx答曰：二十三。232*70+3*21+2*15(mod 105)（ 口 訣 ： 三 人 同 行 七 十 稀 ， 五 樹 梅 花 廿 一 枝 ， 七子團圓月正半，除百零五便得知。）問，70，21，15如何得到的？原問題為：求解同余方程組26注意注意：若x0為上述同余方程組的解，則x0=x0+105*k(kz) 也為上述同余方程組的解。有意義的是，解題口訣提示我們先解下面三個特殊的同余方程組(1) (2) (3)的特殊解=?=?=?以方程（1）為對象，相當于解一個這樣的同余方程 35y1(mod 3)，為什

10、么呢？原因是，從（1）的模數及條件知，x應同時是5和7的倍數，即應是35的倍數，于是可以假設x35y有：1(mod3)0(mod5)0(mod7)xxx0(mod3)1(mod5)0(mod7)xxx0(mod3)0(mod5)1(mod7)xxx1000100012735y1(mod 3)相當于2y1(mod)3解出y=2（mod3）于是x35*2 70(mod105)類似地得到（2）、（3）方程的模105的解21、15。于是有：得700012101015100)105(mod2315*221*370*210020103001223228中國剩余定理中國剩余定理：設自然數m1,m2,mr兩兩

11、互素，并記M=m1m2mr，b1.br表示r個整數，則同余方程組（A）在模M同余的意義下有唯一解。1122(mod)(mod).(mod)rrxbmxbmxbm29證明： M=m1m2mr，令Mj=M/mj=m1m2mj-1mj+1mr求yj使：Mjyj 1 mod mj j=1,2,.r由于（Mj,mj)=1，所以yj是存在的。令：x0 b1M1y1+b2M2y2+brMryr mod M (B) 可證明x0便是（A）式的解。為證明這一點，注意j =h時mh|Mj。故Mj 0 mod mh,即x0中各項除第h項外，其余都模mh同余0。又Mhyh 1 mod mh,所以： X0 bhMhyh

12、mod mh bh mod mh。即滿足(A)式，x0是其解。 下面證明x0是模M的唯一解。如若不然，設x1和x2是（A）式模M的兩個解，則有：x1 x2 bj mod mj (j=1r)那么，x1-x2 0 mod mj ,即mj |(x1-x2) （j=1r)因此，M（x1-x2),即x1-x2 0 mod M所以x1，x2是模M的相同解，從而證明了對于模M式（A）的解是唯一的。30 例如：x1 mod 2x2 mod 3x3 mod 5解：M=235=30M1=15, M2=10, M3=615y11mod2, y1=110y21mod3, y2=16y31mod5, y3=1所以,x=

13、1151+2101+361=5323 mod 3031l群的概念是由一個非空集合G組成，在集合G中定義了一個二元運算符“ ”，并滿足以下性質的代數系統，記為G, 32交換群：有限群無限群有限群的階循環群循環群的生成元33l群中的單位元是唯一的l群中每一個元素的逆元是唯一的 l(消去律) 對任意的，如果 ，或，則 Gcba,cabacb acab34l域的概念域是由一個非空集合F組成，在集合F中定義了兩個二元運算符：“+”和“ ”，并滿足：l域記為F,+, 35兩個定義：兩個定義：有限域有限域的階域的實質：域是一個可以在其上進行加法、減法、乘法和除法運算而結果不會超出域的集合。如有理數集合、實數集合、復數集合都是域，但整數集合不是 減法：a-b=a+(-b)除法：a/b=a(b-1)36密碼學常用素域GF(p)或階為2m的域GF(2m) 3738l生成元可證明：在GF(p)中至少存在一個元素g，使得