AKS素性测试
AKS素性测试(又被称为Agrawal–Kayal–Saxena素性测试和Cyclotomic AKS test)是一个决定型素性测试算法 ,由三个来自印度坎普尔理工学院的计算机科学家,曼宁德拉·阿格拉瓦尔、尼拉吉·卡亚尔和尼汀·沙克谢纳,在2002年8月6日发表于一篇题为素数属于P的论文。[1]作者们因此获得了许多奖项,包含了2006年的哥德尔奖和2006年的富尔克森奖。这个算法可以在多项式时间之内,决定一个给定整数是素数或者合数。
重要性
AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的素数判定算法。先前的算法至多达到了其中三点,但从未达到全部四个。
- AKS算法可以被用于检测任何一般的给定数字是否为素数。很多已知的高速判定算法只适用于满足特定条件的素数。例如,卢卡斯-莱默检验法仅对梅森素数适用,而Pépin测试仅对费马数适用。
- 算法的最长运行时间可以被表为一个目标数字长度的多项式。ECPP和APR能够判断一个给定数字是否为素数,但无法对所有输入给出多项式时间范围。
- 算法可以确定性地判断一个给定数字是否为素数。随机测试算法,例如米勒-拉宾检验和Baillie–PSW,可以在多项式时间内对给定数字进行校验,但只能给出概率性的结果。
- AKS算法并未“仰赖”任何未证明猜想。一个反例是确定性米勒检验:该算法可以在多项式时间内对所有输入给出确定性结果,但其正确性却基于尚未被证明的广义黎曼猜想。
概念
AKS素性测试主要是基于以下定理:整数n (≥ 2)是素数,当且仅当
-
(
)
这个同余多项式对所有与n互素的整数a均成立。 这个定理是费马小定理的一般化,并且可以简单的使用二项式定理跟二项式系数的这个特征:
- ,对任何 ,当且仅当 n 是素数
来证明出此定理。
虽然说关系式 (1) 基本上构成了整个素性测试,但是验证花费的时间却是指数时间。因此,为了减少计算复杂度,AKS改为使用以下的同余多项式:
-
(
)
这个多项式与存在多项式f与g,令:
-
(
)
意义是等同的。
这个同余式可以在多项式时间之内检查完毕。这里我们要注意所有的素数必定满足此条件式(令g = 0则 (3) 等于 (1),因此符合n必定是素数)。 然而,有一些合数也会满足这个条件式。有关AKS正确性的证明包含了推导出存在一个够小的r以及一个够小的整数集合A,令如果此同余式对所有A里面的整数都满足,则n必定为素数。
历史以及运算时间
在上文引用的论文的第一版本中,作者们证明了算法的渐近时间为O 。换言之,算法使用少于n的二进制数字长度的十二次方。但是,论文证明的时间上界却过于宽松;事实上,一个被普遍相信的关于索菲热尔曼素数分布的假设如果为真,则会立即将最坏情况减至O 。
在这一发现后的几个月中,新的变体陆续出现(Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra和Pomerance 2003)并依次提高了算法的速度(以改进幅度为序)。由于这些变体的出现,Crandall和Papadopoulos在其科学论文“AKS-类素性测试的实现”(2003年三月发表)中将其称为算法的“AKS-类”。
出于对这些变体和其他回复的回应,论文“素数属于P”稍后被进行了更新,新版本包括了一个AKS算法的正规公式化表述和其正确性证明。(这一版本在数学年刊上发表。)虽然基本思想没有变化, 却被采用了新方法进行选择,而正确性证明也变得更加紧致有序。与旧证明依赖于许多不同的方法不同,新版本几乎只依赖于有限域上的分圆多项式的特征。新版本同时也优化了时间复杂度的边界到O 。通过筛法获得的其他结果可以将其进一步简化到O 。
在2005年,Carl Pomerance和H. W. Lenstra, Jr.展示了一个AKS的变体,可以在 次操作内完成测试( 是被测试数)。对于原算法的 边界而言,这是一个显著的改进。[2]
算法
整个算法的操作如下:[1]
- 输入:整数 n > 1
- 若存在整数a > 0 且b > 1 ,令 n = ab ;则输出合数
- 找出最小的 r 令 ordr(n) > log2(n).
- 若 对某些a ≤ r,1 < gcd(a,n) < n,输出合数。(gcd是指最大公约数)。
- 若 n ≤ r, 输出素数。
- 对 a = 1 到 的所有数,
- 如果 (X+a)n≠ Xn+a (mod Xr − 1,n), 输出合数。
- 输出 素数。
这里的 ordr(n)是n mod r的阶。 另外,这里的log 代表以二为底的对数, 则是r的欧拉函数。
下面说明若n是个素数,那么算法总是会返回素数:由于n是素数,步骤1和3永远不会返回合数。步骤5也不会返回合数,因为(2)对所有素数n为真。因此,算法一定会在步骤4或6返回素数。
对应地,如果n是合数,那么算法一定返回合数:如果算法返回素数,那么则一定是从步骤4或6返回。对于前者,因为n ≤ r, n必然有因子a ≤ r符合1 < gcd(a,n) < n,因此会返回合数。剩余的可能性就是步骤6,在文章[1]中,这种情况被证明不会发生,因为在步骤5中检验的多个等式可以确保输出一定是合数。
例子:n = 31为素数
- 输入:整数n = 31 > 1。
若存在整數a > 0 且b > 1 ,令 n = ab ;則輸出「合數」。 for ( b = 2; b < = log2(n); b + + ){ a = n1/b; If ( a是整數 ) 輸出「合數」; } // a = n1/2...n1/4 = {5.568, 3.141, 2.360},計算結果不是整數
找出最小的 r 令 ordr(n) > log2(n)。 nextR = True; r = 1; while ( nextR = = True ) { r + + ; nextR = False for ( k = 1;(!nextR) &&k ≤ log2(n); k + + ){ nextR = (nk % r = = 1 || nk % r = = 0); } } // 計算結果為:r = 29
若 對某些a ≤ r,1 < gcd(a,n) < n,輸出「合數」。 for ( a = r; a > 1; a-- ){ If ( 1 < gcd(a,n) < n ) 輸出「合數」; } // gcd(29,31) = 1, gcd(28,31) = 1, ..., gcd(2,31) = 1,計算結果為找不到符合的a使得1 < gcd(a,n) < n為真
若 n ≤ r, 輸出「質數」。 If ( n ≤ r ) 輸出「質數」; // 31 > 29,計算結果n比r大
對 a = 1 到 的所有數, 如果 (X + a)n≠ Xn + a (mod Xr − 1,n), 輸出「合數」。 for ( a = 1; a ≤ , a + + ) if ( ((X + a)n-(Xn + a)) % (Xr−1,n) ≠ 0 ) 輸出「合數」。 } / * * * (x + a)31 % (x29-1,31) = (((x + a)29 % (x29-1,31)) * (x + a)2 % 31) % (x29-1,31) = ((1 + a29 + 29a28x + (406 % 31)a27x2 + (3654 % 31)a26x3 + (23751 % 31)a25x4 + (118755 % 31)a24x5 + (475020 % 31)a23x6 + (1560780 % 31)a22x7 + (4292145 % 31)a21x8 + (10015005 % 31)a20x9 + (20030010 % 31)a19x10 + (34597290 % 31)a18x11 + (51895935 % 31)a17x12 + (67863915 % 31)a16x13 + (77558760 % 31)a15x14 + (77558760 % 31)a14x15 + (67863915 % 31)a13x16 + (51895935 % 31)a12x17 + (34597290 % 31)a11x18 + (20030010 % 31)a10x19 + (10015005 % 31)a9x20 + (4292145 % 31)a8x21 + (1560780 % 31)a7x22 + (475020 % 31)a6x23 + (118755 % 31)a5x24 + (23751 % 31)a4x25 + (3654 % 31)a3x26 + (406 % 31)a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31) = ((1 + a29 + 29a28x + 3a27x2 + 27a26x3 + 5a25x4 + 25a24x5 + 7a23x6 + 23a22x7 + 9a21x8 + 21a20x9 + 11a19x10 + 19a18x11 + 13a17x12 + 17a16x13 + 15a15x14 + 15a14x15 + 17a13x16 + 13a12x17 + 19a11x18 + 11a10x19 + 21a9x20 + 9a8x21 + 23a7x22 + 7a6x23 + 25a5x24 + 5a4x25 + 27a3x26 + 3a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31) = ((1 + 2 * 29 + 3) % 31)a2 + a31 + ((2 + 29) % 31)ax + ((29 + 2 * 1) % 31)a30x + x2 + ((3 + 2 * 29 + 1) % 31)a29x2 + ((27 + 2 * 3 + 29) % 31)a28x3 + ((5 + 2 * 27 + 3) % 31)a27x4 + ((25 + 2 * 5 + 27) % 31)a26x5 + ((7 + 2 * 25 + 5) % 31)a25x6 + ((23 + 2 * 7 + 25) % 31)a24x7 + ((9 + 2 * 23 + 7) % 31)a23x8 + ((21 + 2 * 9 + 23) % 31)a22x9 + ((11 + 2 * 21 + 9) % 31)a21x10 + ((19 + 2 * 11 + 21) % 31)a20x11 + ((13 + 2 * 19 + 11) % 31)a19x12 + ((17 + 2 * 13 + 19) % 31)a18x13 + ((15 + 2 * 17 + 13) % 31)a17x14 + ((15 + 2 * 15 + 17) % 31)a16x15 + ((17 + 2 * 15 + 15) % 31)a15x16 + ((13 + 2 * 17 + 15) % 31)a14x17 + ((19 + 2 * 13 + 17) % 31)a13x18 + ((11 + 2 * 19 + 13) % 31)a12x19 + ((21 + 2 * 11 + 19) % 31)a11x20 + ((9 + 2 * 21 + 11) % 31)a10x21 + ((23 + 2 * 9 + 21) % 31)a9x22 + ((7 + 2 * 23 + 9) % 31)a8x23 + ((25 + 2 * 7 + 23) % 31)a7x24 + ((5 + 2 * 25 + 7) % 31)a6x25 + ((27 + 2 * 5 + 25) % 31)a5x26 + ((3 + 2 * 27 + 5) % 31)a4x27 + ((29 + 2 * 3 + 27) % 31)a3x28 = a31 + x2 (x31 + a) % (x29-1,31) = a + x2 (a31 + x2)-(a + x2) = a31-a (131-1) % 31 = 0, (231-2) % 31 = 0, (331-3) % 31 = 0, ..., (2631-26) % 31 = 0,計算結果為找不到符合的a使得(X + a)n≠ Xn + a (mod Xr − 1,n)為真 * * * /
輸出「質數」。 31必為質數。
注释
- ^ 1.0 1.1 1.2 Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P (页面存档备份,存于互联网档案馆)", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
- ^ 亨德里克·伦斯特拉 and Carl Pomerance, "Primality Testing with Gaussian Periods (页面存档备份,存于互联网档案馆)", preliminary version July 20, 2005.
延伸阅读
- Dietzfelbinger, Martin. Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P. Lecture Notes in Computer Science 3000. Berlin: 施普林格科学+商业媒体. 2004. ISBN 3-540-40344-2. Zbl 1058.11070.
外部链接
- 埃里克·韦斯坦因. AKS Primality Test. MathWorld.
- R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
- Article by Borneman, containing photos and information about the three Indian scientists(页面存档备份,存于互联网档案馆) (PDF)
- Andrew Granville: It is easy to determine whether a given integer is prime(页面存档备份,存于互联网档案馆)
- The Prime Facts: From Euclid to AKS(页面存档备份,存于互联网档案馆), by Scott Aaronson (PDF)
- The PRIMES is in P little FAQ(页面存档备份,存于互联网档案馆) by Anton Stiglic
- 2006 Gödel Prize Citation
- 2006 Fulkerson Prize Citation(页面存档备份,存于互联网档案馆)
- The AKS "PRIMES in P" Algorithm Resource(页面存档备份,存于互联网档案馆)
- Grime, Dr. James. Fool-Proof Test for Primes - Numberphile (video). 布雷迪·哈兰. [2018-05-10]. (原始内容存档于2018-03-23). [the video describes the exponential time relation (1), which it calls AKS]