信息安全導(dǎo)論-5密碼學(xué)數(shù)學(xué)基礎(chǔ)省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

信息安全導(dǎo)論第五講密碼學(xué)技術(shù)中數(shù)學(xué)基礎(chǔ)華中科技大學(xué)圖象所信息安全研究室Dr.ZuxiWang2025/2/211第1頁(yè)密碼學(xué)是研究密碼系統(tǒng)或通信安全一門(mén)學(xué)科，分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是使得消息保密學(xué)科，從事此行稱(chēng)為密碼編碼者。密碼分析學(xué)（密碼破譯學(xué)）是研究加密消息破譯學(xué)科，從事此行稱(chēng)為密碼分析者。精于此道人被稱(chēng)為密碼學(xué)家，當(dāng)代密碼學(xué)家通常是理論數(shù)學(xué)家。2025/2/212第2頁(yè)密碼學(xué)是一門(mén)交叉學(xué)科，它很大程度上是應(yīng)用數(shù)學(xué)學(xué)科。密碼學(xué)中包括數(shù)論、代數(shù)、概率論、組合數(shù)學(xué)、計(jì)算復(fù)雜理論等各種數(shù)學(xué)知識(shí)。還包括信息論學(xué)科知識(shí)。密碼學(xué)所包括知識(shí)十分遼闊，這里僅介紹部分?jǐn)?shù)學(xué)基本知識(shí)。2025/2/213第3頁(yè)數(shù)論基礎(chǔ)素?cái)?shù)同余、模運(yùn)算中國(guó)剩下定理Euclean算法Fermat定理、Euler定理素性檢驗(yàn)因子分解離散對(duì)數(shù)2025/2/214第4頁(yè)整除、素?cái)?shù)記整數(shù)集合Z={…,-3,-2,-1,0,1,2,3,…}整除設(shè)a,b∈Z，a≠0，假如存在m∈Z，使得b=ma，則稱(chēng)a整除b，以a|b表示，a是b一個(gè)因子或約數(shù)。假如沒(méi)有任何m，使得b=ma，則稱(chēng)a不能整除b,記a?b，此時(shí)有a=mb+r且0<r<b。素?cái)?shù)(質(zhì)數(shù))

整數(shù)p>1被稱(chēng)為素?cái)?shù)是指p因子僅有1，-1，p，-p。不然，稱(chēng)為合數(shù)。2025/2/215第5頁(yè)整除基本性質(zhì)a|a;b≠0，b|0;Ifa|b,b|c,thena|c;ifa|1,thena=±1;ifa|b,andb|a,thena=±b;ifb|gandb|h,thenb|(mg+nh),foranyintegersmandn注意:ifa=0modn,thenn|a2025/2/216第6頁(yè)互素與最大條約數(shù)最大條約數(shù)（最大公因子）：若a,b,c∈Z，假如c∣a，c∣b，稱(chēng)c是a和b條約數(shù)。正整數(shù)d稱(chēng)為a和b最大條約數(shù)(記d=gcd(a,b)或(a,b))

，假如它滿足:d是a和b條約數(shù)。對(duì)a和b任何一個(gè)條約數(shù)c有c∣d。等價(jià)定義形式是：

gcd(a,b)=max{k:k∣a，k∣b}若gcd(a,b)=1，稱(chēng)a與b是互素。2025/2/217第7頁(yè)最小公倍數(shù)最小公倍數(shù)a,b倍數(shù)中最小者稱(chēng)為a,b最小公倍數(shù)，記為：lcm(a,b)a,b不全為0，有ab=gcd(a,b)·lcm(a,b).注意：對(duì)有限個(gè)整數(shù)a1,a2,…,an,也可定義最大條約數(shù)gcd(a1,a2,…,an)和最小公倍數(shù)lcm(a1,a2,…,an).2025/2/218第8頁(yè)帶余除法帶余除法：

a∈Z,m>0，可找出兩個(gè)唯一確定整數(shù)q和r使a=qm+r,0≤r<m。(若r=0則m∣a）

q和r這兩個(gè)數(shù)分別稱(chēng)為以m去除a所得到商數(shù)和余數(shù).記：q=adivm或[a/m],r=amodm。存在x,y，gcd(a,b)＝ax+by假如a=qb+r,則gcd(a,b)=gcd(b,r).gcd(a/gcd(a,b),b/gcd(a,b))=12025/2/219第9頁(yè)算術(shù)基本定理下面關(guān)于素?cái)?shù)事實(shí)均成立假如p是一個(gè)素?cái)?shù)，而且p|ab，則有p|a或p|b；素?cái)?shù)有沒(méi)有窮多個(gè)；素?cái)?shù)定理:記π(x)為小于x素?cái)?shù)個(gè)數(shù)，則有它表明，對(duì)于充分大x，能夠用xlnx近似地表示π(x)。算術(shù)基本定理：任何一個(gè)不等于0正整數(shù)a都能夠?qū)懗晌ㄒ槐硎臼?，這里P1>P2>P3…>Pt是素?cái)?shù)，其中αi>0整數(shù)。2025/2/2110第10頁(yè)當(dāng)前沒(méi)有可用于整數(shù)分解有效算法。對(duì)于整數(shù)a,b(a,b≥2)，a,b素?cái)?shù)分解式分別為：

，，其中ei，fi≥0,t≥i≥1，則有：2025/2/2111第11頁(yè)帶余除法中，a∈Z，m>0，a=qm+r，0≤r<m，r為a除以m余數(shù)或剩下(Residue)，m稱(chēng)為模數(shù)，所以稱(chēng)r為a模正整數(shù)m剩下，記r≡amodmm∣(a-b)

a=q1m+r,b=q2m+r。即a和b分別除以m有相同余數(shù)同余稱(chēng)整數(shù)a模正整數(shù)m同余(數(shù))于整數(shù)b，并寫(xiě)a≡b（modm）是指m∣(a－b),m稱(chēng)為模數(shù)。note:ifa=0modm,thenm|a整數(shù)同余式和同余方程2025/2/2112第12頁(yè)1、模關(guān)系：相對(duì)于某個(gè)固定模數(shù)m同余關(guān)系，是指整數(shù)間一個(gè)等價(jià)關(guān)系。含有等價(jià)關(guān)系三點(diǎn)基本性質(zhì)：

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

對(duì)稱(chēng)性：若a≡b(modm)，則b≡a（modm）

傳遞性：若a≡b(modm),b≡c(modm),則a≡c(modm)全體整數(shù)集合Z可按模m（m>1）分成一些兩兩不交等價(jià)類(lèi)（剩下類(lèi)）。2、整數(shù)模m同余類(lèi)共有m個(gè)，他們分別為mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一個(gè)算一類(lèi)，每一類(lèi)都能夠選一個(gè)代表元，普通選這一類(lèi)中最小非負(fù)整數(shù)。于是稱(chēng)[0],[1],[2],…[m-1]為標(biāo)準(zhǔn)完全剩下系。其中與m互素剩下類(lèi)組成模m簡(jiǎn)約剩下系。Z模12標(biāo)準(zhǔn)完全剩下系為：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]2025/2/2113第13頁(yè)Modulo7Example...-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456

78910111213141516171819202122232425262728293031323334...2025/2/2114第14頁(yè)3、模運(yùn)算：對(duì)于某個(gè)固定模m同余式能夠象普通等式那樣相加相減和相乘：a(modm)±b(modm)=(a±b)(modm)a(modm)*b(modm)=a*b(modm)例：由同余式演算證實(shí)560－1是56倍數(shù)，223－1是47倍數(shù)。解： 注意53=125≡13(mod56)

于是有56≡169≡1(mod56)

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

≡900*(-30)*(32)mod(47)≡(7)*(-30)*(32)(mod47)≡1(mod47)

于是有47∣(223-1)2025/2/2115第15頁(yè)Modulo8Example2025/2/2116第16頁(yè)4、定理：(消去律)對(duì)于ab≡ac(modm)來(lái)說(shuō)，若最大公因子gcd(a,m)＝1（即a與m是互素），則b≡c(modm)加法消去律：

a+b≡a+c(modm)，有b≡c(modm).5、一次同余方程ax≡b(modm)，這個(gè)方程有沒(méi)有解，相當(dāng)于問(wèn)有沒(méi)有那樣一個(gè)整數(shù)x，使得對(duì)于某個(gè)整數(shù)y來(lái)說(shuō)，有ax+my=b

定理：記最大公因子(a,m)=d，則同余方程ax≡b(modm)有解充分必要條件是d∣b。當(dāng)這個(gè)條件滿足時(shí)，恰有d個(gè)模m同余類(lèi)中整數(shù)是上述方程解。證實(shí)：略。（從ax+my=b入手）2025/2/2117第17頁(yè)6、整數(shù)環(huán)z模正整數(shù)m得到剩下類(lèi)集合能夠記為zm(或z/(m)),zm={[0],[1],…,[m-1]}

在3、中已說(shuō)明zm對(duì)剩下類(lèi)加法，乘法是封閉，可列出它們加乘表。我們稱(chēng)zm為剩下類(lèi)環(huán)（或同余類(lèi)環(huán)）7、在整數(shù)環(huán)z中是沒(méi)有零因子，即兩個(gè)非零整數(shù)乘積一定不等于0，不過(guò)剩下環(huán)則不然。例z12中：[3]*[4]=[12]=[0]說(shuō)明，zm中元素可分為兩類(lèi)，一類(lèi)是零因子，即若α∈zm,α≠[0]，存在β∈zm且β≠[0]，有α*β=[0]，則稱(chēng)α，β都為zm中零因子。另一類(lèi)是可逆元，即若α∈zm，存在β∈zm，使α*β=[1]，此時(shí)α,β互為各自逆元，記α-1=β；β-1=α2025/2/2118第18頁(yè)定理：剩下類(lèi)環(huán)zm中元素α=[a]為zm可逆元

最大條約數(shù)(a,m)=1要證實(shí)這個(gè)定理，只需證實(shí)以下引理：引理：任意兩個(gè)整數(shù)a和b都有一個(gè)最大條約數(shù)，這么一個(gè)最大條約數(shù)d能夠表示成a,b二數(shù)關(guān)于整系數(shù)線性組合，即有s,t∈z，使d＝sa＋tb。證實(shí)：不妨設(shè)b>0，用輾轉(zhuǎn)相除法，先用b去除a，得

a=q1b+r1,0≤r1<b; (1)假如r1=0，停頓，不然再用r1去除b，得

b=q2r1+r2,0≤r2<r1; (2)假如r2=0，停頓，不然再用r2去除r1，得

r1=q3r2+r3;0≤r3<r2; (3)等等，這么一直進(jìn)行下去，可得一系列關(guān)系式：

rk-3=qk-1rk-2+rk-1,0≤rk-1<rk-2; (k-1) rk-2=qkrk-1+rk,0≤rk<rk-1; (k)2025/2/2119第19頁(yè)因?yàn)闅v次所得余數(shù)

r1>r2>r3>r4>…rk>…≥0是嚴(yán)格遞降一串非負(fù)整數(shù)，故最終總會(huì)出現(xiàn)余數(shù)為0情形：

rk-1=qk+1rk (k+1)所以，進(jìn)行有限步必停頓，此時(shí)d=rk=(a,b)成立，這是因?yàn)?).可知rk為a和b條約數(shù)，只要按倒序分析自然有此結(jié)論。2).a和b任何一個(gè)條約數(shù)c都是rk約數(shù)，只要按正序分析，自然可知。為證定理后一部分，將式(1)做移項(xiàng)有

r1=s1a+t1b（其中s1=1,t1=-q1）

再將式(2)右端經(jīng)過(guò)移項(xiàng)變?yōu)閞2=s2a+t2b這么一直下去，最終得d=rk=s*a+t*b, s,t∈z.2025/2/2120第20頁(yè)例子：求(180，252)，并將他表示為180和252這兩個(gè)數(shù)一個(gè)帶整系數(shù)線性組合。解： 252=1*180+72 (1) 180=2*72+36 (2) 72=2*36 (3)得(180,252)=36，同時(shí)有 72=252-1*180 (1

)由(2)得 36=180-2*72 (2

)

將(1

)代入(2

)，即得

36=180-2*(250-180)

=3*180-2*2522025/2/2121第21頁(yè)中國(guó)剩下定理例子：（孫子算經(jīng)）今有物不知其數(shù)：三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問(wèn)物幾何？答曰：二十三。23≡2*70+3*21+2*15(mod105)（口訣：三人同行七十稀，五樹(shù)梅花廿一枝，

七子團(tuán)圓月正半，除百零五便得知。）問(wèn)，70，21，15怎樣得到？原問(wèn)題為：求解同余方程組2025/2/2122第22頁(yè)注意：若x0為上述同余方程組解，則x0

=x0+105*k(k∈z)也為上述同余方程組解。有意義是，解題口訣提醒我們先解下面三個(gè)特殊同余方程組(1) (2) (3) 特殊解 =? =? =?以方程（1）為對(duì)象，相當(dāng)于解一個(gè)這么同余方程35y≡1(mod3)，為何呢？原因是，從（1）模數(shù)及條件知，x應(yīng)是35倍數(shù)，于是能夠假設(shè)x＝35y，有2025/2/2123第23頁(yè)35y≡1(mod3)相當(dāng)于2y≡1(mod3)

解出y=2（mod3）

于是x35*2(mod(3*35))70(mod105)類(lèi)似地得到（2）、（3）方程模105解21、15。

于是有

得

2025/2/2124第24頁(yè)中國(guó)剩下定理：設(shè)自然數(shù)m1,m2,…mr兩兩互素，并記M=m1m2…mr，則同余方程組在模M同余意義下有唯一解。2025/2/2125第25頁(yè)證實(shí)：考慮方程組，

(1<=i<=r)

因?yàn)橹Tmi(1<=i<=r)兩兩互素，這個(gè)方程組作變量替換，令x=(M/mi)*y，方程組等價(jià)于解同余方程： (M/mi)y≡1(modmi)2025/2/2126第26頁(yè)若得到特解yi,只要令

xi=(M/mi)yi則方程組解為

x0=b1x1+b2x2+…+brxr(modM)模N意義下唯一。中國(guó)剩下定理用途之一是，它給出了一個(gè)方法，使非常大數(shù)對(duì)M模運(yùn)算轉(zhuǎn)化到更小數(shù)上來(lái)進(jìn)行運(yùn)算，當(dāng)M為150位或150位以上時(shí)，這種方法非常有效。2025/2/2127第27頁(yè)Euclidean算法依據(jù)(a,b)=(b,amodb)輾轉(zhuǎn)除法是求解兩個(gè)整數(shù)最大公因子傳統(tǒng)方法，由此而得歐幾里得算法是一個(gè)用于計(jì)算兩個(gè)整數(shù)最大公因子有效算法。Euclidean算法：輸入a和b，wherea,b∈z,a,b≥0,a≥b.假如b≠0，則依次完成:r←amodb,a←b,b←r,不然返回a.輸出gcd(a,b)=r.2025/2/2128第28頁(yè)ExampleGCD(1970,1066)1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)2025/2/2129第29頁(yè)擴(kuò)展Euclidean算法經(jīng)擴(kuò)張Euclidean算法不但能夠被用于計(jì)算d=gcd(a,b)，而且能夠找到滿足等式ax+by=d整數(shù)x和y。擴(kuò)展Euclidean算法：輸入a和b，wherea,b∈z,a,b≥0,a≥b.假如b=0，則:d←a,x←1,y←0,返回(d,x,y).x2←1,x1←0,y2←0,y1←1假如b≠0，則依次完成:q←[a/b],r←a-qb,x←x2-qx1,y←y2-qy1;a←b,b←r,x2←x1,y2←y1,x1←x,y1←yd←a,x←x2,y←y2，返回(d,x,y).Euclidean算法和擴(kuò)展Euclidean算法時(shí)間復(fù)雜度為O((lgn)2).2025/2/2130第30頁(yè)Fermat定理和Euler定理Fermat定理：假如p是素?cái)?shù)而且a是正整數(shù),(p,a)=1那么，ap-1≡1(modp)

證實(shí)：設(shè)z*p≡{α∈zp∣(α,p)=1}

易見(jiàn)，z*p={1,2,3,…,(p-1)}且因?yàn)椋╝,p）＝1知

az*p={[a],[2a],[3a],…,[(p-1)a]}=z*p，原因是az*p內(nèi)元素兩兩不一樣。他們剛好為1,2,3…,(p－1)一個(gè)排列。所以

[a]*[2a]*[3a]*…[(p-1)a]≡1*2*3*…(p-1)(modp)

由（(p－1)！，p）＝1，

所以ap-1≡1(modp)推論：對(duì)素?cái)?shù)p，任意正整數(shù)a，有ap≡a(modp).usefulinpublickeyandprimalitytesting2025/2/2131第31頁(yè)Euler函數(shù)φEuler函數(shù)φ(n)是這么來(lái)定義：

當(dāng)n＝1時(shí),φ(1)＝1；當(dāng)n>1時(shí)，它值φ(n)等于比n小而與n互素正整數(shù)個(gè)數(shù)。以n＝24為例，比24小而與24互素正整數(shù)為：1,5,7,11,13,17,19,23。所以，我們有φ(24)＝8。若p為素?cái)?shù)，則φ(p)＝p-1。若p，q都為素?cái)?shù)且p≠q，此時(shí)有

φ(pq)＝φ(p)φ(q)=(p-1)·(q-1)證實(shí)：考慮zpq剩下類(lèi)集合是{0，1，2，…，（pq-1）},集合中與pq不互素元素子集為{p,2p,…,(p-1)q}和子集{q,2q,…(p-1)q}以及0，于是若設(shè)n＝pq，有φ(n)=pq-[(q-1)+(p-1)+1]=(p-1)(q-1)=φ(p)φ(q).例：φ(21)=φ(3*7)=φ(3)φ(7)=2*6=12.2025/2/2132第32頁(yè)若m1,m2互素，則φ(m1m2)＝φ(m1)φ(m2).設(shè)n=p1e1p2e2…prer，其中p1,p2,…,pr為互異素?cái)?shù)，則φ(n)=p1e1-1p2e2-1…prer-1(p1-1)(p2-1)…(pr-1)

=n(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pr)Euler公式

證實(shí)：考慮1/n,2/n,…n/n，然后化簡(jiǎn)成既約分?jǐn)?shù)，分母為d一類(lèi)分?jǐn)?shù)有φ(d)個(gè)，于是

歐拉定理（Euler）：若整數(shù)a與整數(shù)n互素，則aφ(n)≡1(modn)。證實(shí)：設(shè)小于n而和n互素φ(n)個(gè)正整數(shù)為

r1,r2,r3…,rφ(n) (1)2025/2/2133第33頁(yè)他們是模n兩兩互不一樣余。對(duì)每一個(gè)定數(shù)i來(lái)說(shuō)，因?yàn)閍和ri都與n互素，所以(ari,n)=1，所以ari同余于（1）中某個(gè)ri’即

ari≡ri’(modn)，1≤i≤φ(n)而且當(dāng)i≠j時(shí)有ari

/≡arj(modn).于是,為

置換.所以有由(ri,n)=1,所以

Remarks：1*.n＝p時(shí)，(a,p)=1,有ap-1≡1(modp)為Fermat定理！而對(duì)任意a，有ap≡a(modp)（Fermat）2*.易見(jiàn)aφ(n)+1≡a(modn)3*.若n=pq，p與q為相異素?cái)?shù)，取0<m<n，若(m,n)=1，有mφ(n)+1≡m(modn)，也即m(p-1)(q-1)+1≡m(modn).2025/2/2134第34頁(yè)4*.對(duì)于3中，若(m,n)＝p或q，也一樣有mφ(n)+1≡m(modn)5*.由(mφ(n))k≡1k(modn)知

mkφ(n)≡1(modn)，深入

mkφ(n)+1≡m(modn) mk(p-1)(q-1)+1≡m(modn)2025/2/2135第35頁(yè)素性檢驗(yàn)、因子分解在許多加密算法中，需要隨機(jī)選擇一個(gè)或多個(gè)非常大素?cái)?shù)，所以必須確定一個(gè)給定大數(shù)是否是素?cái)?shù)。－－素性檢驗(yàn)(測(cè)試)當(dāng)前還沒(méi)有簡(jiǎn)單有效方法處理該問(wèn)題。Miller和Rabin提出一個(gè)算法，其利用了Fermat定理。該算法產(chǎn)生數(shù)不一定數(shù)素?cái)?shù)，但令人詫異是，其產(chǎn)生數(shù)幾乎能夠必定是素?cái)?shù)。2025/2/2136第36頁(yè)素性檢驗(yàn)、因子分解RSA算法安全性以對(duì)大整數(shù)進(jìn)行素?cái)?shù)分解困難性為基礎(chǔ)，即無(wú)法在多項(xiàng)式時(shí)間內(nèi)對(duì)于一個(gè)足夠大整數(shù)進(jìn)行分解。一旦這個(gè)難題被破解，則RSA算法安全性便不復(fù)存在。一些具代表性因子分解算法包含：二次篩法p-1因子分解方法是更為有效橢圓曲線方法基礎(chǔ)數(shù)域篩法等2025/2/2137第37頁(yè)強(qiáng)素?cái)?shù)許多密碼算法關(guān)心強(qiáng)素?cái)?shù)。設(shè)n∈Z，p和q是素?cái)?shù)，而且n=pq。當(dāng)p，q滿足以下特征時(shí)，稱(chēng)之為強(qiáng)素?cái)?shù)。①Gcd(p-1,q-1)比較??；②p-1和q-1都有大素因子（分別記為p*和q*）；③p*-1和q*-1都有大素因子；④p+1和q+1都有大素因子；⑤(p-1)/2和(q-1)/2都是素?cái)?shù)。假如素?cái)?shù)p含有特征⑤,則它們一定含有特征③和④.此時(shí)，即使采取一些特殊因子分解方法，對(duì)整數(shù)n進(jìn)行因子分解也非常困難。2025/2/2138第38頁(yè)為了增加密碼算法安全性，提議使用長(zhǎng)度大而且含有隨機(jī)性結(jié)構(gòu)強(qiáng)素?cái)?shù)，其中，素?cái)?shù)長(zhǎng)度比其結(jié)構(gòu)特點(diǎn)更為主要。不過(guò)，從因子算法對(duì)整數(shù)進(jìn)行分解概率角度考慮，強(qiáng)素?cái)?shù)與其它素?cái)?shù)相比并沒(méi)有明確優(yōu)勢(shì)。2025/2/2139第39頁(yè)代數(shù)基礎(chǔ)－－群、環(huán)、域、布爾代數(shù)概述群、環(huán)、域基本概念有限域

GF(pn)多項(xiàng)式算術(shù)布爾代數(shù)與布爾函數(shù)2025/2/2140第40頁(yè)概述有限群、有限域、布爾函數(shù)等在密碼技術(shù)和應(yīng)用中越來(lái)越主要。cryptographyAES,EllipticCurve,IDEA,PublicKey將從抽象代數(shù)群、環(huán)、域基本概念開(kāi)始介紹。2025/2/2141第41頁(yè)群（Group）代數(shù)系統(tǒng)：一個(gè)集合以及定義在其上一組運(yùn)算一起組成一個(gè)代數(shù)系統(tǒng)。群（group）是一個(gè)代數(shù)系統(tǒng)<G；*>，它僅有一個(gè)二元運(yùn)算*（因?yàn)槭谴鷶?shù)系統(tǒng)，所以運(yùn)算封閉性滿足），并滿足:結(jié)合律: (a*b)*c=a*(b*c)

含有單位元e: e*a=a*e=a

每一元a有逆元a-1: a*a-1=e假如滿足交換律:a*b=b*a

則形成一個(gè)交換群(commutativegroup),也叫阿貝爾群(abeliangroup).Remark:在不引發(fā)歧義下，經(jīng)常將運(yùn)算符號(hào)省略。a*b=ab2025/2/2142第42頁(yè)

例1<N；+><Z；+><I；·>和<R；·>不是群。

<I；+>、<R；+>和<R-｛0｝；·>都是群。例2設(shè)有Z4=｛0,1,2,3｝，模4加法運(yùn)算定義為則<Z4;>組成一個(gè)群。

012301230123123023013012Examples:2025/2/2143第43頁(yè)Examples:<Zm,+>是一個(gè)交換群，也叫加群。+是關(guān)于模m加法；<Zm-{0},·>，·是關(guān)于模m乘法。當(dāng)m是素?cái)?shù)時(shí)，它組成一個(gè)乘法交換群；但當(dāng)m不是素?cái)?shù)時(shí)，它不組成群。2025/2/2144第44頁(yè)循環(huán)群（CyclicGroup）群元素冪example: a3=a*a*aak=a*a*…*a(k個(gè)a相乘，k正整數(shù))要求:e=a0，a-k=a-1*a-1*…*a-1=(a-1)-k(k個(gè)a-1相乘，k正整數(shù))對(duì)任意整數(shù)m,n,am*an=am+n,(am)n=amn,a-n=(a-1)n=(an)-1.群中任何元都是某個(gè)元g冪，稱(chēng)群為循環(huán)群，g稱(chēng)為其一個(gè)生成元(generator)。i.e.對(duì)群中任一元b,存在k,使b=

gk.以g為生成元循環(huán)群記為G=<g>.稱(chēng)為由g生成循環(huán)群.2025/2/2145第45頁(yè)對(duì)任意負(fù)整數(shù),按照群中逆元表示方法例3

群<I；+>是循環(huán)群，1是生成元，10=0，對(duì)任意正整數(shù)n，n=1+1+…+1，按照群中元素冪表示方法n=1n.

例4

例2中群<Z4；

4>是循環(huán)群，1是其生成元，3也是其生成元。因?yàn)?0=0，11=1，12=1

41=res4(2)=2,13=12

41=2

41=res4(3)=3又30=0，31=3，32=3

43=res4(6)=2,33=32

43=2

43=res4(5)=12025/2/2146第46頁(yè)

例5

設(shè)G={a,b,c,e}，*是G上二元運(yùn)算，

*eabceabcaecbbceacbaeeabc

a*a=b*b=c*c=e*e=e,a*b=b*a=c,b*c=c*b=a，a*c=c*a=b<G；*>是一阿貝爾群，但它不是循環(huán)群，普通稱(chēng)這個(gè)群為Klein四元群。2025/2/2147第47頁(yè)群階和元素周期設(shè)<G；*>是一個(gè)群，假如G是有限集，則稱(chēng)<G；*>是有限群，G中元素個(gè)數(shù)稱(chēng)為群<G；*>階；若G是無(wú)限集，則稱(chēng)<G；*>是無(wú)限群。設(shè)<G;*>是一個(gè)群，a∈G，若存在正整數(shù)r，使得ar=e，則稱(chēng)元素a含有有限周期。使ar=e成立最小正整數(shù)r稱(chēng)為a周期。假如對(duì)于任何正整數(shù)r，都有ar≠

e，則稱(chēng)a周期為無(wú)限。2025/2/2148第48頁(yè)群階和元素周期Examples在群<R-{0};·>中，單位元1周期為1,-1周期為2.（-1）2=（-1）4=（-1）6=…=1群<Z4；

4>中，14=13

41=3

41=res4(4)=0；

21=2，22=2

42=res4(4)=0；34=33

43=1

43=res4(4)=0。

生成元1和3周期均為4，循環(huán)群<Z4；

4>階也為4。循環(huán)群<I；+>生成元1和–1，其周期均為無(wú)限，群<I；+>是一個(gè)無(wú)限階循環(huán)群。2025/2/2149第49頁(yè)群部分性質(zhì)消去律：設(shè)<G;*>是一個(gè)群，則對(duì)任意a,b∈G，（1）存在唯一元素x∈G，使a*x=b；（2）存在唯一元素y∈G，使y*a=b。設(shè)<G;*>是一個(gè)群，則對(duì)任意a,b,c∈G（1）若a*b=a*c,則b=c；（2）若b*a=c*a，則b=c。2025/2/2150第50頁(yè)群部分性質(zhì)求逆:設(shè)<G;*>是一個(gè)群，則對(duì)任意a,b,a1,a2,…,ak∈G(a*b)-1=b-1*a-1;(a1*a2*…*ak)-1=ak-1*…*a2-1*a1-1.關(guān)于元素周期:群<G;*>中元素

a若含有有限周期r，則當(dāng)且僅當(dāng)k

是r整數(shù)倍時(shí)，ak

=e.群中任一元素與它逆元含有相同周期。在有限群<G;*>中，每個(gè)元素均含有有限周期，且周期不超出群<G;*>階。結(jié)論對(duì)無(wú)限群不成立。如群<I；+>.

2025/2/2151第51頁(yè)群部分性質(zhì)設(shè)<G;*>是一由元素g生成循環(huán)群，則若g周期為n，則<G;*>是一個(gè)階為n有限循環(huán)群；若g周期為無(wú)限，則<G;*>是一個(gè)無(wú)限階循環(huán)群。2025/2/2152第52頁(yè)群部分性質(zhì)Examples群<Z4；

4>中單位元0周期是1；1和3周期均為4；2周期為2，群<Z4；

4>階4.設(shè)<G;*>是一個(gè)群，且對(duì)于任意a,b∈G，有(a*b)2=a2

*b2,則<G;*>是阿貝爾群。設(shè)Z6={0,1,2,3,4,5},

6是模6加法，定義為：a

6b=res6(a+b)，<Z6;6>是一個(gè)群。給出其單位元；各元素逆元；各元素周期。2025/2/2153第53頁(yè)設(shè)<G;*>是一個(gè)群，若<H;*>是<G;*>子代數(shù)，單位元e∈H，且對(duì)于任意a∈H，有a-1∈H，則稱(chēng)<H;*>是<G;*>子群。<G;*>非空子集H關(guān)于G運(yùn)算*組成子群，必須滿足：封閉性：H關(guān)于

*

封閉，a,b∈H，有a*b∈H;單位元：G單位元e∈H;可逆性：任意a∈H，有a-1∈H.Example:對(duì)于任意整數(shù)m，若令I(lǐng)m={mi:i

∈I}.則<Im;+>均組成<I；+>子群。子群（Subgroup）2025/2/2154第54頁(yè)若<H;*>是<G;*>子群，則<H;*>也是群。設(shè)<G;*>是一個(gè)群，H是G非空子集，若<H;*>也是群，則稱(chēng)<H;*>是<G;*>子群。（子群等價(jià)定義）設(shè)<G;*>是群，H是G非空子集，若(1)對(duì)于任意a,b∈H，有a*b∈H；(2)對(duì)任意a∈H，有a-1∈H，則<H;*>是<G;*>子群。子群（Subgroup）2025/2/2155第55頁(yè)設(shè)<G;*>是群，H是G非空子集，若對(duì)于任意a,b∈H，有a*b-1∈H，則<H;*>是<G;*>子群。設(shè)<G;*>是一有限群，若<H;*>是<G;*>子代數(shù)，則<H;*>是<G;*>子群。即：若對(duì)于任意a,b∈H，有a*b∈H，則<H;*>是<G;*>子群（H有限且關(guān)于運(yùn)算封閉就組成子群）。設(shè)<G;*>是一個(gè)群，若<H;*>是<G;*>有限子代數(shù)，則<H;*>是<G;*>子群。子群（Subgroup）2025/2/2156第56頁(yè)子群（Subgroup）Examples設(shè)<G;*>是一個(gè)群，a是G中任一元素，令H是a全部整數(shù)次冪集合，則H對(duì)于G運(yùn)算組成<G;*>子群。顯然<H;*>是由元素a生成一個(gè)循環(huán)群。設(shè)<G;*>是一個(gè)群，定義G子集H={h:對(duì)任意x∈G,h*x=x*h}，H對(duì)于運(yùn)算*組成<G;*>子群。2025/2/2157第57頁(yè)陪集（coset）、正規(guī)子群（normalsubgroup）H是G子群，a屬于G，aH={ah|h屬于H}稱(chēng)為G一個(gè)關(guān)于H左陪集（a所在陪集）。一樣Ha組成一個(gè)右陪集。對(duì)a，aH不一定等于Ha。假如對(duì)所以a，都有aH＝Ha，則稱(chēng)H為G一個(gè)正規(guī)子群。稱(chēng)aH或Ha為陪集。2025/2/2158第58頁(yè)拉格朗日(Lagrange)定理陪集定理：G關(guān)于H全部不用左（右）陪集組成G一個(gè)分劃。Lagrange定理：群G必為其子群H及其全部不相同陪集直和。推論：有限群階必為其子群階整數(shù)倍。素?cái)?shù)階群只有平庸子群（群本身與單位元）2025/2/2159第59頁(yè)群同態(tài)與同構(gòu)h:G1→G2群間一個(gè)映射，假如h保持群運(yùn)算，即：a,bofG，有h(ab)=h(a)h(b)，則稱(chēng)h為群G1,G2間一個(gè)同態(tài)映射，簡(jiǎn)稱(chēng)同態(tài)(homomorphism)。若同態(tài)h同時(shí)是一個(gè)雙射，那么稱(chēng)h為一個(gè)同構(gòu)映射，簡(jiǎn)稱(chēng)同構(gòu)(isomorphism)

。這是稱(chēng)兩群G1,G2是同構(gòu)。從代數(shù)結(jié)構(gòu)角度看，同構(gòu)群含有相同代數(shù)結(jié)構(gòu)，被視為同一群。2025/2/2160第60頁(yè)商群（Quotientgroup）群G正規(guī)子群H與其全部不相同陪集在陪集乘法意義下組成一個(gè)群，稱(chēng)為G關(guān)于H商群，記為G/H。f:G→G’群間一個(gè)同態(tài)映射，kerf＝{g:f(g)=e’,e’為G’單位元}，即kerf為G’單位元e’在G中原象集合。稱(chēng)kerf為同態(tài)映射f核。同態(tài)基本定理：設(shè)G’為G關(guān)于同態(tài)映射f象，則有：1.kerf是G正規(guī)子群；2.G’與商群G/kerf同構(gòu)。2025/2/2161第61頁(yè)變換群（Transformgroup）集合A上若干雙射（一一映射）對(duì)于映射復(fù)合運(yùn)算組成一個(gè)群，稱(chēng)其為A上一個(gè)變換群。一個(gè)集合A全部一一變換作成一個(gè)變換群。任何一個(gè)群都與一個(gè)變換群同構(gòu)。2025/2/2162第62頁(yè)置換群（permutationgroup）有限集A到直身一個(gè)雙射稱(chēng)為A上一個(gè)置換。＃A=n，稱(chēng)A上置換為n階置換。＃A＝n，A上全部n階置換在置換乘積（映射復(fù)合操作）下組成一個(gè)群，稱(chēng)為n階對(duì)稱(chēng)群(Symmetricgroup)，記為Sn。Sn任一子群，都稱(chēng)為一個(gè)置換群。全部n階偶置換（可分解為偶數(shù)個(gè)對(duì)換乘積置換）組成Sn一個(gè)子群，叫交織群(Alternativegroup)，記為An。2025/2/2163第63頁(yè)置換群（permutationgroup）對(duì)稱(chēng)群Sn階為n!，交織群An階為n!/2。凱萊(Caylay)定理：每一個(gè)有限群均同構(gòu)于由群元素集合上一個(gè)置換群（Sn一個(gè)子群）(

gG，gf(g),f(g)為G上一個(gè)置換，f(g)：gig

gi,全體f(g)組成G上置換群)2025/2/2164第64頁(yè)群生成元系G是一個(gè)群，S是G一個(gè)非空子集S生成子群H:G包含S最小子群,記H＝(S)。S生成子群H由S中元素及逆元任意乘積組成。假如G=(S)，那么稱(chēng)S為群G一個(gè)生成元系(Generatorsystemorgeneratorset)。當(dāng)＃S＝1，S＝{a}，那么S生成G一個(gè)循環(huán)子群，(S)＝<a>.群生成元系通常不唯一。2025/2/2165第65頁(yè)對(duì)稱(chēng)群生成系對(duì)稱(chēng)群Sn每個(gè)元都能夠?qū)懗?12),(13),…,(1n)這n-1個(gè)對(duì)換（2-循環(huán)置換）中若干個(gè)乘積。S={(12),(13),…,(1n)}是Sn一個(gè)生成元系。Remark：Sn還有其它生成元系。2025/2/2166第66頁(yè)環(huán)（Ring）帶兩個(gè)運(yùn)算（稱(chēng)加法和乘法）集合<R,+,·>滿足:關(guān)于加法+組成一個(gè)abelian群<R,+>，其單位元為‘0’稱(chēng)為零元；關(guān)于乘法·滿足:乘法封閉律；滿足結(jié)合律；a(bc)=(ab)c對(duì)加法分配律:a(b+c)=ab+ac則稱(chēng)<R,+,·>為一個(gè)環(huán)（Ring）假如乘法是交換，則稱(chēng)環(huán)為交換環(huán)(commutativering)環(huán)中關(guān)于乘法假如有單位元，稱(chēng)之為環(huán)單位元。2025/2/2167第67頁(yè)子環(huán)、理想、剩下類(lèi)環(huán)<R,+,·>子代數(shù)即為其子環(huán)。R子集關(guān)于R運(yùn)算依然是環(huán)，稱(chēng)為R子環(huán)。R子環(huán)I，假如同時(shí)關(guān)于乘法還滿足：對(duì)R中任意元r，I中任意元a，有ar,ra均仍屬于I.則稱(chēng)I為一個(gè)理想。R理想I，關(guān)于加法組成剩下類(lèi)集合上關(guān)于模I加法和乘法組成環(huán)，叫R模I剩下類(lèi)環(huán)。記為R/I.2025/2/2168第68頁(yè)環(huán)同態(tài)與同構(gòu)環(huán)同態(tài)與同構(gòu)映射定義類(lèi)似群同態(tài)與同構(gòu)。兩個(gè)環(huán)之間映射假如保持分別保持環(huán)運(yùn)算，就稱(chēng)為環(huán)同態(tài)假如同態(tài)是一一映射，就稱(chēng)為同構(gòu)。類(lèi)似地有同態(tài)基本定理。2025/2/2169第69頁(yè)零因子、整環(huán)若ab=0,但a,b都不是R中零元,

那么a(b)均稱(chēng)為左(右)零因子.不然，稱(chēng)為非零因子.無(wú)零因子環(huán):假如R中a,b有ab=o,那么必有a=0orb=0.整環(huán)（domain）：交換有單位元無(wú)零因子環(huán)，稱(chēng)為一個(gè)整環(huán)。2025/2/2170第70頁(yè)Example:整數(shù)集關(guān)于普通加法和乘法組成一個(gè)環(huán)且是一個(gè)整環(huán).<Zm,+,·>是一個(gè)交換環(huán)，稱(chēng)為模m剩下類(lèi)環(huán)。當(dāng)m是合數(shù)時(shí)，剩下類(lèi)環(huán)Zm中有零因子，Zm中a，若(a,m)=1,則a有逆元；當(dāng)m是素?cái)?shù)時(shí)，剩下類(lèi)環(huán)Zm是整環(huán)。2025/2/2171第71頁(yè)除環(huán)、域一個(gè)環(huán)關(guān)于其乘法不一定有單位元，另外其任一元也不一定有乘法逆元。假如一個(gè)環(huán)有單位元，而且任一非零元都有逆元，則稱(chēng)其為一個(gè)除環(huán)。所以<R,+,·>是除環(huán)，它最少有一非零元，且<R,+>是加群；<R-{0},·>是群。一個(gè)除環(huán)，假如其關(guān)于乘法是交換，則稱(chēng)其為一個(gè)域（Field）。2025/2/2172第72頁(yè)有限域（GaloisFields）有限域也叫Galois域，在密碼學(xué)中有主要作用。三個(gè)結(jié)論：每個(gè)有限域階必為素?cái)?shù)冪。對(duì)任意素?cái)?shù)p和正整數(shù)n，存在pn階域。同階有限域必同構(gòu)。于是：在同構(gòu)意義下，pn階有限域有且只有一個(gè)，記為GF(pn).尤其地，經(jīng)慣用到有限域:GF(p)－－稱(chēng)為素域GF(2n)2025/2/2173第73頁(yè)GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}上關(guān)于模p加法、乘法組成有限域。P為素?cái)?shù)時(shí)，其中任意非零數(shù)都有逆元.2025/2/2174第74頁(yè)ExampleGF(7)2025/2/2175第75頁(yè)GF(p)中乘法逆元算法經(jīng)過(guò)擴(kuò)展Euclidean算法得到:EXTENDEDEUCLID(m,b)1.(A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);（bmodm沒(méi)有逆）3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB3（A3除以B3商）5.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2GF(pn)中乘法求逆類(lèi)似（換成關(guān)于多項(xiàng)式除法）2025/2/2176第76頁(yè)Inverseof550inGF(1759)2025/2/2177第77頁(yè)域上多項(xiàng)式域F上多項(xiàng)式為形如：表示式，其中n∈N,ai∈F,i=1,2,…,n.若an≠0,稱(chēng)n為該多項(xiàng)式次數(shù),記n=deg(f(x)),并稱(chēng)an為首項(xiàng)系數(shù),首項(xiàng)系數(shù)為1多項(xiàng)式稱(chēng)為首1多項(xiàng)式.2025/2/2178第78頁(yè)多項(xiàng)式整環(huán)記F[x]為域上全部多項(xiàng)式f(x)組成集合，則F[x]關(guān)于通常多項(xiàng)式加法+和乘法·形成一個(gè)整環(huán)，叫域F上（一元）多項(xiàng)式環(huán)。0為其零元，1為其單位元。在F[x]上類(lèi)似于整數(shù)環(huán)，關(guān)于多項(xiàng)式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。2025/2/2179第79頁(yè)多項(xiàng)式帶余除法帶余除法：a(x),b(x)∈F[x],且b(x)≠0,則存在唯一q(x),r(x)∈F[x],使a(x)=q(x)b(x)+r(x),式中deg(r(x))≤deg(b(x)).q(x)稱(chēng)為商式,r(x)稱(chēng)為余式也用a(x)modp(x)

表示a(x)除以p(x)余式.稱(chēng)為a(x)模p(x)，p(x)稱(chēng)為模多項(xiàng)式。2025/2/2180第80頁(yè)不可約多項(xiàng)式若存在q(x),b(x)，deg(q(x))≥1,deg(b(x))≥1，使a(x)=q(x)b(x)，則稱(chēng)a(x)為可約多項(xiàng)式，不然稱(chēng)為不可約(既約)多項(xiàng)式。2025/2/2181第81頁(yè)多項(xiàng)式運(yùn)算僅考慮一元多項(xiàng)式可把多項(xiàng)式運(yùn)算分為三種：使用代數(shù)基本規(guī)則普通多項(xiàng)式運(yùn)算；系數(shù)運(yùn)算是模p運(yùn)算多項(xiàng)式運(yùn)算，即系數(shù)在Zp中；系數(shù)在Zp中，且多項(xiàng)式被定義為模一個(gè)多項(xiàng)式m(x)多項(xiàng)式運(yùn)算。2025/2/2182第82頁(yè)普通多項(xiàng)式運(yùn)算加法、減法為(相同次項(xiàng))對(duì)應(yīng)系數(shù)加減法乘法為逐項(xiàng)相乘。egletf(x)=x3+x2+2andg(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+22025/2/2183第83頁(yè)系數(shù)在Zp中多項(xiàng)式運(yùn)算在普通多項(xiàng)式運(yùn)算中，全部系數(shù)都取modp運(yùn)算。尤其是mod2多項(xiàng)式運(yùn)算ieallcoefficientsare0or1eg.letf(x)=x3+x2andg(x)=x2+x+1f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x22025/2/2184第84頁(yè)模多項(xiàng)式運(yùn)算基于多項(xiàng)式帶余除法:f(x)=q(x)g(x)+r(x)r(x)稱(chēng)為余式(remainder)記r(x)=f(x)modg(x)定義模g(x)多項(xiàng)式加法、乘法。假如沒(méi)有余式，說(shuō)g(x)整除

f(x)假如g(x)僅有它自己和1為其因式，說(shuō)g(x)不可約(或既約)多項(xiàng)式(或素多項(xiàng)式)全部多項(xiàng)式在模不可約多項(xiàng)式加法乘法下組成一個(gè)域。2025/2/2185第85頁(yè)模p(x)剩下類(lèi)環(huán)F[x]中一個(gè)多項(xiàng)式p(x)，(p(x))為由p(x)生成F[x]子環(huán)，它是一個(gè)理想(主理想).F[x]/(p(x))形成一個(gè)模p(x)剩下類(lèi)環(huán)。它等同于全部n-1次多項(xiàng)式集合上關(guān)于模p(x)加法乘法運(yùn)算組成環(huán)。當(dāng)p(x)為不可約多項(xiàng)式時(shí)，其形成一個(gè)域。2025/2/2186第86頁(yè)最大公因式尋找多項(xiàng)式最大公因式c(x)=GCD(a(x),b(x))假如c(x)

是同時(shí)整除a(x),b(x)

次數(shù)最高多項(xiàng)式。（等價(jià)定義）經(jīng)過(guò)擴(kuò)充Euclidean算法來(lái)尋找:EUCLID[a(x),b(x)]1.A(x)←a(x);B(x)←b(x)2.ifB(x)=0returnA(x)=gcd[a(x),b(x)]3.R(x)=A(x)modB(x)4.A(x)←B(x)5.B(x)←R(x)6.goto22025/2/2187第87頁(yè)模多項(xiàng)式運(yùn)算、GF(2n)有限域元素個(gè)數(shù)必為pn，p為素?cái)?shù)，n為正整數(shù)。p個(gè)元素上以模p運(yùn)算產(chǎn)生一個(gè)域,Zp。但含有pn個(gè)元素集合上模pn運(yùn)算卻不一定能產(chǎn)生域。怎樣定義適當(dāng)運(yùn)算，使之pn個(gè)元成域？Zpn關(guān)于模pn運(yùn)算是不行。2025/2/2188第88頁(yè)模多項(xiàng)式運(yùn)算、GF(2n)S為域Zp上次數(shù)小于等于n-1全部多項(xiàng)式組成。S中共有pn個(gè)不一樣多項(xiàng)式。定義適當(dāng)運(yùn)算，每個(gè)這么S都是一個(gè)有限域。運(yùn)算定義為：運(yùn)算遵照基本代數(shù)規(guī)則中普通多項(xiàng)式運(yùn)算規(guī)則系數(shù)運(yùn)算以p為模，即遵照有限域Zp上運(yùn)算規(guī)則。多項(xiàng)式運(yùn)算遵照模某個(gè)n次既約多項(xiàng)式m(x)運(yùn)算。S即為一個(gè)pn階有限域，在同構(gòu)意義下，即為GF(pn).實(shí)際上，S=Zp[x]/(m(x)).2025/2/2189第89頁(yè)模多項(xiàng)式運(yùn)算、GF(2n)P=2時(shí)，即為GF(2n).求其中逆元經(jīng)過(guò)擴(kuò)展Euclidean求逆算法（與前面GF(p)中求逆類(lèi)似，將那里整數(shù)換成Zp上多項(xiàng)式）2025/2/2190第90頁(yè)ExampleGF(23)2025/2/2191第91頁(yè)計(jì)算上考慮GF(2n)中多項(xiàng)式系數(shù)都是0or1,所以任一多項(xiàng)式都能夠由它n個(gè)二進(jìn)制系數(shù)唯一表示。所以GF(2n)中每個(gè)多項(xiàng)式都能夠表示成一個(gè)n位二進(jìn)制整數(shù)。兩個(gè)多項(xiàng)式加法等同于按位異或(XOR)運(yùn)算。乘法經(jīng)過(guò)左移一位后按位異或來(lái)實(shí)現(xiàn)重復(fù)取模運(yùn)算來(lái)簡(jiǎn)約高次多項(xiàng)式(alsoshift&XOR)2025/2/2192第92頁(yè)布爾代數(shù)代數(shù)系統(tǒng)(B;－,,)(這里

和

分別稱(chēng)并和交運(yùn)算、－稱(chēng)為求補(bǔ)運(yùn)算)假如滿足以下性質(zhì)，稱(chēng)為一個(gè)布爾代數(shù)：對(duì)于B中任意元素x,y,z，有：(1)交換律:x

y＝y(tǒng)

x，x

y＝y(tǒng)

x(2)結(jié)臺(tái)律:x

(y

z)＝(x

y)

zx

(y

z)＝(x

y)

z(3)等冪律:x

x＝x，x

x＝x(4)吸收律:x

(x

y)＝x，、x

(x

y)＝x2025/2/2193第93頁(yè)(5)分配律:x

(y

z)＝(x

y)

(x

z)x

(y

z)＝(x

y)

(x

z)(6)同一律:x

0＝x,x

1＝x(7)零一律:x

1＝1，x

0＝o(8)互補(bǔ)律:x

(－x)=1，x

(－x)＝o(9)對(duì)合律:－(－x)＝x(10)德·摩根定律:－(x

y)＝(－x)(－y)－(x

y)＝(－x)(－y)以上這10條性質(zhì)并不都是獨(dú)立。實(shí)際上，全部其它性質(zhì)都可由其中四條：交換律、分配律、同一律和互補(bǔ)律推導(dǎo)出來(lái)。2025/2/2194第94頁(yè)如：集合M冪集2M關(guān)于集合并集、交集、補(bǔ)集運(yùn)算形成一個(gè)布爾代數(shù)。有限布爾代數(shù)基域基數(shù)是2冪。2025/2/2195第95頁(yè)布爾函數(shù)布爾表示式布爾代數(shù)B上由x1,x2,…,xn產(chǎn)生布爾表示式歸納地定義為B元素以及符號(hào)x1,x2,…,xn都是布爾表示式；布爾表示式并、交、補(bǔ)運(yùn)算還是布爾表示式。布爾函數(shù)假如x1,x2,…,xn被解釋為只能在B中取值變量，則一個(gè)由x1,x2,…,xn產(chǎn)生布爾表示式實(shí)際上就是一個(gè)從Bn到B函數(shù)。2025/2/2196第96頁(yè)由x1,x2,…,xn產(chǎn)生布爾表示式有時(shí)也稱(chēng)為B上一個(gè)n元布爾函數(shù)。Bn到B函數(shù)不一定是布爾函數(shù)，＃B>2時(shí)，必定有不是布爾函數(shù)函數(shù)存在。＃B=2時(shí)，Bn到B函數(shù)都是布爾函數(shù)。多重布爾函數(shù)：(f1,f2,…,fm):Bn×Bn×...×Bn到Bm函數(shù)。其中fi是Bn到B布爾函數(shù)。2025/2/2197第97頁(yè)GF(2)上布爾函數(shù)GF(2)只有兩個(gè)：0，1。關(guān)于這兩個(gè)量之間邏輯運(yùn)算，GF(2)成為布爾代數(shù)。這時(shí)，GF(2)

n到GF(2)一個(gè)映射就稱(chēng)為一個(gè)n元布爾函數(shù)(因?yàn)镚F(2)基數(shù)為2)。對(duì)于GF(2)中元素，有x

y＝x·yx

y＝x+y+x·y－x=x+1這里+,·分別表示GF(2)中加(異或)、乘(與)運(yùn)算。2025/2/2198第98頁(yè)作為邏輯運(yùn)算函數(shù)，布爾函數(shù)是研究數(shù)字邏輯電路主要數(shù)學(xué)工具，也是研究以此為基礎(chǔ)一切科學(xué)技術(shù)主要工具，從而也是研究密碼學(xué)和密碼技術(shù)主要工具。不論在流密碼還是在分組密碼中，不論在私鑰還是在公鑰密碼中，布爾函數(shù)都有主要應(yīng)用。2025/2/2199第99頁(yè)布爾函數(shù)表示為了方便布爾函數(shù)理論和應(yīng)用，人們?cè)诓灰粯忧闆r下對(duì)布爾函數(shù)采取了不一樣表示方法，主要有：真值表表示法小項(xiàng)表示法多項(xiàng)式表示法walsh譜表示法矩陣表示法等2025/2/21100第100頁(yè)布爾函數(shù)研究問(wèn)題布爾函數(shù)表示布爾函數(shù)研究方法布爾函數(shù)設(shè)計(jì)實(shí)現(xiàn)布爾函數(shù)性質(zhì)滿足一定性質(zhì)布爾函數(shù)特征刻劃、存在性、結(jié)構(gòu)與計(jì)數(shù)布爾函數(shù)不一樣性質(zhì)之間等價(jià)、相斥、相容、制約等關(guān)系密碼學(xué)中，布爾函數(shù)一條性質(zhì)反應(yīng)一個(gè)安全性能指標(biāo)，當(dāng)不一樣性能指標(biāo)相互制約時(shí)，怎樣折衷以提升綜合性能；伴隨技術(shù)發(fā)展和新攻擊方法出現(xiàn)，新性質(zhì)提出和研究等等2025/2/21101第101頁(yè)本原根（本原元）由Euler定理有:a?(n)=1modn,GCD(a,n)=1考慮更普通表示形式am=1modn,GCD(a,n)=1則最少有m=?(n)使之成立，但可能有更小m存在一旦冪次到m,a冪便出現(xiàn)周期循環(huán)假如最小m=?(n)，則a稱(chēng)為n一個(gè)本原根(primitiveroot)假如n=p為素?cái)?shù)，則a連續(xù)冪生成模p剩下類(lèi)群。2025/2/21102第102頁(yè)使am=1modn

成立最小正冪m(這里(a,n)=1)為以下之一amodn階a

所屬模n指數(shù)a

所產(chǎn)生周期長(zhǎng)。Zp中a，假如a階數(shù)?(n)，在a就是n一個(gè)本原根。假如a是n本原根，則其冪a,a2,…,a?(n)是(模n)各不相同，且均與n互素。2025/2/21103第103頁(yè)尤其，對(duì)素?cái)?shù)p，若a是p本原根，則a,a2,…,ap-1是(模p)各不相同。a是Zp生成元。如：素?cái)?shù)19本原根為2,3,10,13,14,15.并不是全部整數(shù)都有本原根。實(shí)際上，只有形為2,4,pb,2pb整數(shù)才有本原根，這里p任何奇素?cái)?shù)，b正整數(shù)。2025/2/21104第104頁(yè)離散對(duì)數(shù)或指標(biāo)求一個(gè)數(shù)模p離散對(duì)數(shù)(discretelogarithm)是求冪逆問(wèn)題即求x使之滿足ax=bmodp記x=logabmodporx=inda,p(b)－－以底a(模p)b指標(biāo)。假如a是一個(gè)本原根，則x總存在,不然不一定。x=log34mod13(x使3x=4mod13)不存在而x=log23mod13=4（經(jīng)過(guò)列出所以?xún)绫阒?025/2/21105第105頁(yè)離散對(duì)數(shù)問(wèn)題模指數(shù)運(yùn)算被認(rèn)為是一個(gè)單向函數(shù)，即：對(duì)于給定整數(shù)n,a和x，輕易經(jīng)過(guò)“平方-乘”方法計(jì)算出axmodn；不過(guò)，對(duì)于給定整數(shù)n,a和b，由方程ax=bmodn求解整數(shù)x確是一個(gè)難題。有限域Zp上離散對(duì)數(shù)問(wèn)題是：對(duì)于給定素?cái)?shù)p，有限域Zp上一個(gè)本原元a，Zp中非零元b，求解滿足ax=bmodp整數(shù)x(0≤x≤p-2)，x=logab(modp)(通常記為x=logab)。2025/2/21106第106頁(yè)離散對(duì)數(shù)計(jì)算當(dāng)前還沒(méi)有能夠計(jì)算離散對(duì)數(shù)問(wèn)題多項(xiàng)式時(shí)間算法。對(duì)于已知攻擊方法，素?cái)?shù)選取應(yīng)該滿足最少兩個(gè)條件：長(zhǎng)度大于150位p-1最少有一個(gè)大素?cái)?shù)因子窮搜索方法能夠?qū)﹄x散對(duì)數(shù)進(jìn)行求解，但對(duì)于足夠大素?cái)?shù)p并不可行，其所需計(jì)算時(shí)間和存放空間均為O(p).2025/2/21107第107頁(yè)離散對(duì)數(shù)計(jì)算有3個(gè)群離散對(duì)數(shù)是密碼設(shè)計(jì)人員最為關(guān)心。這三個(gè)群分別是：素域GF(p)乘法群特征為2有限域GF(2n)上乘法群有限域F上橢圓曲線群EC(F)2025/2/21108第108頁(yè)離散對(duì)數(shù)計(jì)算GF(p)上計(jì)算離散對(duì)數(shù)問(wèn)題算法有很各種。平凡算法：經(jīng)過(guò)預(yù)計(jì)算全部可能ax