素数判定在信息安全中的应用

摘要

本论文致力于研究产生强素数的算法，研究素数判定，从古老的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算法，并提出新的素数判定，进而降低整个算法时间复杂性，加强和完善素数判定在信息安全中的应用.

目录

文摘

英文文摘

第一章绪论

1.1研究背景

1.2相关工作

1.3本论文的体系结构

第二章数论和密码学的背景知识

2.1素数判定的若干定理

2.2广义黎曼假设

2.3算法及其计算量的概念

2.4数论中的基本算法

2.4.1四则运算

2.4.2幂运算

2.4.3 Lucas序列的项的计算

2.4.4最大公因数的算法

2.4.5 Jacobi符号的计算

2.5 RSA公钥密码系统

2.5.1 RSA加密算法

2.5.2强素数

2.6本章小结

第三章素数判定方法

3.1素数判定的一般理论

3.2初等的素数判定算法

3.2.1一个经典的结果

3.2.2 n-1检验法和n+1检验法

3.2.3联合判定

3.3概率多项式算法

3.3.1 Slolovay-Strassen判定

3.3.2 Miller-Rabin判定

3.3.3 ECPP判定

3.4 APR-CL判定

3.5一个确定型的多项式算法

3.6本章小结

第四章AKS算法及其改进

4.1算法及其正确性

4.1.1算法的描述

4.1.2算法的正确性

4.2算法的时间复杂性分析及其改进

4.2.1 AKS算法的时间复杂性

4.2.2算法的改进

4.3基于AKS算法思想的新算法

4.3.1算法的基本思想

4.3.2 证书的构造

4.4本章小结

第五章素数判定在RSA公钥密码系统中的应用

5.1强素数

5.1.1强素数判定

5.1.2生成强素数的一种方法

5.2 AKS算法在RSA中的应用分析

5.2.1Eratosthenes筛法

5.2.2 Miller-Rabin判定

5.2.3 AKS算法

5.2.4构造一个新的素数判定

5.3有待改进的地方

5.4本章小结

参考文献

原创性声明

致谢