密碼學概論密碼學的數(shù)學基礎（四）★本講授課提綱★（1）中國剩余定理（2）費馬小定理（3）歐拉定理★本講授課提綱★（1）中國剩余定理（2）費馬小定理（3）歐拉定理★中國剩余定理★中國剩余定理的發(fā)現(xiàn)和發(fā)展韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝建立了卓絕的功勞。據(jù)說韓信的數(shù)學水平也非常高超，他在點兵的時候，為了保住軍事機密，不讓敵人知道自己部隊的實力，先令士兵從1至3報數(shù)，然后記下最后一個士兵所報之數(shù)；再令士兵從１至５報數(shù)，也記下最后一個士兵所報之數(shù)；最后令士兵從1至7報數(shù)，又記下最后一個士兵所報之數(shù)；這樣，他很快就算出了自己部隊士兵的總人數(shù)，而敵人則始終無法弄清他的部隊究竟有多少名士兵。★中國剩余定理★中國剩余定理的發(fā)現(xiàn)和發(fā)展這個故事中所說的韓信點兵的計算方法，就是現(xiàn)在被稱為“中國剩余定理”的一次同余式解法。它是中國古代數(shù)學家的一項重大創(chuàng)造，在世界數(shù)學史上具有重要的地位。

最早提出并記敘這個數(shù)學問題的，是南北朝時期的數(shù)學著作《孫子算經》中的“物不知數(shù)”題目?！镏袊Ｓ喽ɡ怼镏袊Ｓ喽ɡ淼陌l(fā)現(xiàn)和發(fā)展“物不知數(shù)”題目是這樣的：

“今有物不知其數(shù)：三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”這個問題一般稱孫子問題?！敖裼幸恍┪锊恢鋽?shù)量。如果三個三個地去數(shù)它，則最后還剩二個；如果五個五個地去數(shù)它，則最后還剩三個；如果七個七個地去數(shù)它，則最后也剩二個。問：這些物一共有多少？”★中國剩余定理★中國剩余定理的發(fā)現(xiàn)和發(fā)展

《孫子算經》中記載了這個問題的解法，有人將其解法編成歌訣：“三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五便得知?！彼囊馑际怯?除的剩余數(shù)乘70，用5除的剩余數(shù)乘21，用7除的剩余數(shù)乘15，將所得的結果相加再減去105的倍數(shù)，即可得所求數(shù)。算式是2×70＋3×21＋2×15=233，233－105×2＝23，所以，最小的正整數(shù)解是23?！镏袊Ｓ喽ɡ怼镏袊Ｓ喽ɡ淼陌l(fā)現(xiàn)和發(fā)展

《孫子算經》實際上是對下面的同余方程組總結出一套經驗的解法。x≡a1(mod3)x≡a2(mod5)x≡a3(mod7)經驗公式：x=70a1+21a2+15a3-105k★中國剩余定理★中國剩余定理的發(fā)現(xiàn)和發(fā)展

《孫子算經》的“物不知數(shù)”題雖然開創(chuàng)了一次同余式研究的先河，但由于題目比較簡單，甚至用試猜的方法也能求得，所以尚沒有上升到一套完整的計算程序和理論的高度。真正從完整的計算程序和理論上解決這個問題的，是南宋時期的數(shù)學家秦九韶。秦

九韶在他的《算術九章》中提出了一個數(shù)學方法“大衍求一術”，系統(tǒng)地論述了一次同余式組解法的基本原理和一般程序?！镏袊Ｓ喽ɡ怼镏袊Ｓ喽ɡ淼陌l(fā)現(xiàn)和發(fā)展秦九韶為什么要把他的這一套計算程序和基本原理稱為“大衍求一術”呢？這是因為其計算程序的核心問題是要“求一”。所謂“求一”，通俗地說，就是求“一個數(shù)的多少倍除另一個數(shù)，所得的余數(shù)為一”。那么為什么要“求一”呢？★中國剩余定理★中國剩余定理的發(fā)現(xiàn)和發(fā)展我們可以從“物不知數(shù)”題的幾個關鍵數(shù)字７０、２１、１５中找到如下的規(guī)律：70是5和7的倍數(shù)，但被3除余1；21是3和7的倍數(shù)，但被5除余1；15是3和5的倍數(shù)，但被7除余1；任何一個一次同余式組，只要根據(jù)這個規(guī)律求出那幾個關鍵數(shù)字，那么這個一次同余式組就不難解出★中國剩余定理★中國剩余定理的完整正式版設是兩兩互素的正整數(shù)，則一次同余方程組對模M有唯一解其中ei滿足★中國剩余定理★中國剩余定理的用途中國剩余定理是數(shù)論中最有用的一個工具，定理說如果已知某個數(shù)關于一些兩兩互素的數(shù)的同余方程，就可以重構這個數(shù)。換句話說，中國剩余定理可以用于求解同余方程組。同時中國剩余定理提供了一個非常有用的特性，即在模M下可將非常大的整數(shù)x由一組兩兩互素的小整數(shù)來表達?！镏袊Ｓ喽ɡ怼镏袊Ｓ喽ɡ淼膽谩笸喾匠探M舉例：已知下面的同余方程組，求x★中國剩余定理★中國剩余定理的應用——求同余方程組第一步：求MM=2×3×5×7＝210第二步：求M1=105,M2=70,M3=42,M4=30★中國剩余定理★中國剩余定理的應用——求同余方程組第三步：求eiei滿足即ei是在模mi條件下的乘法逆元素使用觀察法求得乘法逆元素如下e1=1,e2=1,e3=3,e4=4★中國剩余定理★中國剩余定理的應用——求同余方程組第四步：★練習★1.求解下面的同余方程組X≡1(mod2)X≡2(mod3)x≡1(mod5)x≡2(mod7)★本講授課提綱★（1）中國剩余定理（2）費馬小定理（3）歐拉定理★費馬定理★費馬定理如果p是素數(shù)，a是正整數(shù)，且gcd(a,p)=1，那么ap-1≡1(modp)費馬定理的另一種形式如果p是素數(shù)，a是任意正整數(shù)，則對gcd(a,p)=1，有ap≡a(modp)★費馬定理★費馬定理的主要用途——快速尋找素數(shù)通常情況下，如果2n-1≡1(modn)，那么n為素數(shù)。之所以是“通常情況下”，是因為有例外例如2560≡1(mod561)，但561=3×11×17

但這種“例外”并不多見。例：a=7,p=19,求ap-1

modp★費馬定理★費馬定理的主要用途——快速尋找素數(shù)模的以2為底的冪運算有很快的迭代算法，加之滿足2n-1≡1(modn)的n為素數(shù)的可能性較大，那么就可以以此為基礎設計尋找素數(shù)的算法。選擇初始的n0，然后依次檢驗接下來的奇數(shù)n>n0，看是否滿足2n-1≡1(modn)，如果滿足，則采用復雜的素數(shù)判定算法做進一步的檢驗。這種算法比因數(shù)分解法快得多。★本講授課提綱★（1）中國剩余定理（2）費馬小定理（3）歐拉定理★歐拉定理★歐拉函數(shù)歐拉函數(shù)φ(m)表示比m小且與m互素的正整數(shù)的個數(shù)。以m=24為例，比24小而與24互素的正整數(shù)為1,5,7,11,13,17,19,23。因此，φ(24)=8。★歐拉定理★歐拉函數(shù)的性質（1）m是素數(shù)時，有φ(m)=m-1因為與m互素的數(shù)有1,2,…,m-1共m-1個。（2）m=pq，且p和q均是素數(shù)時，有φ(m)=φ(p)φ(q)=(p-1)(q-1)（3）若m和n互素，則φ(m×n)=φ(m)×φ(n)（4）若p是一個素數(shù)，則φ(pe)=pe-pe-1