论文部分内容阅读
本论文致力于研究产生强素数的算法，研究素数判定，从古老的Eratosthenes筛法，n-1检验法和n+1检验法，到Solovary-Sreassen检验法和Miller-Rabin检验法，其间还涉及EllipticCurvesPrimalityProving(ECPP)判定和由Adleman，Pomerance和Rumely提出的APR判定.
在目前素数应用最广泛的领域一公共密钥体系中，一般选择的素数都是相当大的(通常在100位以上)，如果采用试除法来判定，需要很长的时间.所以在一般的应用领域，人们采用的是Miller-Rabin检验法，但是这种方法总是不可避免的存在出错的可能性.本论文给出强素数的产生算法，其中用Agrawal等提出的算法(AKS算法)取代常用的Miller-Rabin检验法来进行素数判定，并将算法应用于RSA公钥体制中.我们研究了对AKS算法的改进，其中改进了求最大公因式的Euclid算法，并提出新的素数判定，进而降低整个算法时间复杂性，加强和完善素数判定在信息安全中的应用.