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

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

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

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

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