導讀
數論是一門研究自然數之間的關系和規律的學科，普遍認為是純數學的分支，但并非是完全沒有實用性的學科。現代密碼學中用到了很多基礎數論中的結論，特别是公鑰加密體系（例如RSA算法，橢圓曲線加密等）。
本文目的在于梳理現代密碼學中常用到的基礎數論方面的定理和結論。其中包括素數的特性、歐幾裡德算法、線性方程定理、算術基本定理、模算數運算、線性同餘定理、歐拉函數、費馬小定理、中國剩餘定理、歐拉定理、本原根、離散對數問題等等一些基礎知識。了解這些知識，應該能夠了解現代密碼學中經典的
Diffie-Hellman密鑰協商和RSA算法的原理，進而能夠了解秘鑰管理、數字簽名、消息認證、公鑰證書等密碼學領域的問題。
本文很大程度上參考了數論概述裡面的内容，也借鑒了算法導論和密碼編碼學與網絡安全原理與實踐的相關章節。
一、關于互質和整除的一些有用結論和定理
數論對素數的特性尤其感興趣，素數是整數的基礎構件，就像是元素在化學式中的作用類似。
1、$d$整除$a$記作：$d \mid a$
如果$d \mid a$且$d \mid b$，那麼$d \mid (ax + by)$.
2、如果$p$是素數，且$p$整除乘積$ab$，則$p$整除$a$或者$p$整除$b$（或者$p$同時整除$a$和$b$）。
證明的關鍵是假設$p$不整除$a$，考慮$1=gcd(p,a)$同時整除$p$和$a$。但由于$p$是素數，$p$的因子隻能是1或者$p$，是以$gcd(p,a)=1$。由後面的線性方程定理得知，可以構造線性方程$px+ay=1=gcd(p,a)$，兩邊同時乘上$b$，得$bpx+aby=b$，$p$整除左邊等價于$p$整除右邊的$b$。$p$不整除$b$的情況可以用同樣的方式證明。
拓展：如果素數$p$整除整數乘積$a_{1}a_{2}a_{3}...a_{r}$,則p至少整除$a_{1}$,$a_{2}$,$a_{2}$,$...$,$a_{r}$中至少一個因數。
3、1和任意一個自然數是都是互質關系。
4、任意兩個質數構成互質關系。
5、一個數是質數，另一個數隻要不是前者的倍數，兩者就構成互質關系，比如3和10。
6、如果兩個數之中，較大的那個數是質數，則兩者構成互質關系，比如97和57。
7、 $p$是大于1的整數，則$p$和$p-1$構成互質關系，比如57和56。
8、$p$是大于1的奇數，則$p$和$p-2$構成互質關系，比如17和15。
9、素數$p$與1到$p-1$的任意整數均互質。并且階乘$(p-1)!$與$p$互質，這個結論在後面費馬小定理和歐拉定理的證明過程中會用到。
二、歐幾裡德算法
歐幾裡德算法的原理和流程其實比較容易了解。
(GCD遞歸定理) ：對于任意的非負整數$a$和正整數$b$，滿足
$gcd(a,b)=gcd(b,a\;mod\;b)$
更詳細的将，其計算流程：
$a=q_{1}\times b+r_{1}\\b=q_{2}\times r_{1}+r_{2}\\r_{1}=q_{3}\times r_{2}+r_{3}\\r_{2}=q_{4}\times r_{3}+r_{4}\\...\\r_{n-3}=q_{n-1}\times r_{n-2}+r_{n-1}\\r_{n-2}=q_{n}\times r_{n-1}+r_{n}\\r_{n-1}=q_{n+1}\times r_{n}+0\\$
$r_{n}$即為求得的$a$和$b$的最大公約數。
以上流程主要需要思考三個問題：
1）為什麼$r_{n}$是公約數？（需要從下往上推理）
2）為什麼$r_{n}$是最大的公約數？（假設$d$是$a$與$b$的任意公約數，如果能夠證明$d$整數$r_{n}$，即可得證。）
3）為什麼歐幾裡德算法最後一定會終止？（因為每輪輾轉之後的餘數是單調遞減的，輾轉的輪次數有上界，最後一定能夠保證餘數為0，然後取最後一個非零餘數$r_{n}$就是正确的結果。）
算法實作Demo：
//歐幾裡德算法疊代實作
public static int getGCD(int a,int b) {
if (a<b) {//保證a>=b
return getGCD(b, a);
}
if (b>=1) {//保證b>=1
int temp = 0;
while(b>0) {
temp = a%b;
a = b;
b = temp;
}
return a;
}else {
return -1;
}
} 三、擴充歐幾裡德算法
擴充歐幾裡德算法可以用來求解一類有意思的線性方程的整數解，該線性方程的整數求解過程與最大公約數有密切關系。
對于線性方程（$a,b,c$為常數）：
$ax+by=c$
是很熟悉的方程。這裡讨論情況是$a,b,c$滿足一定的關系：$c=gcd(a,b)$，也即是這樣的線性方程：
$ax+by=gcd(a,b)$
這個線性方程必然有整數解，但我們更關心如果用更好算法去求解，該算法利用歐幾裡德算法求解最大公約數過程中的中間商和餘數，進行擴充運算，在求$gcd(a,b)$的過程中，同時也就求得線性方程的整數解$(x,y)$。
算法實作Demo：
public static long[] gcdExt(long a,long b){
long ans;
long[] result=new long[3];
if(b==0)
{
result[0]=a;
result[1]=1;
result[2]=0;
return result;
}
long [] temp=gcdExt(b,a%b);
ans = temp[0];
result[0]=ans;
result[1]=temp[2];
result[2]=temp[1]-(a/b)*temp[2];
return result;
} 四、算術基本定理
(算術基本定理)：每個整數$n\geqslant 2$可唯一分解成素數的乘積：
$n=p_{1}^{e_{1}}p_{2}^{e_{2}}...p_{r}^{e_{r}}$
其中，$p_{i}$為素數，且$p_{1}<p_{2} <...<p_{r}$，$e_{i}$為正整數。
實際上，看似理所當然的事實，其實并非如此。如果自定義一個有别正整數集合的其他集合，很可能就不再滿足唯一分解定理。例如，集合E是由偶數構成的集合：
$E=\left \{0,2,4,6,8,10,12...\right \}$
也可在這個集合中定義所謂的“素數”，稱之為“E-素數”，2,6,10,14,18,22,26,30都是“E-素數”。對這個集合中的元素嘗試做“素因子”分解，并不總是能都到唯一分解的結果，例如180=10x18=2x30，存在兩種“E-素數”的分解形式。
實際上算術基本定理包含兩個方面：
1）$n$可以分解成素數乘積的形式。
2）僅有一種這樣的素因子分解的形式（當然這裡不考慮因數重排序的情況）。
顯然唯一性分解是算術基本定理的關鍵和重點。
另外一個有意思的事實：
如果$n$是一個合數，則在小于等于$\sqrt{n}$的數中必定有一個數$a$整除合數$n$。
該結論基于算術基本定理：合數$n$必定可以唯一分解多個素數的乘積，這裡假設$p$是它的素因子中最小的一個，則$n$必定可以寫成$n=p\times m$的形式，這裡的$m$是其餘大于等于$p$的素因子的乘積，顯然$m\geqslant p$,是以$n=p\times m\geqslant p\times p=p^{2}$
是以，在$0...\sqrt{n}$的範圍内，必定存在一個數$a$整除$n$。
可以利用這種方法簡單的分辨一個數是否是素數，也可以反複執行上述過程将一個較小的合數進行素因子分解。
五、 同餘式與模算術
一般來講，可以将$mod$視為一種求餘數的二進制運算符，例如$2=5\;mod\;3$；也可以用來表示同餘關系，這種同餘關系通常用同餘式表示。例如$2\equiv 5\;(mod\;3)$表示模3時2與5同餘。
同餘式雖然有别于普通的算數運算下的等式，但是具有相同模的同餘式與普通等式有一些相似的特性：
如果已知：
$a_{1}\equiv b_{1}\;(mod\;m)$ 且$a_{2}\equiv b_{2}\;(mod\;m)$
那麼有：
$a_{2}\pm a_{2}\equiv b_{2}\pm b_{2}\;(mod\;m)$和$a_{2}a_{2}\equiv b_{2}b_{2}\;(mod\;m)$
同時，也不難得出：
如果，$a^{k}\equiv b\;(mod\;m)$，那麼，$(a^{k})^j\equiv b^{j}\;(mod\;m)$
特别的當$b=1$時：
如果$a^{k}\equiv 1\;(mod\;m)$，那麼，$(a^{k})^{j}\equiv 1\;(mod\;m)$。
但是，由$ac\equiv bc\;(mod\;m)$不一定能得到$a\equiv b\;(mod\;m)$。
例如$2\times25\equiv2\times20\;(mod\;10) $，但是$25\not\equiv 20\;(mod\;10)$。
隻有當$c$和$m$互質時（也即是$gcd=(c,m)=1$），才能夠從同餘式兩邊消去$c$。
由同餘式可以引出同餘方程：
$ax\equiv c\;(mod\;m)$
求解上述同餘方程有一個定理，叫做同餘方程定理。
(同餘方程定理)：設$a,c,m$是整數，$m\geqslant 1$，且設$g=gcd(a,m)$，則
1）如果$g$不整除$c$，那麼同餘方程$ax\equiv c\;(mod\;m)$沒有解。
2）如果$g$整除$c$，那麼同餘方程$ax\equiv c\;(mod\;m)$恰好有$g$個解。
以上同餘方程的求解過程需要用到擴充歐幾裡德的求解方法。實際上$ax\equiv c\;(mod\;m)$可以轉化為線性方程$ax+m(-y)=c$。
特别地，當$a$和$m$互質，即$g=gcd(a,m)=1$時，同餘方程變成：
$ax\equiv 1\;(mod\;m)$
$a$和$x$互為模反元素，這在RSA公鑰加密算法生成秘鑰過程中有應用。
六、費馬小定理
費馬小定理揭示了整數的幂在模運算下的特殊規律。
(費馬小定理)：設$p$是素數，$a$是任意的正整數且滿足$a\not\equiv0\;(mod\;p)$，則
$a^{p-1}\equiv 1 \;(mod\;p)$
實際上對于條件的更簡單的表述可以為"$a$與素數$p$互質"即可。
證明費馬小定理并不是非常難，證明過程是基于這樣一個結論：
設素數$p$與任意正整數$a$互質，那麼集合$S=\left \{ a,2a,3a,...(p-1)a \right \}$中任意任意兩個元素均不可能模$p$同餘。也即是$ja\not\equiv ka\;(mod\;p)$。其證明過程隻需要利用反證法即可。
上述結論表明，如果對集合$S$中的每一個元素模$p$的結果，其結果剛好與集合$T= \left \{ 1,2,3,4...(p-1) \right \}$中的元素一一對應（不考慮次序重排）。
于是有：
$a\times 2a\times3a...\times(p-1)a\equiv 1\times2\times3...\times(p-1)\;(mod\;p)$
稍微整理得：
$(p-1)!\times a^{p-1}\equiv(p-1)!\;(mod\;p)$
這裡必然後$gcd((p-1)!,p)=1$，是以，可以兩邊消去$(p-1)!$，得到$a^{p-1}\equiv 1 \;(mod\;p)$。
正是由于存在這樣的關系，所有費馬小定理可以用來簡化對整數的幂取模的計算。
費馬小定理在數論中非常重要，與其三個定理（分别是威爾遜定理、歐拉定理和中國剩餘定理）合稱數論四大基本定理。更有趣的是，費馬小定理實際上可以視為歐拉定理的一個特例。
最後，費馬小定理還有一種等價的表示形式：
若$p$是素數，$a$是正整數，則
$a^{p-1}\equiv a\;(mod\;p)$
這裡不需要$a$與$p$互質的條件。這并不是一件很奇怪的事情，無非是利用模算術的除法特性（見同餘式與模算術）的變形。
七、中國剩餘定理
中國剩餘定理（也叫作孫子定理）所描述的問題在國小課本中都能找到，隻不過當時隻能用方程組去刻畫這個的問題。
在數論中，它有不止一種表述形式，我見到的就至少有兩種。
其中一種比較易懂的描述為：
設$m,n$是正整數，$gcd(m,n)=1$，$b,c$是任意正整數，則同餘方程組
$x\equiv b\;(mod\;m)\\x\equiv c\;(mod\;n)$
恰有一個解$0\leqslant x\leqslant mn$。
以上是從方程的角度描述，另外一種從對應的角度(數與k元組的對應關系)表述也是可行的，可以看做是上面表述形式更抽象的擴充：
令
$M=\prod_{i=1}^{k}m_{i}$，其中$m_{i}$兩兩互質
則$Z_{M}=\left \{ 0,1,2,3...(m-1)\right \}$中任意整數會對應一個$k$元組：
$A\leftrightarrow (a_{1},a_{2}...,a_{k})$
其中$a_{i}$當然是要在$Z_{m_{i}}$中(也即是$a_{i}\in Z_{m_{i}}$)，并且$a_{i}$由關系$a_{i}=A\;mod\;m_{i}$給出。
從以上定理實際上可以推斷出$A$與$k$元組唯一一對應的事實。
以上描述形式是算法導論和密碼編碼學與網絡安全--原理與實踐中采用的表述形式。相比于第一種表述形式，第二種表述更具有通用性，也更抽象。中國剩餘在推導歐拉函數求解公式時會用到。
八、歐拉函數
歐拉函數$\phi (m)$的含義是1到$m-1$中（也就是$\left [ 1,m-1 \right ]$）且與$m$互質的整數的個數。它是數論中一個非常重要的函數。
如何計算歐拉函數的值是一個關鍵的問題。歐拉函數的計算方法的推導主要用到兩個結論：
（1）如果$p$是素數，$k\geqslant 1$，則$\phi (p^{k})=p^k-p^{k-1}=p^k(1-\frac{1}{p})$
（2）如果$gcd(m,n)=1$，則$\phi (mn)=\phi (m)\times \phi (n)$
證明（1）的思路很簡單：從1到$p^{k}$共有$p^{k}$個整數，這些整數中當然有可能存在與$p^{k}$不互質的數，那麼隻要扣除去這些數就可以了。顯而易見的是，這些與$p^{k}$不互質的數并不難找，它們分别是：
$p,2p,3p,...,(p^{k-1}-2)\times p,(p^{k-1}-1)\times p,p^{k-1}\times p$
一共有$p^{k-1}$個數與$p^{k}$不互質，那麼從$p^{k}$中扣除這$p^{k-1}$個數即可。
證明（2）比較複雜一點，其思路是采用計數的思想然後結合中國剩餘定理（第一種表述形式）來證明。
有了以上兩個結論，結合算術基本定理，可以得到計算$\phi (m)$比較通用的公式：
假設任意正整數$m$，且其素因子分解形式為
$m=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}$
利用上面的（2）可以得到
$\phi (m)=\phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})...\phi (p_{r}^{k_{r}})$
然後利用（1），繼續得到
$\phi (m)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})$
也就是
$\phi (m)=m(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})$
例如
$\phi (12)=\phi (2^{2}\times 3)=\phi (2^{2})\times \phi (3)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=4$
另外，歐拉函數與各因數之間存在一種巧妙的關系：
設$d_{1},d_{2},...,d_{r}$是$n$的因數，則
$\phi (d_{1})+\phi (d_{2})+...+\phi (d_{r})=\phi (n)$
其實當$n=p$或者$n=p^{2}$甚至$n=p^{k}$（$p$是素數）時，很容易驗證其正确性。
九、歐拉定理
歐拉定理與費馬小定理同樣都是揭示了整數的幂在模運算下的特殊規律，實際上他們有微妙的關系。
(歐拉定理)：如果$gcd(a,m)=1$，則
$a^{\phi (m)}\equiv 1\;(mod\;m)$
實際上證明歐拉定理的方法與證明費馬小定理基本類似，此處略去。
歐拉定理與費馬小定理有微妙的關系：如果這裡的$m$是一個素數，則$\phi (m)=m-1$，由此得到費馬小定理。說明費馬小定理實際上可以看成歐拉定理的一個特例。
與費馬小定理類似，歐拉定理也有另外一種表現形式：
$a^{\phi (m)+1}\equiv a\;(mod\;m)$
這裡沒有要求$a$與$m$互質的條件。
十、模反元素
如果兩個正整數$a$和$m$互質，那麼一定可以找到整數$b$，使得 $ab-1$ 被$m$整除，或者說$ab$被$m$除的餘數是1。
$ab\equiv1\;(mod\;m)$
則此時$b$就是$a$的模反元素。
實際上這裡相當于求解同餘方程$ax\equiv 1\;(mod\;m)$，當$gcd(a,m)=1$時，必定存在一個整數解，是以模反元素必定存在，此解即是$a$的模反元素。
從歐拉定理的角度
$a^{\phi (m)}=a\times a^{\phi (m)-1}\equiv 1\;(mod\;m)$
也可以證明模反元素是存在的。
更進一步，如果$p$是素數，由集合$Z_{p}=\left \{ 0,1,2,...p-1 \right \}$和二進制運算模$p$的算術運算構成一個有限交換群G。G中每一個元素都有乘法逆元，此乘法逆元就是這裡的模反元素。
十一、本原根
本原根通常與幂模有關，觀察如下例子：
$3^{1}\;mod\;7=3\\3^{2}\;mod\;7=2\\3^{3}\;mod\;7=6\\3^{4}\;mod\;7=4\\3^{5}\;mod\;7=5\\3^{6}\;mod\;7=1\\...$
可以發現3的各幂次模$n$能夠得到一個循環的序列$\left \{ 3,2,6,4,5,1 \right \}$，這個序列剛好對應着小于等于7且與7互質的整數集合。這并非一個偶然規律，2或者3的各次幂模5，2或者6或者7或者8的各次幂模11都能夠得到同樣的規律。
當然也并不是總是這樣，例如
$2^{1}\;mod\;7=2\\2^{2}\;mod\;7=4\\2^{3}\;mod\;7=1\\2^{4}\;mod\;7=2\\...$
更一般的，考慮$p$為素數，$gcd(a,p)=1$且$a\leqslant p-1$，如下序列
$a\;mod\;p,a^{2}\;mod\;p,a^{3}\;mod\;p,...,a^{p-3}\;mod\;p,a^{p-2}\;mod\;p,a^{p-1}\;mod\;p$
如果$a^{p-1}\;mod\;p=1$，那麼可以證明上述序列值必然各不相同（證明可以用反證法，不存在$a^{i}\equiv a^{j}\;(mod\;p)$的情況）。因為這裡模$p$運算的結果總會映射到集合$Z_{p}=\left \{ 1,2,3,...,p-2,p-1 \right \}$，這個集合中的每個元素與$p$互質。也即是說不考慮次序重排，上述序列值對應了集合$Z_{p}$的值。
這時稱$a$是$p$的本原根或者生成元。
并非所有的整數都存在本原根，事實上隻有$1,4,p^{\alpha},2p^{\alpha}$才有本原根，其中$p$是任意奇素數，可見素數一定存在本原根。
(原根定理)：每個素數$p$都有本原根，而且剛好有$\phi (p-1)$個模$p$的本原根。
另外還有一些值得挖掘的規律，不難發現，對于$a^{k}\equiv1\;(mod\;p)$，這樣的$k$可能不止一個，比如：
$2^{3}\equiv 1\;(mod\;p)\\2^{6}\equiv 1\;(mod\;p)$
取最小的$k$稱為$a$模$p$的階：$ord_{p}(a)$，例如$ord_{7}(2)=3$。
不難發現，$1\leqslant ord_{p}(a)\leqslant p-1$且總是整除$p-1$（從費馬小定理的角度思考可以容易得出結論）。
十二、離散對數問題
離散對數的問題很好了解，與算術對數相對，隻是在算術對數的基礎上增加了模運算。
對于$y=g^{x}\;mod\;p$，如果已知$x,g,p$求$y$是比較容易的求解的；但是反過來，已知$y,g,p$求$x$是很困難的，是以這裡可以看成一個單向函數。
Diffie-Hellman密鑰協商原理正是基于這樣的離散對數問題而設計。而橢圓曲線加密是基于定義在橢圓曲線上的特殊加法運算規則下的離散對數問題而設計，兩者達到的目的是一緻的，都是利用某一個方向上的計算困難程度保證加密算法的機密性。
十三、References
1、數論概述
2、算法導論.第三一章.數論算法
3、密碼編碼學與網絡安全原理與實踐
完！
轉載請注明原文出處：http://www.cnblogs.com/qcblog/p/8976017.html
![BWT (Burrows–Wheeler_transform) 解碼分析[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)