素?cái)?shù)判定在信息安全中的應(yīng)用.pdf

1、　　本論文致力于研究產(chǎn)生強(qiáng)素?cái)?shù)的算法，研究素?cái)?shù)判定，從古老的Eratosthenes篩法，n-1檢驗(yàn)法和n+1檢驗(yàn)法，到Solovary-Sreassen檢驗(yàn)法和Miller-Rabin檢驗(yàn)法，其間還涉及EllipticCurvesPrimalityProving(ECPP)判定和由Adleman，Pomerance和Rumely提出的APR判定.　　在目前素?cái)?shù)應(yīng)用最廣泛的領(lǐng)域一公共密鑰體系中，一般選擇的素?cái)?shù)都是相當(dāng)大的(通常在100

2、位以上)，如果采用試除法來(lái)判定，需要很長(zhǎng)的時(shí)間.所以在一般的應(yīng)用領(lǐng)域，人們采用的是Miller-Rabin檢驗(yàn)法，但是這種方法總是不可避免的存在出錯(cuò)的可能性.本論文給出強(qiáng)素?cái)?shù)的產(chǎn)生算法，其中用Agrawal等提出的算法(AKS算法)取代常用的Miller-Rabin檢驗(yàn)法來(lái)進(jìn)行素?cái)?shù)判定，并將算法應(yīng)用于RSA公鑰體制中.我們研究了對(duì)AKS算法的改進(jìn)，其中改進(jìn)了求最大公因式的Euclid算法，并提出新的素?cái)?shù)判定，進(jìn)而降低整個(gè)算法時(shí)間復(fù)雜性，