Lecture04-密碼學的數(shù)學引論1

第四章密碼學的數(shù)學引論學習要點：了解數(shù)論、群論、有限域理論的基本概念掌握模運算的基本方法掌握歐幾里德算法、費馬定理、歐拉定理、中國剩余定理了解群的性質(zhì)掌握有限域中的計算方法1、除數(shù)(因子)的概念：

設z為由全體整數(shù)而構(gòu)成的集合，若b≠0且

使得a=mb,此時稱b整除a.記為b∣a,還稱b為a的除數(shù)(因子).注:若a=mb+r且0<r<b,此時b不整除a,記為

2、素數(shù)(質(zhì)數(shù))的概念:

整數(shù)p>1被稱為素數(shù)是指p的因子僅有1,-1,p,-p?！?－1數(shù)論—素數(shù)§算術(shù)基本定理：

任何一個不等于0的正整數(shù)a都可以寫成唯一的表達式a＝P1α1P2α2…Ptαt，這里P1＜P2＜P3…＜Pt是素數(shù)，其中αi>0§最大公約數(shù)：若a,b,c∈z，如果c∣a，c∣b，稱c是a和b的公約數(shù)。正整數(shù)d稱為a和b的最大公約數(shù)，如果它滿足d是a和b的公約數(shù)。對a和b的任何一個公約數(shù)c有c∣d。注：1*.等價的定義形式是：

gcd（a,b）＝max{k∣k∣a且k∣b}2*．若gcd（a,b）=1，稱a與b是互素的。帶余除法：

a∈z,>0，可找出兩個唯一確定的整數(shù)q和r,

使a=qm+r,0<=r<m,q和r這兩個數(shù)分別稱為以m去除a所得到的商數(shù)和余數(shù)。(若r=0則m∣a）整數(shù)同余：定義：如果amodm=bmodm，則稱整數(shù)a模正整數(shù)m同余于整數(shù)b，并寫a≡b（modm）是指m∣（a－b）,m稱為模數(shù)。

注：1*.m∣a-ba=q1m+r,b=q2m+r即a和b分別除以m有相同的余數(shù)?！巴唷倍值膩碓淳驮谟诖??！?－1數(shù)論—模算術(shù)2*.相對于某個固定模數(shù)m的同余關(guān)系，是整數(shù)間的一種等價關(guān)系。具有等價關(guān)系的三點基本性質(zhì)：

自反性：對任意整數(shù)a有：a≡a（modm）

對稱性：如果a≡b(modm)，則b≡a（modm）

傳遞性：如果a≡b(modm）b≡c（modm），則a≡c(modm)

于是，全體整數(shù)集合z可按模m（m>1）分成一些兩兩不交的等價類。3*.對于某個固定模m的同余式可以象普通的等式那樣相加、相減和相乘，可結(jié)合：(1)[a(modm)±b(modm)]modm=(a±b)(modm)(2)[a(modm)*b(modm)]modm=a*b(modm)(3)[(a*b)mod

m+(a*c)modm]modm=[a*(b+c)]modm

例子.通過同余式演算證明：（1）560－1是56的倍數(shù)（2）223－1是47的倍數(shù)。解： 注意53=125≡13(mod56)

于是有56≡169≡1(mod56)

對同余式的兩邊同時升到10次冪， 即有56∣560-1。同理,注意到26=64≡17(mod47), 于是223=(26)3·25=(26·26)26·25

≡289*(17)*(32)mod47≡7*17*32(mod47)≡25*32(mod47)≡1(mod47)

于是有47∣223-1定理：(消去律)對于ab≡ac（modm）來說，若gcd(a,m)＝1則b≡c(modm)例如1：附加條件不滿足的情況6×3=18≡2mod86×7=42≡2mod8但3≡7mod8例如2：附加條件滿足的情況

5×3＝15≡7mod85×11=55≡7mod83≡11mod8原因：模m的乘法運算返回的結(jié)果是0到m-1之間的數(shù)，如果乘數(shù)a和模數(shù)m有除1以外的共同因子時將不會產(chǎn)生完整的余數(shù)集合。Z801234567乘以606121824303642模8后余數(shù)06420642Z801234567乘以505101520253035模8后的余數(shù)05274163§4－1數(shù)論—歐幾里德算法歐幾里德算法用于確定兩個正整數(shù)a,b(a>b)的最大公約數(shù)原理：gcd(a,b)=gcd(b,r=amodb)求最大公因數(shù)的Euclid算法p57ab153636151566330最大公因數(shù)的求法：輾轉(zhuǎn)相除法例如：求gcd(15,36)gcd(54,30)36=152+654=30+2415=62+330=24+66=32+024=46+0因此，gcd(15,36)=3gcd(54,30)=6這里，gcd(36,15)=gcd(6,15)=gcd(6,3)=3求x，滿足(a·x)modn=1,即xa-1(modn)當a與n互素時,方程xa-1(modn)有唯一解；即：ax-kn=1當a與n不互素時,此方程無解。一個數(shù)關(guān)于某一個模的乘法逆元不一定存在。2關(guān)于模14的乘法逆元不存在，因為2與14不互素a與n互素，a關(guān)于模n的乘法逆元才存在求乘法逆元：擴展的Euclid算法例：求5關(guān)于模14的乘法逆元輾轉(zhuǎn)相除：14=52+45=4+1逆推：1=5-4=5-（14-52）=53-14因此，5關(guān)于模14的乘法逆元為3。§4－1數(shù)論—乘法逆元素例：求4關(guān)于模7的乘法逆元

7=41+34=3+11=4-3=4-(7-4)=42-7

所以4關(guān)于模7的乘法逆元為2練習練習：求17關(guān)于模26的乘法逆元。答案求17關(guān)于模26的乘法逆元。答案：2326=17+91=9-817=9+8=9-(17-9)9=8+1=92-17=(26-17)2-17=262-173=17(-3)+262+1726-1726=1723-2615§4－1數(shù)論—費馬Fermat定理§

Fermat定理：如果p是素數(shù)并且a是不能被p整除的正整數(shù),那么，ap-1≡1(modp)

Fermat定理的另一種形式：對gcd（a，p）＝1有ap≡a(modp)例子：a=7,p=19,求ap-1modp解：72=49≡11mod1974≡121mod19≡7mod1978≡49mod19≡11mod19716≡121mod19≡7mod19ap-1=718=716×72≡7×11mod19≡1mod19§4－1數(shù)論—歐拉(Euler)定理例子：比24小而與24互素的正整數(shù)為：1、5、7、11、13、17、19、23。故

這12個數(shù)是：｛1,2,4,5,8,10,11,13,16,17,19,20｝歐拉定理（Euler）（文字表述）：若整數(shù)a與整數(shù)n互素，則aφ(n)≡1(modn)注：1*.n＝p時，有ap-1≡1(modp)為Fermat定理！2*.易見aφ(n)+1≡a(modn)階與本原元am≡1modn，如果a與n互素，則至少有一個整數(shù)m（如m=phi(n)）滿足這一方程，稱滿足方程的最小正整數(shù)m為模n下a的階。a=7,n=19,則71=7mod19;72=14mod19;73=1mod19;即7在模19下的階為3。循環(huán)周期階與本原元如果a的階m=phi（n），則稱a為n的本原元。n＝19，a＝3，在mod19下的冪分別為3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。即3的階為18＝phi(19)，所以3為19的本原元。本原元并不一定唯一(可驗證19的本原元有2，3，10，13，14，15)并非所有的整數(shù)都有本原元，只有以下形式的整數(shù)才有本原元：2,4,pa,2pa（a為整數(shù)，p為奇素數(shù)）§4－1數(shù)論—中國剩余定理定理：如果n的素數(shù)因子分解式為p1p2

…pt，則一組方程(xmodpi）=

ai，其中i=1,2,…,t，有唯一解x，其中x小于n（其中某些pi可能相等）。例：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？xmod3=2xmod5=3xmod7=2解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1

p2

p3=357=105，M1=n/p1=35,M2=n/p2=21,M3=n/p3=15求解35·

x1

mod3=1,得x1=2求解21·

x2

mod5=1,得x2=1求解15·

x3

mod7=1,得x3=1則x=(M1

·x1

·a1+M2

·x2

·a2+M3

·x3

·a3)modn=(3522+2113+1512)mod105=233mod

105=23§4－2群論群的概念是由一個非空集合G組成，在集合G中定義了一個二元運算符“·”，并滿足以下性質(zhì)的代數(shù)系統(tǒng)，記為｛G,·｝

交換群：有限群:群的元素個數(shù)有限無限群：群的元素個數(shù)無限有限群的階：有限群中元素的個數(shù)循環(huán)群：群中的每一個元素都是其中某一個元素g的某次冪循環(huán)群的生成元：如果元素g可以通過冪運算生成群中的其它所有元素，則稱g為群的生成元群的性質(zhì)群中的單位元是唯一的群中每一個元素的逆元是唯一的(消去律)對任意的，如果，或，則§4－3有限域理論

域的概念域是由一個非空集合F組成，在集合F中定義了兩個二元運算符：“+”和“·”，并滿足：域記為｛F,+,·}

兩個定義：有限域：包含有限個元素有限域的階：有限域中元素的個數(shù)稱為有限域的階域的實質(zhì)：域是一個可以在其上進行加法、減法、乘法和除法運算而結(jié)果不會超出域的集合。如有理數(shù)集合、實數(shù)集合、復數(shù)集合都是域，但整數(shù)集合不是(使用除法