我正在实现ntruencrypt算法,根据ntru教程,一个多项式f有一个逆g,这样f*g=1 mod x,基本上多项式乘以它的逆约化模x得到1。我得到了这个概念,但在他们提供的一个例子中,一个多项式
f = -1 + X + X^2 - X4 + X6 + X9 - X10
我们将其表示为数组
[-1,1,1,0,-1,0,1,0,0,1,-1]
有一个反义词
g
属于
[1,2,0,2,2,1,0,2,1,2,0]
所以当我们把它们相乘并把结果模减到3时,我们得到1,但是当我使用NTRU算法进行相乘和减小时,我们得到-2。
这是我用java编写的乘法算法:
public static int[] PolMulFun(int a[],int b[],int c[],int N,int M)
{
for(int k=N-1;k>=0;k--)
{
c[k]=0;
int j=k+1;
for(int i=N-1;i>=0;i--)
{
if(j==N)
{
j=0;
}
if(a[i]!=0 && b[j]!=0)
{
c[k]=(c[k]+(a[i]*b[j]))%M;
}
j=j+1;
}
}
return c;
}
它以多项式a为基础,乘以b,再求出c的结果,n表示多项式的阶数+1,在n=11以上的例子中,m表示复用模,在3以上的例子中。
为什么我得到-2而不是1?
