代码之家  ›  专栏  ›  技术社区  ›  J Chapman

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

  •  2
  • J Chapman  · 技术社区  · 7 年前

    我目前正在尝试编写自己的AKS算法实现。可以看到这方面的伪代码(直接取自论文“PRIMES is in P”) here

    我正在努力解决的部分是 if 第5行的声明。这需要我们检查

    (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和Symphy包的语句,以及以下代码

    if(sym.div(sym.div(mod_zero, x**r - 1)[1], n)[1] == 0):
         print("Congruent")
    
    1 回复  |  直到 7 年前
        1
  •  1
  •   user6655984 user6655984    7 年前

    您的解释 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代码没有那么优雅,但要快一个数量级。