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

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

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

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

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