前言
質數的觀念雖然起源於人類有自然數的觀念不久後，但是直到近代尋找大質數仍是數學家有興趣研究的問題。然而這個問題在實務上真正的應用卻要等到資訊時代來臨的今天：網路安全與電子商務上的資料加密及數位簽章。
質數有無窮多
對於任何一個大於1的正整數，如果除了1和本身之外，沒有其他的因數，則稱這個數為質數(prime)，否則則稱為合數(composite)。例如，2,
3, 5, 7, 11等是質數，4,
6, 8, 9, 10則是合數。在所有正整數的數列中，質數出現的頻率似乎是隨著數字的增大而降低，因為一個較大的整數有其他因數的可能性應該比一個較小的整數來得大。既然質數出現的頻率越來越低，那麼質數的個數是否是有限的呢？關於這個問題，歐幾里得(Euclid)證明”質數的個數為無限”如下：
假設P是一個最大的質數。令N為所有小於或等於P的質數的乘積。則N+1很明顯不能被任何小於或等於P的質數整除，因此只有兩種可能：
(1) N+1是一個大於P的質數
(2) N+1的質因數都大於P
不論是(1)或(2)的情況都會得到大於P的質數
這個證明提出一個有趣的觀念，由2開始將一連串的質數相乘後加1，就會創造新的質數！(注意：新質數出現在2´3´5´...´p+1之中，而不一定是2´3´5´...´p+1)。既然質數的個數是無限的，於是數學家就希望可以用一些公式來表示質數，但是，往往無法成功。較有名的是17世紀初法國數學家梅森尼提出的梅森尼質數(Mersenne
primes) 2p-1，本來以為只要p是一個質數，n=2p-1就會是一個質數，這在p=3
(n=7)，p=5
(n=31)，p=7
(n=127)，都是正確的，但是p=11
(n=2047=23´89)
就不正確了。雖然如此，科學家們還是用梅森尼質數來尋找最大的質數，目前的紀錄是1999年找出的26972593-1，是一個2098960位數的整數。
公鑰密碼系統需要大質數
自從1976年Diffie和Hellman提出公鑰密碼系統(public-key
cryptosystem)的觀念之後，許多演算法例如Diffie-Hellman密鑰交換(1976)、RSA加密(1978)、ElGamal數位簽章(1985)紛紛提出，應用在包括資料加密以及數位簽章等實際用途上。這些公鑰密碼系統都有一個共通點：需要大質數來建構其系統；RSA演算法需要兩個質數p和q相乘得到的N來當作系統運作時的參數，Diffie-Hellman演算法以及數位簽章標準(DSS)則需要質數p來構成一個有限體(finite
field) Zp以供系統運作。更重要的是，這些公鑰密碼系統的「安全強度」往往取決於所選擇的質數大小以及強弱(這裡的強弱是指有些質數具有較弱的性質，例如，如果p-1的質因數都太小，就容易被攻擊者用特殊的攻擊法攻擊)；對RSA演算法來說，其強度決定於「大數分解」的困難度，至於對Diffie-Hellman演算法及DSS而言，其強度則決定於Zp上的離散對數問題的困難度。因此，如何找到一個大的質數來構成我們所需要的安全公鑰密碼系統，就成為一個重要的研究課題。
如何尋找大質數
一般而言，在實際應用上我們會利用以下的步驟來找尋我們所需要的大質數：
(1)
根據所要求的位數，隨機挑選整數n當候選質數
(2)
對n作質數檢驗(primality
test)
(3) 如果n被驗證不是質數，則回到步驟(1)；否則輸出n
這個方式的可行性必須考慮以下兩點：1.
由於我們是隨機挑選n，因此我們必須討論挑選到的數是質數的機率有多少，會不會太小以致於我們必須重複非常多次才能找到我們要的質數。2.
另外，有沒有好的演算法可以檢查n是不是質數，又通過演算法的n是否真的是質數。
首先，由質數定理我們知道質數的分佈密度：小於或等於n的質數個數約等於n
/ loge n，換句話說，當我們任意挑選一個數n，且這個數n是質數的機率約等於1
/ loge n；舉例來說，如果任意挑選一個100位數的整數，且挑到的整數又剛好是質數的機率約為1
/ loge 10100 »
1/230，也就是平均每230次應該會有一個質數。實際上這個數字可以透過一些篩選的技巧使得次數降低，例如判斷是否是小質數2,
3, 5, 11的倍數來決定要不要成為候選質數，如此一來就可以將次數再降低。
如何檢驗質數
接著，我們說明如何做質數檢驗，這裡我們將檢驗通過的候選質數分為兩類：一類是檢驗通過的候選質數有很大的機率真的是質數但不是絕對的，稱為可能質數(probable
prime)；另一類則是檢驗通過的質數真的就是質數，稱為可證明質數(provable
prime)。以下我們就找第一類可能質數的檢驗法加以說明。這一類的檢驗法乍看之下似乎沒有價值，然而由於其執行效率快，且可以透過重複多次的檢驗使得錯誤率迅速的降到很低(如低於10-100)，因此在實際應用上，反而有較高的價值。
檢查一個整數是否是質數最直覺的方法就是試除法，把n用小於或等於√n的質數去試除，如果都無法整除則n是質數，這個方法雖然看起來簡單，但執行起來卻十分費時，一般來說當n是10位數時就已經很吃力了，更何況我們要的質數往往都是100位數以上。1640年法國數學家費馬(Fermat)注意到質數的一個性質，稱為費馬小定理(Fermat’s
little theorem)：
[費馬小定理]
若n是質數，則對所有與n互質的數a，an-1≡1
(mod n)
實際上當n不是質數的時候，有可能存在這樣一個a，使得an-1≡1
(mod n)，這時候我們稱n為基於a的偽質數(base-a
pseudoprime)，因此，根據定理的逆方向設計的質數檢驗法稱為費馬檢驗(Fermat
testing)。
[費馬檢驗]
for i = 1 to t
do
隨機挑選a，a介於2和n-2之間
計算r
= an-1 (mod n)
if r ¹
1 then output “合數”
output
“質數”
這個檢驗法希望藉由重複t次不同a值的檢驗，將產生偽質數的機率降到很低。然而有一類合數n，滿足對所有與n互質的數a，an-1≡1
(mod n)成立，這種n稱為卡麥克數(Carmichael
numbers)。因此即使n通過所有a的費馬檢驗，n仍然有可能屬於卡麥克數而不是質數。數學家已經找出所有255個8位數以內的卡麥克數，其中前三個分別是561,
1105, 1729。注意，費馬小定理中的所有與n互質的數，當n是質數時，實際上就是{1,
2, …, n-1}；如果n不是質數，例如n=12，則所有與n互質的數為{1,
5, 7, 11}，也就是說，在檢查是否屬於卡麥克數時，只檢查aÎ{1,
5, 7, 11}，而不是{1,
2, …, 11}。
米勒-拉賓檢驗
到目前為止，實際運用上最常使用的質數檢驗法為米勒-拉賓(Miller-Rabin)檢驗，其依循的是當p為質數時，X2≡1
(mod p)只有兩個解X≡±1
(mod p)。利用這個觀念，米勒-拉賓檢驗在計算an-1
(mod n)的過程中，隨時檢查是否有X2≡1
(mod n)，但是X不等於±1
(mod n)的情形發生，如果有此種X，則n為合數。同樣的也挑選t次不同的a值進行檢查，使得產生偽質數的機率降低。有理論可以證明每挑選一次a值進行檢查，結果是偽質數的機率小於或等於1/4，經過t次之後我們就可以把錯誤率降到1/4t，達到可以接受的範圍之內。
[米勒-拉賓檢驗]
for i = 1 to t
do
隨機挑選a，a介於2和n-2之間
計算r
= an-1 (mod n)，過程中
if
$
X2≡1
(mod n) but X¹
±1
(mod n) then output “合數”
if r ¹
1 then output “合數”
output
“質數”
結語
本文從大質數最重要的應用—密碼學的角度出發，探討尋找大質數的方法及程序，並提供目前檢驗質數最有效的米勒-拉賓檢驗法。另一類可證明質數的檢驗法因其有效性與檢驗出質數的可用性在實際應用上有所不足，故在文中沒有提及。此外對於大質數相關的問題尚有各種質數檢驗法、特別種類的質數、可以定義質數的函數、質數有關的分佈均可在Paulo
Ribenboim編寫的”The
Little Book of Big Primes”(1991 Springer-Verlag出版)一書中找到資料。
