基于代数整数的概率性素性测试算法

无心人

首一整系数不可约多项式$f(x)$， $a$是一个根
则有代数数域$Q[a]$，$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 [3, 9]
{
    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

nyy

不要瞎折腾了bpsw就挺好！