AKSAKS算法及其素数判定的算法及其素数判定的C C语言实现语言实现马云涛 西南交通大学、四川 成都myt2681163.com摘要摘要：最近，印度的三个计算机科学家Manindra Agrawal、Neeraj Kayal和Nitin Saxena 提出了一个称为AKS的算法。使用这个算法证明了可在多项式时间内对一个整数是否为素数 进行确定性的判定，从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理 论的研究与发展具有重要意叉。由于现代密码学正是建立在整数分解理论和计算复杂性理 论的基础之上，因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐 述。关键词：AKS算法 现代密码学 RSA算法AKS algorithm and its prime numbers to determine by the C program languageMa Yun Tao Southwest Jiaotong University , Chengdu Sichuan myt2681163.comAbstract： 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 timeSo，they have cracked an age- old mathematical problemThe result has important significance to research and development in both number theory and computational complexity theoryBecause 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 attentionIt will be discussed in this paper Keywords：AKS algorithm，Modem cryptography，RSA algorithm1引引 言言 很久以来，素数问题是一个使得很多数学家着迷的问题。素数就是一个除了l和它自 身以外不能被其它数整除的数。素数的一个基本问题是如何有效地确定一个数是否是一个 素数，即素性测试问题。素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际 中也是非常重要的。例如，很多现代密码学应用通常需要确定一个几百位的素数。如果不 采用一些专门有效的方法，即使人们使用运行速度最快的计算机来测试一个l00位的十进制 整数，那么花费的时间将超过宇宙存在的时间。 数学家尝试设计对素数的有效测试已经长达两千多年了。Eratosthenes筛法是对于所 有素数都有效的最古老的算法，然而它的时间复杂性是输入规模的幂指数，因此在实际中 使用它是不合适的。l7世纪的Fermat小定理是一些有效素性测试算法的起点，但其逆定理 是不满足的。上世纪80年代，这个领域的普遍观点是应该存在一个用于素性测试的确定的 多项式时间算法，但没有人能给出证明。当前，已经确立了一些素性测试算法，但是它们 都存在一些问题。一些算法是非常快速的，但是这些算法会以很小的概率产生一个错误结果；另一些算法是有条件的，如使用了未证明的假设；还有一些算法是确定的也是无条件 的，但不能在多项式时间内完成。因此，设计一个在多项式时间内每次都给出一个正确回 答的有效算法在计算机科学和数学中都是一个挑战。多年来，研究者们已经尝试了很多方 法，包括使用了一些复杂的数学技术，但没有一个成功。 然而，到了2002年8月这一情况有了改变。Manindra Agrawal教授和他的两个学生 Neeraj Kayal，Nitin Saxena设计了一个被称为AKS的算法，该算法是一个用于素性测试的 多项式时间的确定算法。这一结果被认为是这一领域的一个主要突破。一些权威认为这个 算法将产生广泛的影响，而最直接的就是对整数理论和计算复杂性理论的影响。由于现代 密码学正是以整数分解理论和计算复杂性理论为基础，因此AKS 算法对现代密码学的影响 引起了人们的关注。RSA算法是现代密码学中应用最为广泛的一个算法， 同时它既可用于 加密，又可用于数字签名。2AKS 算法简介算法简介 Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技 术研究所开发设计了AKS算法。AKS算法证明了可以应用一个确定的算法在输入规模的多项 式时间内决定一个整数是否为素数的问题，而没有使用任何未证明的数学假定。下面是AKS 算法的简要描述。 Input : integer n11.If (n=ab for aN and b1), output composite. 2.Find the smallest r such that Or(n)log2n. 3.If 1 #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=4*sqrt(r)*(unsigned long)(log(n)/log(2) 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算法的改进工作，减少算法运行所需的时间花费，使得算法大为改善。从而就密码学 意义而言，尤其是在某些需要大的素数而又不允许发生任何错误的情况下，使其优于当前用于鉴定素数的通用算法。 参考文献参考文献 1M Agrawal，N Kayal，N SaxenaPrimes is in Phttp:/www.cse.iitk.ac.in/news/primality.pdf 2http:/www.rsasecurity.com 3Michael Sipser. Introduction to Theory of ComputationM.PWS Publishing company,1997 4http:/primes.utm.edu/glossary/page.php/CarmichaelNumber.html 5http:/mathworld.wolfram.com 6 谢希仁计算机网络(第2版)M北京：电子工业出版社，2001251277 7 NISTNIST的AF-q算法评估报告EB/OLhttp:/gains.nist.gov，2001附：作者姓名作者姓名：马云涛 单位单位：西南交通大学交通运输学院 地址地址：四川省成都市二环路北一段 111 号邮编邮编：610031 电话电话：15882057223 邮箱：邮箱：myt2681163.com作者简介作者简介：马云涛 1972 出生、男、安徽淮南人、工程师、硕士学位