Skip to main content
 首页 » 编程设计

python之在 SymPy 多项式中更改系数模 p

2024年12月31日8Free-Thinker

我本学期在研究生院学习了密码学类(class),我们涵盖的主题之一是 NTRU。我试图用纯 Python 编写代码,这纯粹是一种爱好。当我试图找到一个多项式的逆模 p(在这个例子中 p = 3)时,SymPy 总是返回负系数,而我想要的是严格的正系数。这是我的代码。我会解释我的意思。

import sympy as sym 
from sympy import GF 
 
def make_poly(N,coeffs): 
    """Create a polynomial in x.""" 
    x = sym.Symbol('x') 
    coeffs = list(reversed(coeffs)) 
    y = 0 
    for i in range(N): 
        y += (x**i)*coeffs[i] 
    y = sym.poly(y) 
    return y 
 
N = 7 
p = 3 
q = 41 
f = [1,0,-1,1,1,0,-1] 
 
f_poly = make_poly(N,f) 
 
x = sym.Symbol('x') 
 
Fp = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(p)) 
Fq = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(q)) 
 
print('\nf =',f_poly) 
print('\nFp =',Fp) 
print('\nFq =',Fq) 

在这段代码中,f_poly是一个次数最多为6的多项式(次数最多为N-1),其系数来自列表 f(f中的第一个条目是x的最高次方的系数,按降序排列)。

现在,我想在卷积多项式环Rp = (Z/pZ)[x]/(x^N - 1)(Z/pZ)[x](与 q 类似)。底部打印语句的输出是:

f = Poly(x**6 - x**4 + x**3 + x**2 - 1, x, domain='ZZ') 
Fp = Poly(x**6 - x**5 + x**3 + x**2 + x + 1, x, modulus=3) 
Fq = Poly(8*x**6 - 15*x**5 - 10*x**4 - 20*x**3 - x**2 + 2*x - 4, x, modulus=41) 

这些多项式的模数是正确的,但我希望到处都有正系数,因为稍后在算法中涉及一些中心提升,所以我需要有正系数。结果应该是

Fp = x^6 + 2x^5 + x^3 + x^2 + x + 1 
Fq = 8x^6 + 26x^5 + 31x^4 + 21x^3 + 40x^2 + 2x + 37 

我得到的答案在模数方面是正确的,但我认为 SymPy 的 invert 正在将一些系数更改为负变体,而不是留在模数内。

有什么方法可以更新这个多项式的系数,使模数中只有正系数,或者这只是 SymPy 函数的产物?我想保留 SymPy Poly 格式,以便以后可以使用它的一些嵌入式功能。任何见解将不胜感激!

请您参考如下方法:

这似乎取决于有限域对象在 GF 中的实现方式。在给定模数周围“包装”整数。默认行为是 symmetric ,这意味着任何整数 x为此 x % modulo <= modulo//2映射到 x % modulo , 否则映射到 (x % modulo) - modulo .所以GF(10)(5) == 5 ,而 GF(10)(6) == -4 .你可以制作GF始终通过传递 symmetric=False 映射到正数参数:

import sympy as sym 
from sympy import GF 
 
def make_poly(N, coeffs): 
    """Create a polynomial in x.""" 
    x = sym.Symbol('x') 
    coeffs = list(reversed(coeffs)) 
    y = 0 
    for i in range(N): 
        y += (x**i)*coeffs[i] 
    y = sym.poly(y) 
    return y 
 
N = 7 
p = 3 
q = 41 
f = [1,0,-1,1,1,0,-1] 
 
f_poly = make_poly(N,f) 
 
x = sym.Symbol('x') 
 
Fp = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(p, symmetric=False)) 
Fq = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(q, symmetric=False)) 
 
print('\nf =',f_poly) 
print('\nFp =',Fp) 
print('\nFq =',Fq) 

现在您将获得所需的多项式。 print(...) 的输出示例末尾的语句应如下所示:

f = Poly(x**6 - x**4 + x**3 + x**2 - 1, x, domain='ZZ') 
Fp = Poly(x**6 + 2*x**5 + x**3 + x**2 + x + 1, x, modulus=3) 
Fq = Poly(8*x**6 + 26*x**5 + 31*x**4 + 21*x**3 + 40*x**2 + 2*x + 37, x, modulus=41) 

主要作为供我自己引用的注释,以下是您将如何获得 Fp使用 Mathematica:

Fp = PolynomialMod[Algebra`PolynomialPowerMod`PolynomialPowerMod[x^6 - x^4 + x^3 + x^2 - 1, -1, x, x^7 - 1], 3] 

输出:

1 + x + x^2 + x^3 + 2 x^5 + x^6