返回總目錄第3章

根底數論教學目的了解模運算及輾轉相除法了解中國余式子定律了解Lagrange定理與費馬小定理了解原根、二次剩余、Galois域等概念了解質數理論和連分數了解密碼平安偽隨機數字生成器

模運算與輾轉相除法本章內容

中國余式子定律

Lagrange定理與費馬小定理

原根

二次剩余

Galois域

連分數

質數理論密碼平安偽隨機數字生成器模運算與輾轉相除法3.1模運算與輾轉相除法假設今天是星期五，請問10000天后是星期幾？

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

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

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

（2）交換律：若同余類則（3）結合律：若同余類則

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

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

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

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

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

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

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

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

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

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

為非二次剩余

Legendre符號

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

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

公理：*對有分配律質數理論3.7質數理論定義令p為不為1的正整數，p為質數（Prime）若某正整數d整除p（記為），則d=1或d=p。Eratosthenes篩法質數定理質數定理Riemann猜測Hardy-Littlewood猜測與同時為質數連分數3.8連分數定義任何以下形式的數均稱為連分數其中，q1、q2、……為整數連分數性質令為一實數，其連分數表達式為其中，而其各項連分數的收斂值為：當中滿足遞推關系及初始條件連分數定理：令（且）為實數x的某項連分數的收斂值密碼平安偽隨機數生成器3.9密碼平安偽隨機數生成器BlumBlumShub(){ do { p=RandomPrime(); }while(p%4!=3); do { q=RandomPrime(); }while(p%4!=3); //p,q為隨機質數且=3mod4 n=p*q; do{ s=RandomInteger(1,n); }while(gcd(s,n)!=1); //gcd(s,n)=1且s為隨機數種子 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偽隨機數字生成器

密碼平安偽隨機數生成器算法RSA偽隨機數字生成器

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