关于素数测试的问题
在The Agrawal -Kayal -Saxena Test的素数测试中Input: Integer n > 1
if (n has the form ab with b > 1) then output COMPOSITE;
r := 2;
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE;
if (r is prime greater than 2) then {
let q be the largest factor of r-1;
if (q > 4sqrt(r)log n) and (n^[(r-1)/q] is not 1 (mod r)) then
break;
}
r := r + 1;
}
for a := 1 to 2sqrt(r)log n {
if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE;
}
output PRIME;
这句：
if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE;
应该如何理解？ 难道是分别用两个数对取模？
还是对应取模? 本帖最后由 wayne 于 2010-1-21 10:23 编辑
2# 无心人
http://upload.wikimedia.org/math/c/e/c/cec4ba46c9f923e710ea06738a21f5dc.png
http://en.wikipedia.org/wiki/AKS_primality_test
页:
[1]