素性检测及其应用开题报告

1. 研究目的与意义（文献综述）

随着计算机与网络普及到各大领域，人们深刻体会到网络给我们带来的便利，但随之网络病毒等危害网络的因素也同时出现，人们对网络安全（特别是个人的信息安全）越来越重视，网络安全话题也逐步变为网络中最为重要的话题之一。网络安全中的一大手段就是对数据进行加密，目前加密方法有许多，但在现代密码学中，许多加密方法都依赖于素数的选取，特别是大素数，大素数的使用使我们的信息越来越安全，从而大素数的生成和检测成为了至今为止一大重点。同时虽然素数的问题已经研究2000多年，但如何快速检验一个大整数为素数一直以来是数学上的一大挑战。

从很久以前欧几里得就得以证明素数的无限性；后来在公元前250年左右又有了eratosthenes筛法；17世纪的fermat小定理；1975年prat证明了整数的素数检测在非确定多项式时间内是可以完成的，1976年miller在广义黎曼假设条件成立的情况下，给出了一个确定多项式时间算法来验整数素性；1977年solovay与strassen和1980年rabin分别运用费马小定理和二次剩余定理证明出在多项式时间内可以判定一个数是否是一个合数；1981年，w.j.miller和n.g.trbovich发现了一个能够产生并检验大素数的高效算法；到了2002年，由agrawal、kayal和saxena成功解决在多项式时间内是否可以判别素数的难题，提出来著名算法aks；近些年，许多科学家在aks的基础上进行了lenstra、pomerance、berrizbeitia、bernstein等改进方法；

现阶段虽然对素数的检测已经有了很多方法，并且有了很多改良后已经应用到现今很多加密方法中，但对于试用于实际的素数检测和选取问题仍是一个重点加难点，在素性检测中有两种方法：一种是素性检测的概率算法，一种是素性检测的确定性算法；前者有一定的不准确性（检测出的数中还有小几率可能为合数），后者则对于大素数检测的时间复杂度远高于前者。现以概率性检测入手的科学家以优化速度与概率为目标，而更多的研究人员关于素性检测论文一般都以已有的各种概率检测方法为基础，从而构造出一个适用在现有计算水平上并且准确率也有保证的计算方法，预使时间以及精确度之间寻找一个理想的值，使素性检测更适用于实际生产中。

2. 研究的基本内容与方案

基本内容：本文先介绍素数和素性检测问题以及其在实际中应用的一些情况，再介绍几种密码体制以及其对大素数的利用和密切联系。然后从两种检测方法开始一一介绍并深入探讨：1.确定性算法，比如：椭圆曲线等。2.概率性算法，比如：solovay-strassen算法和miller-rabin算法等。然后试优化其中一种（或几种）让其能适用于实际计算和应用中。最后通过大整数素数检测计算和实验结果给出该方法可以继续改进的方式以及优缺点。

目标：从各方法中选取1中或几种进行改进，得到一种（或几种）可以适应生产（主要目的减少计算复杂度），并且有一定的准确性的一种方法，希望其可以在大整数素性检测中发挥一定的价值。

采用：预采用文献与实验综合的方法；通过查找文献学习并且进行分析和比较每种检测方法的时间复杂都和产生错误结果的概率，通过计算并寻找一个可以减少时间复杂度并且错误概率可以接受的的方法，并且通过一些密码体制实验rsa等（加密与解密）中试用，通过检验的成功的’素数’来进行实验分析，判断其的实际效果，预找到一个有一定优化效果的检测方案。

3. 研究计划与安排

开题报告结束后：

1-3周：总体设计，完成论文综述

4-7周：素性检验的理论分析，设计素性检验算法

4. 参考文献（12篇以上）

[1]issamkaddoura,samih abdul-nabi.on formula to compute primes and the nth prime.mathematics,2012.

[2]gabrielemartino.primality test.american journal of computationalmathematics(ajcm),2013.

[3] puryabaghaei,nazila amrahi.primality testing using complex integers and pythagoreantriplets,2011