我目前正在尝试编写自己的 AKS 算法实现。伪代码(直接取自论文“PRIMES 在 P 中”)可以看到 here .
我纠结的部分是第 5 行 if 语句中的代码。这需要我们检查是否
(x+a)^n = x^n + a ( mod x^r - 1, n )
有谁知道我该怎么做(在 python 中)?我相信这种同余等价于说存在多项式 q(x) 和 r(x) 这样
f(x) = g(x) + (x^r - 1) * q(x) + n * r(x)
虽然我不确定这一点。
我尝试使用 python 和带有以下代码的 sympy 包复制此 if 语句
if(sym.div(sym.div(mod_zero, x**r - 1)[1], n)[1] == 0):
print("Congruent")
请您参考如下方法:
如果 g 被理解为为零,且 q 和 r 具有整数系数。但这实际上是两个步骤:将多项式除法的余数除以 (x^r - 1),然后将 mod n 应用于系数。
在 SymPy 术语中,比较是
trunc(rem((x + a)**n -(x**n + a), x**r - 1), n) == 0
其中 rem 求多项式余数,trunc 取系数 mod n。示例:
x = poly("x")
n = 35
r = 29
a = 7
trunc(rem((x + a)**n - (x**n + a), x**r - 1), n)
输出 Poly(14*x**25 + 7*x**10 - 7*x**5 + 14*x - 14, x, domain='ZZ')
同时,将 35 替换为 31,我们得到 Poly(0, x, domain='ZZ'),它通过了 == 0 测试。
加速
优化的一种方法是在 rem 之前也应用 trunc,以使除法之前的系数更小。
trunc(rem(trunc((x + a)**n - (x**n + a), n), x**r - 1), n)
这有点帮助。但是可以通过使用“galoistools”模块中的低级例程来实现更大幅度的加速。它们将系数作为列表进行运算,如下所示:[1, a] 是 x + a。
from sympy.polys.galoistools import gf_lshift, gf_sub, gf_add_ground, gf_pow, gf_rem
n = 35
r = 29
a = 7
f1 = gf_pow([1, a], n, n, ZZ) # (x + a)**n
f2 = gf_add_ground(gf_lshift([1], n, ZZ), a, n, ZZ) # x**n + a
g = gf_add_ground(gf_lshift([1], r, ZZ), -1, n, ZZ) # x**r - 1
print(gf_rem(gf_sub(f1, f2, n, ZZ), g, n, ZZ))
打印 [14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 28, 0, 0, 0, 14, 21] 与之前的结果一致(模 35)。
在此表示中,零多项式是 []:因此,测试可以像这样简单
if gf_rem(gf_sub(f1, f2, n, ZZ), g, n, ZZ):
print("Composite") # [] is falsy, other lists are truthy
galoistools 代码不够优雅,但速度快了一个数量级。
