math - 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] ，所以当我们将它们相乘并减少结果模 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？

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 循环的末尾。