現(xiàn)代密碼學第四章公鑰密碼4.1密碼學中的一些常用數(shù)學知識4.2公鑰密碼體制的基本概念4.3RSA算法4.4背包密碼體制4.5Rabin密碼體制4.6NTRU公鑰密碼系統(tǒng)4.7橢圓曲線密碼體制4.8SM2橢圓曲線公鑰密碼加密算法第四章公鑰密碼4.1密碼學中的一些常用數(shù)學知識4.1.1群、環(huán)、域4.1.2素數(shù)和互素數(shù)4.1.3模運算4.1.4模指數(shù)運算4.1.5費爾碼定理、歐拉定理

卡米歇爾定理4.1.6素性檢驗4.1.7歐幾里得算法第四章公鑰密碼4.1.8中國剩余定理4.1.9離散對數(shù)4.1.10二次剩余4.1.11循環(huán)群4.1.12循環(huán)群的選取4.1.13雙線性映射4.1.14計算復雜性第四章公鑰密碼4.1.1群、環(huán)、域

代數(shù)系統(tǒng)是對要研究的現(xiàn)象或過程建立起的一種數(shù)學模型，模型中包括要處理的數(shù)學對象的集合以及集合上的關(guān)系或運算，運算可以是一元的也可以是多元的，可以有一個也可以有多個。設是集合上的運算，若對

，有

，則稱

對運算

是封閉的。若是一元運算，對

，有

，則稱

對運算

是封閉的。

群、環(huán)、域都是代數(shù)系統(tǒng)（也稱代數(shù)結(jié)構(gòu)）

若對

，有

，則稱滿足結(jié)合律。第四章公鑰密碼定義4-2設

是一個代數(shù)系統(tǒng)，

滿足：（1）封閉性。

（2）結(jié)合律。（3）存在元素

，對

，有

稱

為

的單位元。（4）對，存在元素，使得；稱

為元素

的逆元。則稱是群。若其中的運算已明

確，有時將簡記為。定義4-1設

是一個代數(shù)系統(tǒng)，

滿足：（1）封閉性。（2）結(jié)合律。

則稱

是半群。第四章公鑰密碼如果是有限集合，則稱是有限群，否則是無限群。有限群中，的元素個數(shù)稱為群的階數(shù)。如果群中的運算還滿足交換律，即對，有

，則稱為交換群或Abel群。群中運算一般稱為乘法，稱該群為乘法群。若運算改為，則稱為加法群，此時逆元寫成。第四章公鑰密碼【例4-1】1.是Abel群，其中是整數(shù)集合。

2.是Abel群，其中是有理數(shù)集合。

3.設是任一集合，表示上的雙射函數(shù)集合，是群，這里表示函數(shù)的合成，通常這個群不是Abel群。

4.是Abel群，其中

，是模加，

等于

，。不是群，因為0沒有逆元，這

里

是模乘，等于。第四章公鑰密碼定義4-3設是一個群，是整數(shù)集合。如果存在一個元素，對于每一個元素，都有一個相應的，能把表示成，則稱是循環(huán)群，稱為循環(huán)群的生成元，記。稱滿足方程的最小正整數(shù)為

的階，記為。定義4-4若代數(shù)系統(tǒng)的二元運算和滿足：（1）是Abel群；（2）是半群；（3）乘法在加法上可分配，即對，有和則稱是環(huán)。密碼學中使用的群大多為循環(huán)群。第四章公鑰密碼【例4-2】（1）是環(huán)，因為是Abel群，是半群，乘法

在加法上可分配。（2）是環(huán)，因為是Abel群，是半群，對

可分配。（3）是環(huán)，這里是上方陣集合，是矩陣

加法，是矩陣乘法。（4）是環(huán)，這里是所有實系數(shù)的多項式集合，

和分別是多項式加法和乘法。第四章公鑰密碼定義4-5若代數(shù)系統(tǒng)的二元運算和滿足：(1) 是Abel群；(2) 是Abel群，其中0是+的單位元；(3)乘法在加法上可分配，即對，有和則稱是域。、、都是域，其中、、分別是有理數(shù)集合、實數(shù)集合和復數(shù)集合。第四章公鑰密碼已知所有實系數(shù)的多項式集合在多項式加法和乘法運算下構(gòu)成環(huán)。類似地，任意域上的多項式（即系數(shù)取自）集合在多項式的加法和乘法運算下也構(gòu)成環(huán)。

中不可約多項式的概念與整數(shù)中的素數(shù)概念類似，是指在上僅能被非0常數(shù)或自身的常數(shù)倍除盡，但不能被其它多項式除盡的多項式。

有限域是指域中元素個數(shù)有限的域，元素個數(shù)稱為域的階。若是素數(shù)的冪，即，其中是素數(shù)，

是自然數(shù)，則階為的域稱為Galois域，記為或。第四章公鑰密碼兩個多項式的最高公因式為1時，稱它們互素。多項式的系數(shù)取自以素數(shù)為模的域時，這樣的多項式集合記為。若是上的次不可約多項式，上多項式加法和乘法改為以為模的加法和乘法，此時的多項式集合記為，集合中元素個數(shù)為，

是一個有限域。第四章公鑰密碼1.因子設是兩個整數(shù)，如果存在另一整數(shù)，使得

，則稱整除，記為，且稱是的因子。否則稱不整除，記為。4.1.2素數(shù)和互素數(shù)整除的性質(zhì)：(1) ，那么；(2) 且，則；(3)對任一

，；(4) ，則對任意整數(shù)，有。第四章公鑰密碼這里只給出(4)的證明，其它三個性質(zhì)的證明都很簡單，證(4)：

由知，存在整數(shù)、，使得，

所以

因此。第四章公鑰密碼2.素數(shù)稱整數(shù)是素數(shù)，如果的因子只有和。若不是素數(shù)，則稱為合數(shù)。任一整數(shù)都能唯一地分解為以下形式：

其中，是素數(shù)，。例如

，這一性質(zhì)稱為整數(shù)分解的唯一性，也可如下陳述：設是所有素數(shù)集合，則任意整數(shù)都能唯一地寫成以下形式：

其中。第四章公鑰密碼等號右邊的乘積項取所有的素數(shù)，然而大多指數(shù)項為0。相應地，任一正整數(shù)也可由非0指數(shù)列表表示。如：11011可表示為。兩數(shù)相乘等價于對應的指數(shù)相加，即：由可得：對每一素數(shù)，。而由可得：對每一素數(shù)

。這是因為只能被

整除。第四章公鑰密碼3.互素數(shù)稱是兩個整數(shù)的最大公因子，如果(1)是的因子也是的因子，即是的公因子；(2)和的任一公因子，也是的因子。表示為。由于我們要求最大公因子為正，所以

。一般。

由任一非0整數(shù)能整除0，可得

。如果將都表示為素數(shù)的乘積，則極易確定。第四章公鑰密碼【例4-3】

一般由可得：對每一素數(shù)，。如果，則稱和互素。稱是兩個整數(shù)的最小公倍數(shù)，如果(1)是的倍數(shù)也是的倍數(shù)，即是的公倍數(shù)；(2)和的任一公倍數(shù)，也是的倍數(shù)。表示為。若是兩個互素的正整數(shù)，則。第四章公鑰密碼4.1.3模運算設是一正整數(shù)，是整數(shù)，如果用除，得商為，余數(shù)為，則其中為小于或等于的最大整數(shù)。用表示余數(shù)，則。如果，則稱兩整數(shù)和模同余，記為。稱與模同余的數(shù)的全體為的同余類，記為，稱為這個同余類的表示元素。第四章公鑰密碼注意：如果，則。同余有以下性質(zhì)：(1) 與等價。(2) ，則。(3) ，則。(4) ，，則。(5)如果，，則。(6)如果，，則。第四章公鑰密碼證明：(5)由及，得，。(6)由得，即是的公倍數(shù)，所以。從以上性質(zhì)易知，同余類中的每一元素都可作為這個同余類的表示元素。第四章公鑰密碼求余數(shù)運算（簡稱求余運算）將整數(shù)映射到集合，稱求余運算在這個集合上的算術(shù)運算為模運算，模運算有以下性質(zhì)：(1) 。(2) 。(3)。證(1)：

設，，則存在整數(shù)使得

，

。因此

(2)、(3)的證明類似。第四章公鑰密碼【例4-4】設，考慮上的模加法和模乘法，結(jié)果如下：表4-1模8運算第四章公鑰密碼從加法結(jié)果可見，對每一，都有一，使得

。如對2，有6，使得，稱為的負數(shù)，也稱為加法逆元。對，若有，使得，如，則稱為的倒數(shù)，也稱為乘法逆元。本例可見并非每一都有乘法逆元。一般，定義為小于的所有非負整數(shù)集合，即：

稱為模的同余類集合。第四章公鑰密碼其上的模運算有以下性質(zhì)：(1)交換律：

(2)結(jié)合律：

(3)分配律：(4)單位元：

(5)加法逆元：對，存在，使得，記。此外還有以下性質(zhì)：如果，則，稱為加法的可約律。第四章公鑰密碼該性質(zhì)可由的兩邊同加上的加法逆元得到。然而類似性質(zhì)對乘法卻不一定成立。

例如，，但。

原因是6乘0到7得到的8個數(shù)僅為的一部分，看上例。

如果將對作6的乘法（即用6乘中每一數(shù)）看作到的映射的話，中至少有兩個數(shù)映射到同一數(shù)，因此該映射為多到一的，所以對6來說，沒有唯一的乘法逆元。但對5來說，，因此5有乘法逆元5。

仔細觀察可見，與8互素的幾個數(shù)1，3，5，7都有乘法逆元。

記。第四章公鑰密碼定理4-1

中每一元素有乘法逆元。證明首先證明中任一元素與中任意兩個不同元素（不妨設）相乘，其結(jié)果必然不同。否則設，則存在兩個整數(shù)，使得，可得，所以是

的一個因子。又由，得是的一個因子，設，所以，即，與矛盾。所以。對中任一元素，由，得，，所以。第四章公鑰密碼由以上兩條得。因此對，存在，使得，即是的乘法逆元。記為。

（定理4-1證畢）證明中用到如下結(jié)論：設是2個集合，滿足且，則。設為一素數(shù)，則中每一非0元素都與互素，因此有乘法逆元。類似于加法可約律，可有以下乘法可約律：如果且有乘法逆元，那么對兩邊同乘以，即得。第四章公鑰密碼4.1.4模指數(shù)運算模指數(shù)運算是指對給定的正整數(shù)，計算?！纠?-5】，則易求出,,。由于,所以,,…,即從開始所求的冪出現(xiàn)循環(huán)，循環(huán)周期為3?？梢娫谀Ｖ笖?shù)運算中，若能找出循環(huán)周期，則會使得計算簡單。稱滿足方程的最小正整數(shù)為模下的階，記為。第四章公鑰密碼定理4-2設，則的充要條件是為的倍數(shù)。證明

設存在整數(shù)，使得，則。反之，假定，令其中，那么

與是階矛盾。（定理4-2證畢）第四章公鑰密碼4.1.5費爾馬定理、歐拉定理、卡米歇爾定理這三個定理在公鑰密碼體制中起著重要作用。1.費爾馬(Fermat)定理定理4-3(費爾馬定理)若是素數(shù)，是正整數(shù)且，則。證明在定理1-1的證明中知，當時,，其中表示與中每一元素做模乘法。又知，所以，。即分別將兩個集合中的元素連乘，得：

第四章公鑰密碼另一方面，

因此

由于與互素，因此有乘法逆元，由乘法可約律得。（定理4-3證畢）Fermat定理也可寫成如下形式：

設是素數(shù)，是任一正整數(shù)，則。第四章公鑰密碼2.歐拉函數(shù)設是一正整數(shù)，小于且與互素的正整數(shù)的個數(shù)稱為的歐拉函數(shù)，記為?！纠?-6】，，。

定理4-4(1)若是素數(shù)，則；(2)若是兩個素數(shù)和的乘積，則

；

(3)若有標準分解式，則

。第四章公鑰密碼（2）考慮，其中不與互素的數(shù)有三

類：

，，，且，否則如果，其中則是的因子，因此是的因子，設。則，與矛盾。所以證明

（1）顯然；第四章公鑰密碼(3)當時，之間與不互素的數(shù)有，共個，所以。當，由(2)得，

（定理4-4證畢）【例4-7】第四章公鑰密碼3.歐拉定理定理4-5（Euler定理）

若和互素，則。證明設是由小于且與互素的全體數(shù)構(gòu)成的集合，，考慮中任一元素，因與互素，與

互素，所以與互素，且，因此

，所以。第四章公鑰密碼所以得，所以，，，由每一與

互素，知與互素，在下有乘法逆元。所以。

（定理4-5證畢）又因中任意兩個元素都不相同，否則，由與互素知在下有乘法逆元，得。第四章公鑰密碼推論：。推論說明，一定是的因子。如果，則稱為的本原根。

如果是的本原根，則

在下互不相同且都與互素。特別地，如果是素數(shù)的本原根，則

在下都不相同?！纠?-8】，則，考慮2在下的冪

，，，，

。即，所以2為9的本原根。第四章公鑰密碼【例4-9】在mod19下的冪分別為3，9，8，5，15，7，2，6，18，16，10，11，14，4，12，17，13，1即，所以3為19的本原根。本原根不唯一。可驗證除3外，19的本原根還有2，10，13，14，15。注意并非所有的整數(shù)都有本原根，只有以下形式的整數(shù)才有本原根：

其中為奇素數(shù)。第四章公鑰密碼4.卡米歇爾定理對滿足的所有，使得同時成立的最小正整數(shù)，稱為的卡米歇爾（Carmichael）函數(shù)，記為?！纠?-10】n=8，與8互素的數(shù)有1,3,5,7，即。

所以。從該例看出，。第四章公鑰密碼定理4-6(1)如果，則；(2)對任意互素的正整數(shù)，有；(3) 第四章公鑰密碼證明對滿足的所有，，由得，

。設，其中，則

，所以，即。(2)由(1)得，，即是和的公倍數(shù)。又設是和的任一公倍數(shù)，由得，其中，所以，其中，。所以是和

的最小公倍數(shù)。(3)可由(2)得到。（定理4-6證畢）第四章公鑰密碼定理4-7（卡米歇爾定理）若和互素，則。證明設，下面證明。如果或奇素數(shù)的冪，由定理1-6(3)，，所以。

又因，所以。當時，，我們需要證明，對用歸納法。第四章公鑰密碼當時，對每一奇整數(shù)成立。設

對成立，即，是一正整數(shù)。則當時，

由歸納法，對任意成立。由，得，其中

，所以。（定理4-7證畢）第四章公鑰密碼4.1.6素性檢驗

素性檢驗是指對給定的數(shù)檢驗其是否為素數(shù)。1.愛拉托斯散(Eratosthenes)篩法定理4-8設是一正整數(shù)，如果對所有滿足的素數(shù)，都有，那么一定是素數(shù)?；谶@個定理，有一個尋找素數(shù)的算法，稱為愛拉托斯散(Eratosthenes)篩法。

要找不大于的所有素數(shù)，先將2到之間的整數(shù)都列出，從中刪除小于等于的所有素數(shù)（設滿足的素數(shù)有個）的倍數(shù)，余下的整數(shù)就是所要求的所有素數(shù)第四章公鑰密碼【例4-11】求不超過的所有素數(shù)。解：因為，小于10的素數(shù)有2、3、5、7，刪去

之間的整數(shù)中2的倍數(shù)（保留2）得：11121314151617181920212223242526272829302345678910313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100第四章公鑰密碼刪去3的倍數(shù)（保留3）得：2123252729123579

11131517193133353739414345474951535557596163656769717375777981838587899193959799刪去5的倍數(shù)（保留5）得：

1

2357111317192325293135374143474953555961656771737779837589918597第四章公鑰密碼刪去7的倍數(shù)（保留7）得：

1

2357111317192329313741434749

535961677173777983899197

此時，余下的數(shù)就是不超過100的所有素數(shù)。 愛拉托斯散篩法在判斷是否為素數(shù)時，要除以小于等于的所有素數(shù)，當很大時，實際上是不可行的。第四章公鑰密碼引理4-1如果為大于2的素數(shù)，則方程的解只有和。證明由，有，，因此或或且。若且，則存在兩個整數(shù)和，使得

，兩式相減得，為不可能結(jié)果。所以有或。設，則，因此。類似地可得。

（引理4-1證畢）第四章公鑰密碼2.Miller-Rabin概率檢測法【例4-12】

考慮方程由4.1.3節(jié)上模乘法的結(jié)果得,，,

又，，所以方程的解為1，-1，3，-3，可見8不是素數(shù)。引理4-1的逆否命題為：

如果方程有一解，那么不為素數(shù)。下面介紹Miller-Rabin的素性概率檢測法。

其核心部分如下：第四章公鑰密碼WITNESS(a，n)將n-1表示為二進制形式；

；

；

；

；

；.算法有兩個輸入，n是待檢驗的數(shù)，a是小于n的整數(shù)。如果算法的返回值為FALSE，則n肯定不是素數(shù)，如果返回值為TRUE，則n有可能是素數(shù)。第四章公鑰密碼for循環(huán)結(jié)束后，有，由Fermat定理知，若n為素數(shù)，則d為1。因此若，則n不為素數(shù)，所以返回FALSE。因為，所以意指有不在中的根，因此n不為素數(shù)，返回FALSE。該算法有以下性質(zhì)：對s個不同的a，重復調(diào)用這一算法，只要有一次算法返回為FALSE，就可肯定n不是素數(shù)。如果算法每次返回都為TRUE，則n是素數(shù)的概率至少為，因此對于足夠大的s，就可以非?？隙ǖ叵嘈舗為素數(shù)。第四章公鑰密碼3.AKS算法2002年，印度數(shù)學家ManindraAgrawal,NeerajKayal,NitinSaxena給出了一個確定性的素數(shù)判別算法，簡稱AKS算法。設N和I分別是自然數(shù)集合和整數(shù)集合，且，滿足

的最小正整數(shù)k稱為模n下a

的階，記為。第四章公鑰密碼算法基于以下引理：引理4-2

設是一自然數(shù)，，則n

是素數(shù)的充要條件是：

證明對，中的系數(shù)為。如果n是素數(shù)，則，所以的系數(shù)都為0。如果n

是合數(shù)，可設q是它的一個素數(shù)因子且，則不能除盡，而且和互素，所以在模n下，的系數(shù)不為0，。（引理4-2證畢）第四章公鑰密碼引理4-2給出了一個素數(shù)檢驗的簡單方法，然而要驗證等式是否成立，需計算n

個系數(shù)。

為了減少系數(shù)的計算，可在等式的兩邊同時對一個形如的多項式取模（其中r是一個適當選擇的小整數(shù)），即將判斷等式是否成立，改為判斷

是否成立。表示在環(huán)上，。第四章公鑰密碼算法如下：

輸入整數(shù)n，

1.如果，輸出“合數(shù)”；

2.求滿足的最小的r；

3.如果存在a

，滿足且，輸出“合數(shù)”；

4.如果，輸出“素數(shù)”；5.

如果，輸出“合數(shù)”；

6.輸出“素數(shù)”。第四章公鑰密碼4.1.7歐幾里得算法

歐幾里得（Euclid）算法是數(shù)論中的一個基本技術(shù)，是求兩個正整數(shù)的最大公因子的簡化過程。

而推廣的Euclid算法不僅可求兩個正整數(shù)的最大公因子，而且當兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的乘法逆元。1.求最大公因子Euclid算法是基于下面一個基本結(jié)論：設是任意兩個正整數(shù)，將它們的最大公因子簡記為。有以下重要結(jié)論

第四章公鑰密碼證明：是正整數(shù)，因此可將表示為其中為一整數(shù)，所以。設是的公因子，即，所以。由

和

得，因此是和的公因子。所以得出的公因子集合與的公因子集合相等，兩個集合的最大值也相等，得證。在求兩個數(shù)的最大公因子時，可重復使用以上結(jié)論。第四章公鑰密碼【例4-13】(55,22)=(22,55mod22)=(22,11)=(11,0)=11?！纠?-14】(18,12)=(12,6)=(6,0)=6,(11,10)=(10,1)=1。Euclid算法如下：設是任意兩個正整數(shù),記反復用上述除法（稱為輾轉(zhuǎn)相除法），有:

第四章公鑰密碼因，因此可假定算法的輸入是兩個正整數(shù)，并設。EUCLID1.Xa;Yb；2.ifY=0thenreturnX=(a,b)；3.ifY=1thenreturnY=(a,b)；4.R=XmodY；5.X=Y；6.Y=R；7.goto2.由于，經(jīng)過有限步后，必然存在使得?？傻?，即輾轉(zhuǎn)相除法中最后一個非0余數(shù)就是和的最大公因子。這是因為。第四章公鑰密碼【例4-15】求(1970,1066)。1970=11066+904, (1066,904)1066=1904+162, (904,162)904=5162+94, (162,94) 162=194+68, (94,68) 94=168+26, (68,26)68=226+16, (26,16) 26=116+10, (16,10) 16=110+6, (10,6) 10=16+4, (6,4)6=14+2, (4,2) 4=22+0, (2,0)因此(1970,1066)=2。第四章公鑰密碼在輾轉(zhuǎn)相除法中，有依次將后一項帶入前一項，可得由的線性組合表示。

因此有如下結(jié)論：

存在整數(shù)，使得，即兩個數(shù)的最大公因子能由這兩個數(shù)的線性組合表示。第四章公鑰密碼2.求乘法逆元如果，則b在下有乘法逆元（不妨設），即存在一，使得。推廣的Euclid算法先求出，當時，則返回的逆元。EXTENDEDEUCLID（設）

1.;;2.ifthenreturn；noinverse;3.ifthenreturn；;4. 5. ;6. ;7. ;8.goto2第四章公鑰密碼算法中的變量有以下關(guān)系：;;這一關(guān)系可用歸納法證明：設前一輪的變量為

、、滿足

;;則這一輪的變量、、和前一輪的變量有如下關(guān)系：

所以

第四章公鑰密碼在算法EUCLID中，等于前一輪循環(huán)中的，等于前一輪循環(huán)中的。

而在算法EXTENDEDEUCLID中，等于前一輪循環(huán)中的，等于前一輪循環(huán)中的，由于是除

的商，因此是前一輪循環(huán)中的除的余數(shù)，即

，可見EXTENDEDEUCLID中的、與EUCLID中的、作用相同，因此可正確產(chǎn)生。如果，則在倒數(shù)第二輪循環(huán)中。由可得，，，，所以。第四章公鑰密碼【例4-16】求(1769,550)，算法的運行結(jié)果及各變量的變化情況如表4-2所示：表4-2求(1769,550)時推廣Euclid算法的運行結(jié)果循環(huán)次數(shù)

初值-1017690155013015501-3119241-3119-4137431-413745-1645415-1645-9292951-9292914-45166114-4516-23741371-23741337-11938437-1193-1715501所以(1769，550)=1，。第四章公鑰密碼4.1.8中國剩余定理

中國剩余定理是數(shù)論中最有用的一個工具，它有兩個用途:一是如果已知某個數(shù)關(guān)于一些兩兩互素的數(shù)的同余類集，

就可重構(gòu)這個數(shù)。二是可將大數(shù)用小數(shù)表示、大數(shù)的運算通過小數(shù)實現(xiàn)?！纠?-17】中每個數(shù)都可從這個數(shù)關(guān)于2和5（10的兩個互素的因子）的同余類重構(gòu)。

比如已知關(guān)于2和5的同余類分別是[0]和[3]，即。可知是偶數(shù)且被5除后余數(shù)是3，所以可得8是滿足這一關(guān)系的唯一的。第四章公鑰密碼【例4-18】

假設只能處理5以內(nèi)的數(shù)，則要考慮15以內(nèi)的數(shù)，可將15分解為兩個小素數(shù)的乘積，,將1到15之間的數(shù)列表表示，表的行號為0~2，列號為0~4，將1到15的數(shù)填入表中，使得其所在行號為該數(shù)除3得到的余數(shù),列號為該數(shù)除5得到的余數(shù)。如，所以12應填在第0行，第2列。表4-31到15之間的數(shù)

0123400612391101713425112814第四章公鑰密碼現(xiàn)在就可處理15以內(nèi)的數(shù)了。例如求，因12和13所在的行號分別是0和1，12和13所在的列號分別是2和3，由得所在的列號和行號分別為0和1，這個位置上的數(shù)是6，所以得。

又因，第1行、第0列為10，所以。以上兩例是中國剩余定理的直觀應用,下面具體介紹定理的內(nèi)容。第四章公鑰密碼中國剩余定理最早見于《孫子算經(jīng)》的“物不知數(shù)”問題：今有物不知其數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有多少？這一問題用方程組表示為：下面給出解的構(gòu)造過程。首先將三個余數(shù)寫成和式的形式為滿足第一個方程，即模3后，后2項消失，給后2項各乘以3，得：第四章公鑰密碼

為滿足第二個方程，即模5后，第一、三項消失，給第一、三項各乘以5，得：同理給前2項各乘以7，得：然而，將結(jié)果帶入第一方程，得到，為消去，將結(jié)果的第一項再乘以，得。類似地，將第二項乘以，第三項乘以，得結(jié)果為第四章公鑰密碼又因為（k為任一整數(shù)）都滿足方程組，可取，得到小于的唯一解23，所以方程組的唯一解構(gòu)造如下：把這種構(gòu)造法推廣到一般形式，就是如下的中國剩余定理。第四章公鑰密碼定理4-9（中國剩余定理）設是兩兩互素的正整數(shù)，，則一次同余方程組對模有唯一解:其中滿足第四章公鑰密碼證明設，，由的定義得與是互素的，可知在模下有唯一的乘法逆元，即滿足的是唯一的。下面證明對，上述滿足。注意到當時，，即。所以而

所以,即。第四章公鑰密碼下面證明方程組的解是唯一的。

設是方程組的另一解，即

由得，即。再根據(jù)兩兩互素，有，即，所以。（定理4-9證畢）中國剩余定理提供了一個非常有用的特性，即在模（）下可將大數(shù)由一組小數(shù)表達，且大數(shù)的運算可通過小數(shù)實現(xiàn)。表示為：

其中，則有以下推論：第四章公鑰密碼推論：如果，那么

證明可由模運算的性質(zhì)直接得出?！纠?-18續(xù)】表4-3的構(gòu)造：設，求，將填入表的行、列。表建立完成后，數(shù)可由它的行號和列號，按中國剩余定理如下恢復：第四章公鑰密碼例如，。所以12位于表中第0行、第2列，13位于表中第1行、第3列。反之若求表中第0行、第2列的數(shù)，將帶入

，得。已知數(shù)的行號和列號，可將表示為。

的運算用實現(xiàn)。設，則

。例如12=(0,2),13=(1,3),12+13=(0,2)+(1,3)=(1,0),12·13=(0,2)·(1,3)=(0,1),所以12+13為10，12·13為6。第四章公鑰密碼【例4-19】由以下方程組求