摘要：2006年孙智宏教授给出了k*2m±1型素数的判定准则，这是判定梅森素数的卢卡斯-勒梅检测算法的推广。本文中给出了相应的算法和计算程序，并计算了其时间复杂度和比特计算量。

毕业论文关键词：  素数判定，卢卡斯算法，时间复杂度52489

Abstract: In 2006 professor Zhi-hong Sun gave a general primality criterion for numbers of the form k*2m±1, which can be viewed as a generalization of the Lucas-Lehmer test for Mersenne primes. In this thesis we gave the corresponding algorithm and the calculating programs,  computed the time complexity and bit calculating amount of them. 

Keywords：prime test,  Lucas algorithm,  time complexity.

目录

1  引言 4

2  素数检测基本算法 4

3 一类特殊素数的检测算法 9

结  论 14

参考文献 15

致  谢 16 

1  引言

素数检测算法是计算数论中的重大问题，算法的时间复杂度计算也是较为困难的。目前AKS算法是唯一的适用于所有素数的多项式时间复杂度的算法，但是这一算法的复杂度依然较高，并不实用。实际适用的概率算法、椭圆曲线算法等算法的时间复杂度仍未被确定。

对于某些特殊类型的素数，较好的多项式时间算法是确定存在的，例如判定梅森素数的卢卡斯检测算法。 对梅森素数的研究历史渊源流长。尽管人们目前已拥有千万亿次超级计算机并发现许多先进方法寻找素数，但对梅森数的计算仍然被视为对超级计算机计算性能检验的重要课题。卢卡斯检测算法就是在对梅森素数判定的研究中产生的一类多项式时间的素数检测算法。

2006年，孙智宏教授在[1]中给出了一种特殊类型的素数的判定方法。在这一研究基础上，本文建立了对这一特殊类型素数进行判定的卢卡斯型检测算法，并确定了这一算法的时间复杂度和比特计算量。

2   素数检测基本算法

2.1 时间复杂度概念 

时间复杂度是指程序运行从开始到结束所需要的时间。算法是对特定问题求解步骤的一种描述，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量。

算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n).算法时间度量记作：T(n)=O(f(n)).

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度，简称时间复杂度。

常见的时间复杂度按数量级递增排列依次为：常数O(1)、对数阶O( )、线性阶O(n)、线性对数阶O（n )、平方阶O( )、立方阶O( )、…k次方阶O（ )、指数阶O( ).显然，时间复杂度为指数阶O( )的算法效率极低，当n的稍大时就无法应用。

2.2 几种基本算法的时间复杂度

  在算法时间复杂度的计算，最关键的是得出算法中最多执行的次数。很容易看出，算法中最内层循环体语句往往具有最大语句频度，在计算过程中对它们分析计算。

2.2.1 直接计算法

  当算法中语句的执行次数与某一变量有直接关系，而该变量的变化起止范围又较为明确，则可以利用求和公式得出最大语句频度f(n),在找相应的数量级。