质数的运用.doc

尋找大質數 胡鈞祥，陳榮傑 交通大學 email : jshwu@csie.nctu.edu.tw , rjchen@csie.nctu.edu.tw 前言 質數的觀念雖然起源於人類有自然數的觀念不久後，但是直到近代尋找大質數仍是數學家有興趣研究的問題。然而這個問題在實務上真正的應用卻要等到資訊時代來臨的今天：網路安全與電子商務上的資料加密及數位簽章。 質數有無窮多 對於任何一個大於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年找出的座机电话号码，是一個座机电话号码位數的整數。 公鑰密碼系統需要大質數 自從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 ；另一類則是檢驗通過的質數真的就是質數