python - 在 SymPy 多项式中以 p 为模改变系数
问题描述
这学期我在研究生院上了一门密码学课程,其中一个主题是 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
按降序排列)。
现在,我想f_poly
在卷积多项式环中找到 的逆多项式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
我得到的答案在模数上是正确的,但我认为 SymPyinvert
正在将一些系数更改为负变体,而不是留在模内。
有什么办法可以更新这个多项式的系数,使其模数只有正系数,或者这只是 SymPy 函数的产物?我想保留 SymPyPoly
格式,以便以后可以使用它的一些嵌入式功能。任何见解将不胜感激!
解决方案
这似乎取决于有限域对象如何在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)
现在你会得到你想要的多项式:
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
推荐阅读
- python-xarray - 读取远程数据集时的 xarray MissingDimensionsError (NBM)
- java - 导入 javax.persistence.EntityManager 的问题;
- webrtc - Webrtc:如何在不提前知道号码的情况下协商曲目?
- npm-install - mac os 上的 opencv4nodejs 安装脚本失败(make[1]: *** [modules/sfm/src/libmv/libmv/multiview/CMakeFiles/multiview.dir/all] 错误 2)
- amazon-web-services - 让 Jenkins 在主机/jenkins 上聆听
- node.js - 如何使用 Nestjs 中的请求范围提供程序动态创建和关闭数据库连接?
- sql - 添加列并在列不存在时更新数据时出错
- asp.net - 在本地和云中运行的企业应用程序的 Google 登录实施
- php - 无法在数据库中插入多个文件名
- python - Flutter 无法处理后端 Flask 的 http 请求,现在该怎么办?