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

摘要：

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

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

所属期刊栏目：42

分类号：O156.2(代数、数论、组合理论)

资助基金：国家重点实验室基金51436010505SC0101

在线出版日期：2005-07-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：459-466