《密碼學(xué)-加密演算法》-第3章-基礎(chǔ)數(shù)論

返回總目錄第3章

根底數(shù)論教學(xué)目的了解模運算及輾轉(zhuǎn)相除法了解中國余式子定律了解Lagrange定理與費馬小定理了解原根、二次剩余、Galois域等概念了解質(zhì)數(shù)理論和連分?jǐn)?shù)了解密碼平安偽隨機(jī)數(shù)字生成器

模運算與輾轉(zhuǎn)相除法本章內(nèi)容

中國余式子定律

Lagrange定理與費馬小定理

原根

二次剩余

Galois域

連分?jǐn)?shù)

質(zhì)數(shù)理論密碼平安偽隨機(jī)數(shù)字生成器模運算與輾轉(zhuǎn)相除法3.1模運算與輾轉(zhuǎn)相除法假設(shè)今天是星期五，請問10000天后是星期幾？

〔即5+10000除以7的余數(shù)〕即：10000天后是星期二

同余定義（同余，Congruence）：令。令為兩整數(shù)，稱a同余b模n，記為，當(dāng)n整除b-a。而所有與a同余的整數(shù)所組成的集合，即稱為a的同余類。所有同余類所形成的集合同余類同余類滿足的性質(zhì)：〔1〕〔反身性，Reflexivity〕（2）（對稱性，Symmetry）

若則〔3〕〔遷移性，Transitivity〕若則例：令那么模運算加法：（1）封閉性：若同余類則

（2）交換律：若同余類則（3）結(jié)合律：若同余類則

（4）存在加法單位素：存在，使得

（5）存在加法反元素：對任一存在使得減法：乘法：交換群定義（交換群）考慮，其中G為集合，而*為運算。令公理：（1）封閉性：則；（2）交換律：則；（3）結(jié)合律：則；（4）存在單位素：，，使得（5）存在反元素：，，使得假設(shè)公理1、3、4、5成立，稱為群(Group)；假設(shè)以上公理1～5都成立，稱為交換群。交換環(huán)此時除了為交換群以外，另外針對乘法運算也滿足封閉性、交換律、結(jié)合律以及存在乘法單位素（即）等性質(zhì)，但并非所有非零元素都有乘法反元素，另外乘法對加法有分配律，即：若則此時，以代數(shù)的術(shù)語，稱為交換環(huán)（CommutativeRing）?？紤]輾轉(zhuǎn)相除法例：求7812及6084的最大公因子

被除數(shù)=商×除數(shù)+余數(shù)，gcd〔被除數(shù)，除數(shù)〕=gcd〔除數(shù)，余數(shù)〕輾轉(zhuǎn)相除法就是利用此性質(zhì)，反復(fù)以〔除數(shù)/余數(shù)〕取代〔被除數(shù)/除數(shù)〕k01234567rk78126048172890082872360qk1311112其中：所以gcd(7812,6084)=36

輾轉(zhuǎn)相除法定理3.1整數(shù)線性方程有整數(shù)解證明：若則：為一整數(shù)解假設(shè)有整數(shù)解因：且所以借助廣義輾轉(zhuǎn)相除法，存在整數(shù)，使得對模乘法例：令n為自然數(shù)，則對模乘法為交換群

證明：根據(jù)交換群封閉性那么因，故存在乘法反元素、使得且，而故為的乘法反元素。模運算與輾轉(zhuǎn)相除法3.2中國余式子定理〔ChineseRemainderTheorem〕定理：令為兩兩互質(zhì)的正整數(shù)，令則同余聯(lián)立方程組在集合有惟一解，其解為其中，而余式定理應(yīng)用其中，為n的質(zhì)因數(shù)，性質(zhì)1：存在群同構(gòu)〔GroupIsomorphism〕定義：當(dāng)為正整數(shù)時，定義Euler-Phi函數(shù)為性質(zhì)2：Lagrange定理與費馬小定理3.3Lagrange定理與費馬小定理

令為群，若為子集，且在相同的運算*形成群則稱（或H）為G的子群（Subgroup）。子群(Subgroup)Lagrange定理定理〔Lagrange定理〕假設(shè)G為有限群，H為G中之子群，那么證明：H為G的子群，為方便起見，假設(shè)為乘法群。可定等價關(guān)系如下：假設(shè)如此定義出的等價關(guān)系可將分割成假設(shè)干個等價類，即每個等價類都有#H個元素（考慮為1－1對應(yīng)）。因此#H整除#G費馬小定理定理〔費馬小定理〕令為p質(zhì)數(shù)、a為與p互質(zhì)的整數(shù)，那么證明：考慮乘法群，為其子群，根據(jù)Lagrange定理所以其中因此：原根考慮2的次方〔mod11〕：3.4原根可以發(fā)現(xiàn)乘法群

中的同余類均可表示為[2]的若干次方此時稱2為乘法群的原根（PrimitiveRoot）

當(dāng)時，則10必整除x；此時稱10為2在（mod11）（或在乘法群）的秩（Order）秩定義：令G為乘法群，而g∈G為其中一元素，那么元素g的秩〔Order〕定義為也可能不存在x∈

N使得，此時定義。若G為有限群，則為G的子群，有，根據(jù)Lagrange定理，子群的元素個數(shù)必整除母群G的元素個數(shù)，故原根定理定理：令g為質(zhì)數(shù)p上的原根，那么〔1〕假設(shè)x為整數(shù)，那么〔2〕假設(shè)i、j為整數(shù)，那么證明：（1）若欲證假設(shè)不成立，可寫得：但：…...所以：有r個元素，這與p為原根的假設(shè)矛盾。（2）假設(shè)i>j，將同余式兩邊同乘以得：利用已證明的性質(zhì)1，此等價于：子群與循環(huán)群令G為任一乘法群，為任一元素，則為G中的子群（封閉性與反元素的存在性自然成立）。此<g>子群稱為由元素g所生成的子群。定義：子群定義：循環(huán)群〔CyclicGroup〕若存在使得，則稱G為循環(huán)群（CyclicGroup），而g為原根或生成元（Generator）。二次剩余3.5二次剩余QuadraticResidue

定義：同余式a與n為互質(zhì)整數(shù)假設(shè)有整數(shù)解，稱a為〔modn〕的二次剩余〔QuadraticResidue〕假設(shè)無解那么稱a為〔modn〕的非二次剩余〔QuadraticNonresidue〕。二次剩余的性質(zhì)性質(zhì)令p為奇質(zhì)數(shù)，可定義函數(shù)則：a為二次剩余其中：為二次剩余

為非二次剩余

Legendre符號

定義：令p為質(zhì)數(shù)，定義Legendre符號如下：定理〔Euler判別〕令p為質(zhì)數(shù)，a與p互質(zhì)。那么：Legendre符號性質(zhì)令p為奇質(zhì)數(shù)，a、b為與p互質(zhì)的整數(shù)，那么（1）若則〔2〕〔3〕〔4〕〔5〕定理QuadraticReciprocity令p、q為奇質(zhì)數(shù)，那么Jacobi符號定義：令a為整數(shù)，n>0為奇整數(shù)，其質(zhì)因數(shù)分解為定義Jacobi符號：性質(zhì)：當(dāng)n>0為奇整數(shù)，Jacobi符號才可能有意義〔5〕〔3〕〔4〕〔2〕〔6〕注：a、b為整數(shù)，m、n為奇整數(shù)Galois域3.6Galois域定義域（Field）：令K為一集合，并含有兩個運算“”及“*”，則（K，，*）為域公理：（K，，*）為交換群，即（1）（-封閉性）（2）（-單位素）（3）（-反元素）（4）（-結(jié)合律）（5）（-交換性）

xyxxxxx=（xy）z=x（yz）xxyGalois域公理：為交換群即：（1）（*-封閉性）（2）（*-單位素）（3）（*-反元素）（4）（*-結(jié)合律）（5）（*-交換性）

公理：*對有分配律質(zhì)數(shù)理論3.7質(zhì)數(shù)理論定義令p為不為1的正整數(shù)，p為質(zhì)數(shù)（Prime）若某正整數(shù)d整除p（記為），則d=1或d=p。Eratosthenes篩法質(zhì)數(shù)定理質(zhì)數(shù)定理Riemann猜測Hardy-Littlewood猜測與同時為質(zhì)數(shù)連分?jǐn)?shù)3.8連分?jǐn)?shù)定義任何以下形式的數(shù)均稱為連分?jǐn)?shù)其中，q1、q2、……為整數(shù)連分?jǐn)?shù)性質(zhì)令為一實數(shù)，其連分?jǐn)?shù)表達(dá)式為其中，而其各項連分?jǐn)?shù)的收斂值為：當(dāng)中滿足遞推關(guān)系及初始條件連分?jǐn)?shù)定理：令（且）為實數(shù)x的某項連分?jǐn)?shù)的收斂值密碼平安偽隨機(jī)數(shù)生成器3.9密碼平安偽隨機(jī)數(shù)生成器BlumBlumShub(){ do { p=RandomPrime(); }while(p%4!=3); do { q=RandomPrime(); }while(p%4!=3); //p,q為隨機(jī)質(zhì)數(shù)且=3mod4 n=p*q; do{ s=RandomInteger(1,n); }while(gcd(s,n)!=1); //gcd(s,n)=1且s為隨機(jī)數(shù)種子 x[0]=s; for(i=1;i<=k;i++) { x[i]=x[i-1]*x[i-1]%n; b[i]=x[i]&1;//取最末位 }; return(b[1],b[2],...,b[k]);}算法Blum-Blum-Shub偽隨機(jī)數(shù)字生成器

密碼平安偽隨機(jī)數(shù)生成器算法RSA偽隨機(jī)數(shù)字生成器

RSA_PseudomBitGen(){ p=RandomPrime(); q=RandomPrime(); n=p*q;