| AKS算法及关于它的一种改进算法的实现分析 |
| |
| 引用本文： | 朱文余.AKS算法及关于它的一种改进算法的实现分析[J].四川大学学报(自然科学版),2005,42(3):459-466. |
| |
| 作者姓名： | 朱文余 |
| |
| 作者单位： | 四川大学数学学院,成都,610064;现代通信国家重点实验室,成都,810信箱,610041 |
| |
| 基金项目： | 现代通信国家重点实验室基金项目(51436010505SC0101) |
| |
| 摘 要： | 2002年，Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题，他们给出了一个算法(简称AKS算法)，该算法对输入整数是素数还是合数进行判断。它是一个确定的多项式时间算法．后来许多科学家对该算法进行了改进，其中一个比较好的改进是由Bernstein给出的(简称Bernstein算法)．作者详细分析了这两种算法，利用C语言实现了这两种算法，并进行了比较，找出了真正需要用到AKS算法和Bemstein算法来判断其为素数和合数的最小数，并估计出所需要的运行时间．
|
| 关 键 词： | 素数 合数 素数判定 多项式时间算法 |
| 文章编号： | 0490-6756(2005)03-0459-08 |
Analyzing the AKS Algorithm and It's an Improvement Algorithm in Detail |
| |
| ZHU Wen-yu.Analyzing the AKS Algorithm and It''''s an Improvement Algorithm in Detail[J].Journal of Sichuan University (Natural Science Edition),2005,42(3):459-466. |
| |
| Authors: | ZHU Wen-yu |
| |
| Institution: | ZHU Wen-yu~ |
| |
| Abstract: | In 2002, Agrawal?Kayal and Saxena presented a remarkable algorithm (the AKS algorithm). It is the deterministic polynomial-time primality testing algorithm that determines whether an input number is prime or composite. After the AKS algorithm is posed, many researchers improved the AKS algorithm. One of the better improvements due to Bernstein (the Bernstein algorithm). In this paper, the author analyzes the two algorithm in detail and implements the two algorithm for some integers and compare them by using C program on machine, and finds out the smallest prime number and composite number that are need to using the AKS algorithm and the Bernstein algorithm, and shows the predicted CPU time. |
| |
| Keywords: | prime composite primality testing polynomial-time algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
