素性檢測算法研究及其在現(xiàn)代密碼學中的應用.pdf

1、素數(shù)問題是一個使很多數(shù)學家著迷的問題。素數(shù)就是一個除了1和它自身以外不能被其它數(shù)整除的數(shù)。素數(shù)的一個基本問題是如何有效地確定一個數(shù)是否是一個素數(shù)，即素性測試問題。 素性測試問題不僅在數(shù)學上是一個有挑戰(zhàn)性的問題，而且在實際應用中也是非常重要的。在現(xiàn)代密碼系統(tǒng)中，大素數(shù)的判別和尋找對一些加密系統(tǒng)的建立起著關鍵作用。很多公鑰密碼算法都用到素數(shù)，特別是160位（二進制）以上的大素數(shù)。RSA的公共模數(shù)就是兩個512位以上的大素數(shù)的乘積；基

2、于有限域PF上離散對數(shù)的公鑰密碼體制，其中素數(shù)p要求在512位以上；基于橢圓曲線離散對數(shù)的公鑰密碼體制（ECC）中，一般要求基點的階是一個160位以上的大整數(shù)，且是一個素數(shù)。由此可見對大數(shù)進行的素性判斷的重要性。 判定一個整數(shù)是否是素數(shù)，最為簡單的想法是直接利用素數(shù)的定義，用比要判斷的整數(shù)小的素數(shù)去一一試除，如果能整除被檢測的數(shù)的話，那就能確定無疑為合數(shù)了．但是對于大素數(shù)來說，由于計算量太大，根本無法實現(xiàn)以用于具體應用。所以科學

3、家們根據(jù)素數(shù)判斷的理論發(fā)明了許多新的算法，提高了判斷一個大數(shù)是否是一個大素數(shù)的效率。 Eratosthenes篩法是對于所有素數(shù)都有效的最古老的算法，然而它的時間復雜性是輸入規(guī)模的冪指數(shù)，因此在實際中使用它是不合適的。17世紀的Fermat小定理是一些有效素性測試算法的起點，但其逆定理是不滿足的。許多科學家在費馬小定理的基礎上進行研究發(fā)明了很多新的素數(shù)檢測方法，但是這些算法大部分都是概率性的，比如說Miller-Rabin算法

4、和Solovay-Strassen概率素數(shù)測試法。直2002年，印度的三位科學家發(fā)明了確定性的素數(shù)檢測算法AKS算法。但是研究表明AKS算法的時間復雜度和空間復雜度并不能滿足時間中的需要。 隨著橢圓曲線算法的研究的開展，許多科學家又發(fā)明了利用橢圓曲線算法進行素性檢測的方法，并且成為今年來素性檢測領域里的一個重要方向。本文也對2中基本的橢圓曲線素性檢測算法做了簡單的分析。 本文從素性檢測算法的基本理論入手，對素性將測算法做