AKS素性测试
编辑AKS 素数测试是一种确定性算法,用于确定自然数在多项式时间内是否为素数。
该算法后来被其他人改进,与所有以前已知的多项式素数证明算法有显着不同:它不建立在任何未经证实的假设(如广义黎曼猜想)上来证明多项式运行时间——基于的长度输入值。 原算法的渐近运行时间为 O ( ( log n ) 7 .5 + ε ) ,其中 n 是要测试的数字, O 是朗道符号,而 ε 是任意小的正数。
算法
编辑为了测试素数,让数字 n >; 1 。 此外,令 a , b , r 为自然数。
1:如果 n = a 对于 a b >; 1 返回复合;2: r = min{ r | 命令(n)> log(n) };3: 如果 1 < gcd(a,n) < n 对于某些 a ≤ r 返回 COMPOSITE;4:如果 n ≤ r 返回 PRIM;5:对于 a = 1 到 sqrt(phi(r))*log(n) do6:如果 (X+a) ≢ X+a ( mod (X−1), n) return COMPOSITE;7: 返回 PRIM;
运行时行为
该算法事实上在有限环 ( ( Z / ( n ) ) ) / ( X r − 1 ) 有 n ⋅ r 个元素。
考虑同余 ≡ ( mod ( X r − 1 ) )在多项式环 Z中,将求幂 ( X + a ) n 的单项式集合减少为 { X 0 , X 1 , … , X r − 1 } 。 考虑同余 ≡ ( mod n ) 将所得系数的位数限制为 log n 。
在 Agrawal、Kayal 和 Saxena 之后
编辑在发现后的几个月内,出现了新的变体,它们将 AKS 速度提高了几个数量级。 由于存在大量变体,Crandall 和 Papadopoulos 在他们的论文 On the implementation of AKS-class primality tests(2003 年 3 月)中提到了 AKS 算法类而不是 AKS-算法。
内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/342210/