AKS算法对现代密码学的影响

The Effect of AKS Algorithm on Modern Cryptography

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

Recently,three computer scientists Manindra Agrawal,Neeraj Kayal and Nitin Saxena in India present an 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.