基于代数整数的概率性素性测试算法
首一整系数不可约多项式$f(x)$， $a$是一个根则有代数数域$Q$，$p, b \in \ZZ$
若$p$是素数，则
$（a+b)^p mod p \equiv (a^p + b) mod p$
因此有以下素性测试算法
$p$ 为待测试整数
$P$ 定义为 $-1$ 和全体素数的集合
$t$ 定义为测试次数
$P_t$ 为 $P$ 前 $t$ 个元素
for m in
{
if m % 3 == 2
$f(x) = x^m + 2x + 1$
else
$f(x) = x^m + x + 1$
定义 a 是由 f(x) 确定的代数数域的一个单位元
for b in $P_t$
{
if $(a + b)^p mod p = (a^p + b) mod p$
continue
else
中断测试，返回 p 是合数
}
}
返回 p 是可能素数
m = 3, f(x) = x^3 + x + 1
(a + 3)^65537 % 65537 = 31233*a^2 + 39761*a + 20825
a^65537 % 65537 = 31233*a^2 + 39761*a + 20822
(a + 3)^65535 % 65535 = 32645*a^2 + 44301*a + 8903
a^65535 % 65535 = 52130*a^2 + 30771*a + 44255
(a + 3)^2047 % 2047 = 1350*a^2 + 410*a + 1538
a^2047 % 2047 = 918*a^2 + 803*a + 389
(a + 3)^561 % 561 = 133*a + 234
a^561 % 561 = 279*a^2 + 292*a + 117 不要瞎折腾了bpsw就挺好！
页:
[1]