概率型与确定型素数生成算法及在密码学中的应用

摘要

在密码学的应用中，素数的检测与应用是一个永恒的主题。数学工作者们在一方面一直致力于寻找各种素数检测的有效方法，提高检测的效率，尽可能地降低时间复杂度；在另一方面，又把各种先进的数论研究成果运用到密码学中去，丰富了密码学的内涵。现在用于检测素数的主要手段是利用诸如Rabin—Miller算法以及Solovary—Strassen算法的概率算法，但遗憾的是它不是确定型的算法，即用概率算法测试得到的“素数”不一定是真正的素数。现在虽提出了一种著名的确定型算法—AKS算法，但是它的执行效率比较低。本文利用初等数论以及抽象代数的基本理论提出了一类确定型的素数的生成算法，以及两种多项式环上的概率型素数生成算法。本文的确定型算法只生成某一特定类型的素数，从而在一定程度上弥补了AKS算法执行效率低的缺点，而且按照这种算法所生成的素数是安全度较高的，因而它特别适合于用作RSA密码体系中的素因子。

目录

文摘

英文文摘

声明

第1章 引言

1.1密码学简介

1.2密码学的应用

1.3素数与密码学

1.4全文结构

第2章 密码学的理论基础—数论

2.1同余

2.2中国剩余定理

2.3原根

2.4 Gauss二次互反律

第3章素数的判断和测试

3.1素数检测的成本

3.2素数检测的一些方法

第4章几种重要的公钥密码系统

4.1 RSA密码系统

4.2 ElGamal密码系统

4.3背包密码系统

第5章 任意长确定型素数的生成

5.1任意长ab+1类确定型素数的生成

5.2任意长ab-1类确定型素数的生成

5.3任意长安全素数的生成

5.4基于不可约多项式的素数测试方法

第6章 总结与展望

参考文献

致谢