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

• 作者: 朱文余
• 来源期刊: 四川大学学报（自然科学版）
• 学科: 数学
• 关键词: 素数 合数 素数判定 多项式时间算法
• 年，卷（期）: 2005,（3）
• 页码范围: 459-466
• 页数: 8页
• 分类号: O156.2
• 字数: 4233字
• 语种: 中文
• DOI: 10.3969/j.issn.0490-6756.2005.03.006

摘要

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