aks算法及其素数判定的c语言实现

《aks算法及其素数判定的c语言实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AKS算法及其素数判定的C语言实现摘要：最近，印度的三个计算机科学家ManindraAgrawal、NeerajKayal和NitinSaxena提出了一个称为AKS的算法。使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定，从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意叉。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上，因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。关键词：AKS算法现代密码学RSA算法AKSalgorithmanditsprimenumberstodeterminebyth

2、eCprogramlanguage百科词典      Loading.......同反义词       相关例句       英英解释      Abstract：Recently，threecomputerscientistsManindraAgrawal，NeerajKayalandNitinSaxenainIndiapresentalgorithmcalledAKS．Bythisalgorithmtheygiveaproofthatitispossibletodetermineifanumberisaprimeinpolynomialtime．So，theyhavecrackeda

3、nage-oldmathematicalproblem．Theresulthasimportantsignificancetoresearchanddevelopmentinbothnumbertheoryandcomputationalcomplexitytheory．Becausemoderncryptographyisbasedonthetheoryofintegerfactoringandthecomputationalcomplexitytheory，theeffectofthisalgorithmtomoderncryptographyhasbeenpaidsignifica

4、ntattention．Itwillbediscussedinthispaper．Keywords：AKSalgorithm，Modemcryptography，RSAalgorithm1引言很久以来，素数问题是一个使得很多数学家着迷的问题。素数就是一个除了l和它自身以外不能被其它数整除的数。素数的一个基本问题是如何有效地确定一个数是否是一个素数，即素性测试问题。素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际中也是非常重要的。例如，很多现代密码学应用通常需要确定一个几百位的素数。如果不采用一些专门有效的方法，即使人们使用运行速度最快的计算机来测试一个l00位的十进制整数，那么花

5、费的时间将超过宇宙存在的时间。数学家尝试设计对素数的有效测试已经长达两千多年了。Eratosthenes筛法是对于所有素数都有效的最古老的算法，然而它的时间复杂性是输入规模的幂指数，因此在实际中使用它是不合适的。l7世纪的Fermat小定理是一些有效素性测试算法的起点，但其逆定理是不满足的。上世纪80年代，这个领域的普遍观点是应该存在一个用于素性测试的确定的多项式时间算法，但没有人能给出证明。当前，已经确立了一些素性测试算法，但是它们都存在一些问题。一些算法是非常快速的，但是这些算法会以很小的概率产生一个错误结果；另一些算法是有条件的，如使用了未证明的假设；还有一些算法是确定的也是无条件

6、的，但不能在多项式时间内完成。因此，设计一个在多项式时间内每次都给出一个正确回答的有效算法在计算机科学和数学中都是一个挑战。多年来，研究者们已经尝试了很多方法，包括使用了一些复杂的数学技术，但没有一个成功。然而，到了2002年8月这一情况有了改变。ManindraA．grawal教授和他的两个学生NeerajKayal，NitinSaxena设计了一个被称为AKS的算法，该算法是一个用于素性测试的多项式时间的确定算法。这一结果被认为是这一领域的一个主要突破。一些权威认为这个算法将产生广泛的影响，而最直接的就是对整数理论和计算复杂性理论的影响。由于现代密码学正是以整数分解理论和计算复杂性理

7、论为基础，因此AKS算法对现代密码学的影响引起了人们的关注。RSA算法是现代密码学中应用最为广泛的一个算法，同时它既可用于加密，又可用于数字签名。1AKS算法简介ManindraAgrawal教授和他的两个学生NeerajKayal和NitinSaxena在坎普尔印度技术研究所开发设计了AKS算法。AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题，而没有使用任何未证明的数学假定。下面是AKS