首页 > 论文范文 > 自然科学论文 > 数学论文 > 数论论文 > 判定算法与素数构造的研究

判定算法与素数构造的研究

2020-06-28 225 上传者：管理员

摘要：分析了用于素数构造和判定的相关定理及常用的算法:Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法及3种改进算法。对Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法的效率进行了比较。实验数据表明,Miller-Rabin素数测试算法的效率最高,基于莱梅定理的素数构造算法次之,AKS素数测试算法及3种改进算法效率最低。

关键词：
AKS定理
二次探测定理
数论
有限域
算法效率
莱梅定理
加入收藏

素数的判定算法是对输入的整数判定是素数还是合数，分为概率算法和确定算法。素数构造算法是输入小素数，经过若干次循环构造出大的素数。对已有的素数构造和判定算法进行梳理，给出算法的描述并编程实现Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法及变体算法，对上述算法的效率进行比较。

1、Miller-Rabin素数测试算法

令n-1=（2s）*d，其中s是非负整数，d是正奇数。若ad=1(modn）或存在一个r,0≤r≤s-1，使得a(2r）*d）≡-1(modn），则称n通过以a为基的MillerRabin测试，n可能是素数。文献[1]指出，如果n通过k次Miller-Rabin素数测试，但n为合数的概率最多不会超过4-k。

Miller-Rabin算法时间复杂度均为O(log(n)3）。文献[2]指出，当n>109时，n通过Miller-Rabin素数测试，但n为合数的概率最多不会超过10-6。

2、基于莱梅定理的素数构造算法

文献[3]提出基于莱梅定理的素数构造算法，算法是由若干个小素数组成的因数基通过循环构造出若干个大素数的算法[3]。基于莱梅定理的素数构造算法的时间复杂度为O(log2(logn)）。

3、AKS素数测试算法及变形算法

3.1AKS素数测试算法

由印度科学家ManindraAgrawal、NeerajKayal和NitinSaxena于2002年提出。AKS素数测试算法是基于如下定理。

a∈Z,gcd(a,n）=1，正整数n（≥2）是素数当且仅当(x+a)n≡(xn+a)(modn)。

AKS素数测试算法可以作为素数判定的确定算法。对输入的n，只要选择a并检验多项式（x+a)n≡（xn+a)(modn）是否成立便可在判断n是素数还是合数。但使用多项式（x+a)n≡（xn+a)(modn）测试需指数时间，因此，AKS算法效率极低。

2003年，ManindraAgrawal、NeerajKayal和NitinSaxena在网站www.cse.iitk.ac.in给出AKS素数测试算法的变形算法[4]，算法描述如下：

算法表示1

2004年，Agrawal,Kayal和Saxena对此进行改进，通过适当选择r，检验是否满足等式（x+a)n=xn+amod(xr–1,n）。如果n是素数，对所有的a和r满足上式。如果n是合数，存在少量的a和r也满足上式。利用有限域上分圆多项式的性质，适当选择r，使得一定范围内的a满足上式，则n是素数的方幂。改进后的AKS素数测试算法基于如下定理：

设n为正整数,r是一个正整数且满足ordr(n)>log2(n)。任意1≤a≤r,gcd(a,n)=1。任意1≤a≤的所有数(x+a)n≡(xn+a)mod(xr–1,n)成立,则n是素数的方幂。

算法的时间复杂度变为O(log(n)7.5）[5]。

3.2AKS-Bernstein第一算法

2003年，Bernstein给出一个比AKS素数测试算法的变形算法较好的改进算法（简称AKS-Bernstein第一算法），算法也是利用有限域上分圆多项式的性质，适当选择r，使得一定范围内的a满足（x+a)n=xn+amod(xr–1,n），则n是素数的方幂。AKS-Bernstein第一算法改进的思路是减少第AKS素数测试算法的变形算法第（10）步循环的次数及多项式xr–1中r的值。

AKS-Bernstein第一算法主要基于如下定理：

设n为正整数，q,r为素数满足q|（r-1）且n(r-1）/qmodr埸{0,1}，s为有限整数集，记|s|为集合s的元素个数，若任意b,b’∈S,b≠b’有gcd(n,b–b’）=1，且。任意b∈s有（x+b)n≡（xn+b)mod(xr-1,n）。则n是素数的方幂[6]。

如果r,q,s满足AKS变形算法，即取时，有

公式1

即如果r,q,s满足AKS变形算法，可得r,q,s满足AKS-Bernstein第一算法。由此可见AKS变形算法的正确性。

3.3AKS-Berrizbeitia算法

Berrizbeitia提出对限定条件的一类整数进行素性测定的AKS算法改进版本（简称AKS-Berrizbeitia算法）。时间复杂度最多为O(log(n)6），大多数时间复杂度变为O(log(n)4。AKS-Berrizbeitia算法是利用有限域上不可约多项式的性质及弗罗贝尼乌斯自同构的性质。算法对于被测正整数n，当n≡1mod4时要求提供整数a满足Jacobi符号（）=-1。需要验证的同余式为：（1+mx)n≡（1+mxn)mod(x2s–a,n）。其中m∈S，|S|=2max(s-k,0),s=┌2loglogn┐，k=v2(n-1)，表示整数n-1分解式中素因子2的指数[7]。

当n≡3mod4时要求提供整数a满足Jacobi符号（）=（1-）=-1。需要验证的同余式为：（1+mx)n≡（1+mxn)mod(x2t+1-2x2t+a,n）。其中m从1至2max(t-k-1,0),t=2loglogn+1,k=v2(n+1），表示整数n+1分解式中素因子2的指数[7]。

3.4AKS-Bernstein第二算法

Bernstein又提出一个比AKS-Berrizbeitia算法更一般的基本上随机4次多项式时间素性证明的AKS算法改进版本（简称AKS-Bernstein第二算法）。算法基于库默尔扩张理论，时间复杂度变为O(log(n)4）[8]。

定理设n,d,e为正整数，c1,c2为整数，f(x）是Zn[x]中最高次数为d的首一多项式，R是一个剩余类环Zn[x]/f(x),r是R中一个元素，S是R中一个子集。（d,e,c1,c2,f,r,S）为n的一个证据，则n是一个素数的方幂。

当d=1时，令f(x）=x，则R=Zn[x]/x=Zn，而R中的单位即为与n互素的整数。

算法简单描述如下[9]：

(1）若存在整数a>0且b>1，令n=ab；则输出合数。

(2）找出n的证据，即（e,c1,c2,r,S）。

(3）若对s∈S,(x-s)n≠（r(n-1）/ex-s)mod(xe–r,n），若不满足，输出合数，若都满足，（e,c1,c2,r,S）是n的一个证据，输出素数。

4、3种算法的实现

4.1Miller-Rabin素数测试算法

Java语言中的java.math.BigInteger类提供了模运算、素性测试、素数生成等操作。成员函数isProbablePrime(intcertainty）是针对BigInteger类的一个素数判断函数，它的实现原理用到Miller-Rabin素数测试，是一个概率算法。参数certainty是素数测试的次数，此方法的执行时间与此参数的值是成比例的。如果一个数可能为素数，则返回true，如果该调用返回true，一个数是素数的概率超出（1-（1/4)certainty）。如果一个数为合数，则返回false。

4.2基于莱梅定理的素数构造算法

NTL是一个用于大整数运算的C++库，可以用于任意长度的整数计算。NTL中函数PowerMod(a,b,c）的功能是求abmodc的值。有了此函数，就可判断n=2r*pi1*pi3+1是否满足莱梅定理的条件：对于n-1的每一个素因子p存在一个整数a使得：an-1=1(modn），且a(n-1)/p≠1(modn）。需自定义函数Power(a,b）求ab。定义数组arr＿p[4]保存初始因子基（2,p11,p12,p13）的值，类型为ZZ。用循环语句实现算法，得到满足条件的素数输出后循环结束。

4.3AKS素数测试算法

NTL是一个用于大整数运算的C++库，可以用于任意长度的整数计算及整数的多项式算法。ZZ表示任意长度的大整数，ZZ＿p表示模p大整数运算类，ZZ＿pX表示ZZ＿p上模p一元多项式运算类。

(1)AKS素数测试算法

算法第①步“若存在整数a>0,b>1,使得n=ab;则输出合数。”首先调用一次Nt1(n),判断n是否为平方数。然后数次调用Nt2(n,e),判断n是否为e次方数(e为奇数)。

Nt1(n)算法如下：

算法2

Nt2(n)算法如下:

算法3

算法计算最小的r使得ordr(n)>log2(n)方法为:固定r为log2(n),判断所有的1≤i≤log2(n),如果ni≡1modr,则r的值增加1,重新判断如果所有的1≤i≤log2(n),都有ni≠1modr,则r值满足条件。

(2)AKS素数测试算法的变形算法

算法需调用NTL中函数SqrRoot(n）求，函数PowerMod(a,b,c）求abmodc的值。需自定义函数LOG＿c(c,n）求以c为底的n的对数；max＿prime(n）求n的最大素因子，prime(n）判断n是否为素数。

(3)AKS-Bernstein第一算法

程序中变量r,s,q为ZZ数据类型。调用NTL中函数SqrRoot(n）求，函数PowerMod(a,b,c）求abmodc的值。需自定义函数max＿prime(n）求n的最大素因子，prime(n）判断n是否为素数，Power(a,b）求ab。

(4)AKS-Berrizbeitia算法

当n≡1mod4时，需调用NTL中函数PowerMod(a,b,c）求abmodc的值；函数GCD(a,b）求a,b的最大公约数。需自定义函数LOG＿c(c,n）求以c为底的n的对数；v2p(n）求n的分解式中素数2的指数；Power(a,b）求ab;max(a,b）求a,b中较大的数。

当n≡3mod4时，需调用NTL中函数PowerMod(a,b,c），函数GCD(a,b）。需自定义函数LOG＿c(c,n),v2p(n），函数Power(a,b），函数max(a,b），函数功能同上。

(5)AKS-Bernstein第二算法

程序中变量e,c1,c2,r,s,q为ZZ数据类型。调用NTL中函数SqrRoot(n）求，函数PowerMod(a,b,c）求abmodc的值，函数GCD(a,b）求a,b的最大公约数。需自定义函数prime(n）判断n是否为素数，Power(a,b）求ab,comb(n,m）求n!/（m!*（n-m）!）。

5、3种算法实验数据比较

实验结果在Intel(R)Celeron(R)CPU3.80GHz,4GB内存，Windows10操作系统，VS2015环境下运行得到。运行时间单位为秒。

5.1AKS算法、AKS变形算法、AKS-Bernstein第一算法实验数据比较

选取4个素数359、65537、3640471、4295884871,3种算法实验数据比较如表1所示。

表13种算法实验数据比较

实验数据表明，3种算法中，AKS算法效率最高。

5.2AKS算法、AKS-Berrizbeitia算法、AKS-Bernstein第二算法实验数据比较

n=65537时，n≡1mod4，满足Jacobi符号（）=-1的a为3。n=359、3640471、4295884871时，n≡3mod4，满足满足Jacobi符号（）=（1-）=-1的a分别为19、3、11。选取上述4个素数，3种算法实验数据比较如表2所示。

表23种算法实验数据比较

实验数据表明，3种算法中，AKS-Bernstein第二算法效率最高。

5.3Miller-Rabin算法、基于莱梅定理的素数构造算法、AKS-Bernstein第二算法实验数据比较

对于基于莱梅定理的素数构造算法，输入4个小素数：（2,65537,7,383），循环2次，第1次循环得到的3个素数为：P11=917519=2*65537*7+，P12=6425771777=28*65537*383+1,P13=85793=25*7*383+1。第2次循环得到的3个素数为：p21=94332283120980209=24*917519*6425771777+1,p22=7720512213636586958650719144300460631075250835340089278134839410689=2186*917519*85793+1,p23=8820579809026577=24*6425771777*85793+1。选取6个素数，对Miller-Rabin算法、基于莱梅定理的素数构造算法、AKS-Bernstein第二算法3种算法实验数据比较如表3所示。

表33种算法实验数据比较

实验数据表明Miller-Rabin素数测试算法的效率最高，基于莱梅定理的素数构造算法次之，AKS-Bernstein第二算法效率最低。

参考文献：

[1]魏成行.素性检测算法研究及其在现代密码学中的应用[D].山东大学,2009.

[3]周利荣.基于莱梅素数判定定理的安全素数构造算法[J].计算机应用研究,2016,52(13):152-156.

[4]朱文余.AKS算法及关于它的一种改进算法的实现分析[J].四川大学学报(自然科学版),2005,42(3):56-58.

[8]金正平.AKS素性测定算法两个改进版本在PC上的实现[D].安徽师范大学,2007.

周利荣,胡天磊.素数构造和判定算法研究综述[J].电脑编程技巧与维护,2019(08):9-12.

基金:衢州职业技术学院重点科研项目,项目编号:QZYZ1705

网友评论

加载更多

我要评论

期刊名称：数学的实践与认识

期刊人气：2808

期刊详情

主管单位：中国科学院

主办单位：中国科学院数学与系统科学研究院

出版地方：北京

专业分类：科学

国际刊号：1000-0984

国内刊号：11-2018/O1

邮发代号：2-809

创刊时间：1971年

发行周期：半月刊

期刊开本：16开

见刊时间：1年以上

论文导航

判定算法与素数构造的研究

相关论文

探讨振子电网反馈增益的取值对同步能力的影响

关键词

数论题目汇总50篇

关键词

数论中纽结理论的应用研究

关键词