一类特殊素数的卢卡斯检测算法

论文总字数：8662字

摘 要

关键词： 素数判定，卢卡斯算法，时间复杂度

Abstract: In 2006 professor Zhi-hong Sun gave a general primality criterion for numbers of the form k*2^m±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),在找相应的数量级。

例2.1 算法如下：

① x=0, y=0,

② for(k=1;klt;=n;k )

③ x ;

④ for( i=1;ilt;=n;i )

⑤ for(j=1;jlt;=n;j )

⑥ y ；

解 以上程序中频度最大的语句是⑥，其频度为，所以该程序时间复杂度是T(n)=O().

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度决定的。

例2.2 算法如下：

① x=1;

② for( i=1; ilt;=n; i )

③ for( j=1; jlt;=i; j )

④ for(k=1;klt;=j;k )

⑤ x ;

解 该程序段中频度最大的语句是⑤内的循环执行次数虽然与问题规模n没有直接关系，但是却与外层循环变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句⑤的执行次数:

则该程序段的时间复杂度为T(n)=O().

2.2.2假设算法

在某些循环结构的循环次数很难直接看出，特别是循环次数与某些循环体的语句k值，再计算出T(n),进而求T(n)的数量级.

例2.3 算法如下：

① i=s=0

② while(slt;n)

③ i ；s=s 1;

解 执行到k次，i=k,s=0 1 2 3 …… k= 。该算法的时间复杂度T(n)=O()。

2.2.3 递推算法

当算法中包括递推函数时，其时间复杂度转化为一个递推关系。递推关系很多，介绍其中一种常见的，再根据递推关系一步步求出T(n)。

例2.4 算法如下：

① void sum(int a[],int n, int k)

② {int i；

③ if(k=n-1)

④ for(i=0;ilt;n;i ) printf(“%d”,a[i]);

Else

{For(i=k;ilt;n;i ) a[i]=a[i] i;

sum(a,n,k 1);}}

解 设sun(a,n,k 1)执行时间为T(k),有算法的递归关系如下：

则T(0)=T(1) n=T(2) (n-1) n=…=n (n-1) … 2 T(n-1)===O()

所以，该算法的时间复杂度T(n)=O().

剩余内容已隐藏，请支付后下载全文，论文总字数：8662字