如何检查两个多项式是否是模(h(x),n)全等的?

您的解释 f(x) = g(x) + (x^r - 1) * q(x) + n * r(x) 如果g被理解为零,并且q和r具有整数系数,则不正确。但实际上有两个步骤:将多项式的余数除以 (x^r - 1) ,然后应用 mod n 到系数。

用同义词来说,比较是

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 测验

加速

优化的一种方法是 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代码没有那么优雅,但要快一个数量级。