4

我正在实现 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 是reduction modulo，在上面3的例子中。

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

4

1 回答 1

4

-2 == 1 mod 3，所以计算很好，但似乎 Java 的模（余数）运算符的输出范围为[-n .. n]for mod n+1，而不是标准的 math [0..n]。

只要if (c[k] < 0) c[k] += M;在你的c[k]=...%M线路后面加上一个，你应该没问题。

编辑：实际上，最好把它放在最外层 ( k) for 循环的末尾。

于 2010-04-24T13:10:29.767 回答