AKS算法及关于它的一种改进算法的实现分析  

Analyzing the AKS Algorithm and It's an Improvement Algorithm in Detail

作　　者：朱文余[1] 

机构地区：[1]四川大学数学学院

出　　处：《四川大学学报（自然科学版）》2005年第3期459-466,共8页Journal of Sichuan University(Natural Science Edition)

基　　金：现代通信国家重点实验室基金项目(51436010505SC0101)

摘　　要：2002年,Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题.他们给出了一个算法(简称AKS算法),该算法对输入整数是素数还是合数进行判断,它是一个确定的多项式时间算法.后来许多科学家对该算法进行了改进,其中一个比较好的改进是由Bernstein给出的(简称Bernstein算法).作者详细分析了这两种算法,利用C语言实现了这两种算法,并进行了比较,找出了真正需要用到AKS算法和Bernstein算法来判断其为素数和合数的最小数,并估计出所需要的运行时间.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.

关 键 词：素数 合数 素数判定 多项式时间算法 

分 类 号：O156.2[理学—数学]