AKS算法及其素数判定的C语言实现
AKS算法及其素数判定的C语言实现
马云涛
西南交通大学、四川成都
myt2681@https://www.wendangku.net/doc/733349246.html,
摘要：最近，印度的三个计算机科学家Manindra Agrawal、Neeraj Kayal和Nitin Saxena 提出了一个称为AKS的算法。使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定，从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意叉。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上，因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。
关键词：AKS算法现代密码学 RSA算法
AKS algorithm and its prime numbers to determine by the C program language
Ma Yun Tao
Southwest Jiaotong University , Chengdu Sichuan
myt2681@https://www.wendangku.net/doc/733349246.html,
Abstract：Recently，three computer scientists Manindra Agrawal，Neeraj Kayal and Nitin Saxena in India present algorithm called AKS ．By this algorithm they give a proof that it is possible to determine if a number is a prime in polynomial time．So，they have cracked an age-old mathematical problem．The result has important significance to research and development in both number theory and computational complexity theory．Because modern cryptography is based on the theory of integer factoring and the computational complexity theory ，the effect of this algorithm to modern cryptography has been paid significant attention．It will be discussed in this paper．
Keywords：AKS algorithm，Modem cryptography，RSA algorithm
1引言
很久以来，素数问题是一个使得很多数学家着迷的问题。素数就是一个除了l和它自身以外不能被其它数整除的数。素数的一个基本问题是如何有效地确定一个数是否是一个素数，即素性测试问题。素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际中也是非常重要的。例如，很多现代密码学应用通常需要确定一个几百位的素数。如果不采用一些专门有效的方法，即使人们使用运行速度最快的计算机来测试一个l00位的十进制整数，那么花费的时间将超过宇宙存在的时间。
数学家尝试设计对素数的有效测试已经长达两千多年了。Eratosthenes筛法是对于所有素数都有效的最古老的算法，然而它的时间复杂性是输入规模的幂指数，因此在实际中使用它是不合适的。l7世纪的Fermat小定理是一些有效素性测试算法的起点，但其逆定理是不满足的。上世纪80年代，这个领域的普遍观点是应该存在一个用于素性测试的确定的多项式时间算法，但没有人能给出证明。当前，已经确立了一些素性测试算法，但是它们都存在一些问题。一些算法是非常快速的，但是这些算法会以很小的概率产生一个错误结果；另一些算法是有条件的，如使用了未证明的假设；还有一些算法是确定的也是无条件的，但不能在
多项式时间内完成。因此，设计一个在多项式时间内每次都给出一个正确回答的有效算法在计算机科学和数学中都是一个挑战。多年来，研究者们已经尝试了很多方法，包括使用了一些复杂的数学技术，但没有一个成功。
然而，到了2002年8月这一情况有了改变。Manindra A．grawal教授和他的两个学生Neeraj Kayal，Nitin Saxena设计了一个被称为AKS的算法，该算法是一个用于素性测试的多项式时间的确定算法。这一结果被认为是这一领域的一个主要突破。一些权威认为这个算法将产生广泛的影响，而最直接的就是对整数理论和计算复杂性理论的影响。由于现代密码学正是以整数分解理论和计算复杂性理论为基础，因此AKS 算法对现代密码学的影响引起了人们的关注。RSA算法是现代密码学中应用最为广泛的一个算法，同时它既可用于加密，又可用于数字签名。
2AKS算法简介
Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技术研究所开发设计了AKS算法。AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题，而没有使用任何未证明的数学假定。下面是AKS算法的简要描述。
Input : integer n>1
1.If (n=a b for a∈N and b>1), output composite.
2.Find the smallest r such that O r(n)>log2n.
3.If 1<(a,n) 4.If n≤r, output prime. 5.For a=1 to lognф? do if ((X+a)n≠X n+a(mod X r-1,n)) ,output composite. 6.output prime. 尽管理解算法的原理有一些困难，但程序的理解是很容易的。算法的详细解释，请参考文献【l】。 AKS算法是一个新颖的、有趣的、优美的算法，它解决了一个很多世纪没有解决的基本问题。AKS算法的最重要之处就是它是相当简单的，不需要特殊的椭圆曲线数学及类似知识。AKS算法不是其他人工作的简单推广，它摒弃了把已有的方法集中到一起的想法，而是探索使用简单的代数概念来解决问题的方法。尽管思想是简单的，但是非常有创造性。然而，这个算法目前可能不会有太多的实际应用。这是因为算法的运行时间是O((1og n) )，与Miller 和Rabin设计的概率测试的O(1og／7,)运行时间相比是相形见绌的。研究者们注意到如果某个猜想被证明。算法可以在O((1ogn) )时间内运行，这样的改善将促进实际的应用。研究者们还证明如果Sophie Germain素数具有期望的分布，那么在时间估计中的指数l2可以减少到6当然如果发现素数的分布并非如此，那将会有很大区别。笔者将不得不期待算法的有效实现。AKS算法最重要的意义是为一个理论结果，为这一领域的研究奠定了基础。之后在技术上将会进行改进与完善，使之更为实用。 3AKS算法的C语言实现 #include #include #include #include unsigned long gcd(unsigned long n,unsigned long r) {if(!r) return n; return gcd(r,n%r); } int cf(unsigned long n) { double i; for(i=2;i<=ceil(log(n)/log(2));i++) { if(pow(n,1/i)-floor(pow(n,1/i))==0) { return 1; break; } } return 0; } int test(unsigned long r) {unsigned long i=2; while(i<=sqrt(r)) {if(i%r!=0) i++; else return 0; } return 1; } unsigned long syz(unsigned long r) {unsigned long i=2; while(i<=sqrt(r)) {if(i%r!=0) i++; else r=r/i; } return r; } unsigned long pf(unsigned long a,unsigned long b,unsigned long r) {unsigned long z=1; while(b!=0) { if(b%2==0) b=b/2; a=(a*a)%r; } else { b=b-1; z=(z*a)%r; } } return z; } unsigned long mods(unsigned long n,unsigned long r,unsigned long a) { int x=5;//? unsigned long f=1,g=x*a,y=n,h; while(y!=0) { if(y%2==0) { y=y/2; h=g*g; g=h%(unsigned long)(pow(x,r)-1); } else { y=y-1; h=f*g; f=h%(unsigned long)(pow(x,r)-1); } } return f; } void main() { unsigned long a=1; int x=5; unsigned long n; printf("输入一个整数n="); scanf("%lu",&n); if(n<2) {printf("请输入一个大于1的整数!\n");exit(0);} if(cf(n)==1) { printf("%lu是一个合数!\n",n); exit(0); } else if(cf(n)==0) { unsigned long r=2; while(r { if(gcd(n,r)!=1) { printf("% lu是一个合数\n",n); exit(0); } if(test(r)==1) { unsigned long q; q=syz(r-1); if(q>=4*sqrt(r)*(unsigned long)(log(n)/log(2))&&pf(n,(r-1)/q,r)!=1) break; } r=r+1; } for(a=1;a<=2*sqrt(r)*((unsigned long)(log(n)/log(2)));a++) { if(mods(n,r,a)!=(((unsignedlong)pow(x,n)-a)%((unsigned long)pow(x,r)-1))) { printf("%lu是一个素数\n",n); break; exit(0); } {printf("%lu是一个合数\n",n);break;} } } } 结果： 输入13 输出素数 输入56 输出合数 4结束语 该文介绍了AKS算法，并用C语言对其进行了实现。由于比目前广泛使用的素性测试方法运行速度慢的原因，使得AKS还不能得到实际的应用。然而，普遍认为许多研究者会致力于AKS算法的改进工作，减少算法运行所需的时间花费，使得算法大为改善。从而就密码学意义而言，尤其是在某些需要大的素数而又不允许发生任何错误的情况下，使其优于当前用于 鉴定素数的通用算法。 参考文献 [1]M Agrawal，N Kayal，N Saxena．Primes is in P．http://www.cse.iitk.ac.in/news/primality.pdf [2]https://www.wendangku.net/doc/733349246.html, [3]Michael Sipser. Introduction to Theory of Computation[M].PWS Publishing company,1997 [4]https://www.wendangku.net/doc/733349246.html,/glossary/page.php/CarmichaelNumber.html [5]https://www.wendangku.net/doc/733349246.html, [6] 谢希仁．计算机网络(第2版)[M]．北京：电子工业出版社，2001．251—277． [7] NIST．NIST的AF-q算法评估报告[EB/OL]．https://www.wendangku.net/doc/733349246.html,，2001． 附：作者姓名：马云涛单位：西南交通大学交通运输学院地址：四川省成都市二环路北一段111号邮编：610031 电话：158******** 邮箱：myt2681@https://www.wendangku.net/doc/733349246.html, 作者简介：马云涛1972出生、男、安徽淮南人、工程师、硕士学位