ntruencrypt中多项式的模块化减少

Question

我正在实现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], ，因此，当我们乘以它们并减少结果modulo 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中占用b，n指定了多项式+1的程度，在n = 11上方的示例中； M是Recuction Modulo，在3上方的exampel中。

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

Answer 1

-2 == 1 mod 3，因此计算很好，但是看来Java的模量（剩余）操作员的输出范围为 [-n .. n] 为了 mod n+1, ，而不是标准数学 [0..n].

只是坚持一个 if (c[k] < 0) c[k] += M; 在你之后 c[k]=...%M 行，你应该没事的。

编辑：实际上，最好将其放在最外面的末尾（k）for-loop。