NTRUEncrypt 中多项式的模约化
我正在实现 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] 具有 [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？
I'm implementing the NTRUEncrypt algorithm, according to an NTRU tutorial, a polynomial f has an inverse g such that f*g=1 mod x, basically the polynomial multiplied by its inverse reduced modulo x gives 1. I get the concept but in an example they provide, a polynomial f = -1 + X + X^2 - X4 + X6 + X9 - X10 which we will represent as the array [-1,1,1,0,-1,0,1,0,0,1,-1] has an inverse g of [1,2,0,2,2,1,0,2,1,2,0], so that when we multiply them and reduce the result modulo 3 we get 1, however when I use the NTRU algorithm for multiplying and reducing them I get -2.
Here is my algorithm for multiplying them written in 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;
}
It basicall taken in polynomial a and multiplies it b, resturns teh result in c, N specifies the degree of the polynomials+1, in teh example above N=11; and M is the reuction modulo, in teh exampel above 3.
Why am I getting -2 and not 1?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
-2 == 1 mod 3，所以计算没问题，但是 Java 的模（余数）运算符对于
mod n+ 的输出范围为，而不是标准数学[-n .. n]1[0..n]。只需在
c[k]=...%M行后面添加if (c[k] < 0) c[k] += M;即可，然后你应该没事的。编辑：实际上，最好将其放在最外层 (
k) for 循环的末尾。-2 == 1 mod 3, so the calculation is fine, but it appears that Java's modulus (remainder) operator has an output range of
[-n .. n]formod n+1, instead of the standard mathematical[0..n].Just stick an
if (c[k] < 0) c[k] += M;after yourc[k]=...%Mline, and you should be fine.Edit: actually, best to put it right at the end of the outermost (
k) for-loop.