摘 要

本文分为三大块。第一块对素数的一些基础理论进行了较简洁的介绍；第二块主要对素性检测进行了比较详细的讲解，并且通过介绍素性检测加深大家对素性检测有更深刻的概念；第二块主要对现有素性检测算法进行优化，使算法执行过程得到优化，所得结果对于素性检测在应用中具有重要的指导意义。

论文主要分析了素性检测的两种方法：确定型检测和概率型检测，并重点研究了概率检测算法。并且分析了其在RSA等密码体制中的应用。

分析结果表明：合适的素性检测可以带来实际应用中的便利，也只有不断地分析实际需求才能得出合适的素性检测方法。

本文的特色:通过分析算法中时间复杂度和精准度，通过优化算法过程，设计一种更适合实际应用的算法。

关键词：素性检测；时间复杂度；素数的概率

Abstract

This paper is divided into three blocks. A concise introduction to the first block of prime numbers some basic theory; the second block mainly on primality testing were more detailed explanation, and by the primality testing deepen everyone on primality testing has more profound concept; the second block mainly existing primality testing algorithm to optimize the algorithm implementation process was optimized. The results for primality testing in the application has important guiding significance.

Thesis focuses on the analysis of the two methods of primality testing: to determine type detection and probability of detection, and focus on the probability of detection algorithm. And its application in RSA and other cryptographic systems is analyzed.

Analysis results show that suitable primality testing can bring convenience of practical application, the only constant analysis of the actual demand to draw the appropriate primality testing method.

The characteristics of this paper: through the analysis of the time complexity and precision of the algorithm, through the optimization algorithm process, the design of a more suitable for the practical application of the algorithm.

Key Words: primality testing; time complexity; prime number probability

目录

摘 要 I

Abstract II

第一章 绪论 1

1.1研究背景 1

1.2研究目的 1

1.3研究意义 2

第二章 素数 3

2.1 素数相关的一些概念 3

2.1.1 素数的定义 3

2.1.2 素数的性质 3

2.1.3 素数发展简单介绍 4

2.2 特殊素数 4

2.2.1 梅森素数 4

2.2.2 孪生素数 4

第三章 素性检测 5

3.1试除法 5

3.2 Solovay-Strassen 素性检测法 5

3.2.1 算法涉及的定义和定理 6

3.2.2 算法内容 11

3.3 Miller-Rabin 素数测试法 12

3.3.1 一些定理 12

3.3.2 Miller-Rabin素数测试法 12

3.3.3 Miller-Rabin的算法优化 13

第四章 素性检测在实际中的应用 15

4.1 RSA公钥密码体制 15

4.1.1 公钥密码体制 15

4.1.2 RSA密码体制的内容 15

4.1.3 RSA的安全性 17

4.2 其他公钥密码体制 18

4.2.1 EIGamal公钥密码体制 18

4.2.2 椭圆曲线Menezes-Vanstone公钥密码体制 18

第五章 总结 19

5.1 论文总体分析 19

5.2 方法扩展 19

参考文献 21

致谢 23

1. 绪论

1.1研究背景

随着计算机与网络普及到各大领域，人们深刻体会到网络带来的便利，但随之网络中木马、病毒、窃取传输数据等危害网络的因素的出现，人们对网络安全（特别是其中的信息安全）越来越受到大家的重视，网络安全的分析与研究逐步变为网络中非常重要的课题之一。网络安全中信息保护的一大手段就是对数据进行加密处理，使数据不能被轻易获取，从而达到传输安全。目前加密方法有许多种，但在现代密码学中，许多加密方法都依赖于素数的选取，特别是大素数，大素数的利用可以使我们的信息越来越安全，大素数的快速生成、检测以及应用成为了今天信息安全的热门话题。

虽然素数的问题已经研究2000多年，但如何快速检验一个大整数为素数一直以来是数学上的一大挑战。很久以前Euclid证明素数的无限性，为我们寻找大素数打下了基础；后来在公元前250年左右又有了Eratosthenes筛法，使素数的检测有了一个方法，但很难寻找很大的素数；之后17世纪的Fermat小定理的出现为概率检测给出了坚实的理论基础；1975年Pratt证明了整数的素数检测在非确定多项式时间内是可以完成的；1976年Miller在广义黎曼假设条件成立的情况下，得出了一个确定多项式时间算法来验整数素性；1977年Solovay与Strassen和1980年Rabin分别运用费马小定理和二次剩余定理证明出在多项式时间内可以判定一个数是否是一个合数；1981年，W.J. Miller和N.G.Trbovich发现了一个能够产生并检验大素数的高效的确定型算法；1983年, L.M.Adleman,C.Pomerance和R.S.Rurnenly发现了一种概率测试素数的算法；1986年Gpldeasser和Killian提出基于椭圆曲线的算法；到了2002年，由Manindra Agrawal、Neeraj Kayal和Nitin Saxena成功解决在多项式时间内是否可以判别素数的难题，提出来著名算法AKS；近些年，许多科学家在AKS的基础上进行了改进也取得了很好的结果^[1]。

1.2研究目的