AKS算法其素数判定C语言实现.doc

.页眉. .页脚. AKS 算法及其素数判定的 C 语言实现马云涛西南交通大学、四川成都 m yt2681@ 摘要: 最近,印度的三个计算机科学家 Manindra Agrawal 、 Neeraj Kayal 和 Nitin Saxena 提出了一个称为 AKS 的算法。使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定, 从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意叉。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上,因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。关键词: AKS 算法现代密码学 RSA 算法 AKS algorithm and its prime numbers to determine by the C program language Ma Yun T ao Southwest Jiaotong University , Chengdu Sichuan m yt2681@ Abstract : Recently , puter 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 ifa number isa 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 theo ry plexity theory . Because modern cryptography is based on the theory of integer factoring and plexity theory , the ef fect 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 位的十进制整数, 那么花费的时间将超过宇宙存在的时间。数学家尝试设计对素数的有效测试已经长达两千多年了。 Eratosthe