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

Question

我这学期在研究生院上了一门密码学课程，我们讲过的主题之一是 NTRU。我试图用纯粹的 Python 编写代码，这纯粹是一种爱好。当我试图找到多项式的逆 modulo p（在这个例子中 p = 3）时，SymPy 总是 returns 负系数，而我想要的是严格的正系数。这是我的代码。我会解释我的意思。

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中是[=17=的最高次方的系数，按降序排列]。

现在，我想在卷积多项式环Rp = (Z/pZ)[x]/(x^N - 1)(Z/pZ)[x]中找到f_poly的逆多项式（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)

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

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

我得到的答案在 modulus 中是正确的，但我认为 SymPy 的 invert 正在将一些系数更改为负变体，而不是留在 mod.

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

Answer 1

这似乎取决于有限域对象如何在给定模数周围的 GF "wraps" 整数中实现。默认行为是 symmetric，这意味着 x 的任何整数 x % modulo <= modulo//2 映射到 x % modulo，否则映射到 (x % modulo) - modulo。所以 GF(10)(5) == 5，而 GF(10)(6) == -4。您可以通过传递 symmetric=False 参数使 GF 始终映射到正数：

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)

现在你会得到你想要的多项式：

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)

主要作为供我自己参考的注释，以下是使用 Mathematica 获得 Fp 的方法：

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

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

Changing coefficients modulo p in a SymPy polynomial

python

sympy

python-3.x

polynomials