问NTRUEncrypt中多项式的模化简

EN

我正在实现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 of [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指定polynomials+1的程度，在上面的例子中N=11；M是在上面的例子中的模3。

为什么我得到的是-2而不是1？