Modular polynomial reduction in NTRUEncrypt

Question

I implement the NTRUEncrypt algorithm, according to the NTRU tutorial, the polynomial f has an inverse g such that f * g = 1 mod x, basically the polynomial multiplied by its inverse reduced to modulo x gives 1. I get but in the example that they provide , the polynomial f = -1 + X + X^2 - X4 + X6 + X9 - X10 , which we will represent as an array [-1,1,1,0,-1,0,1,0,0,1,-1] , has the inverse g of [1,2,0,2,2,1,0,2,1,2,0] , so when we multiply them and decrease the result modulo 3, we get 1, however when I use the NTRU algorithm to multiply and reduce 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; } 

This basic value, taken in a polynomial a and multiplying it by b, returns the result c, N sets the degree of polynomials + 1 in the example above N = 11; and M is the reduction modulo, when considered above 3.

Why am I getting -2, not 1?

Answer 1

-2 == 1 mod 3, so the calculation is beautiful, but it looks like the Java module operator (residual) has an output range [-n .. n] for mod n+1 instead of the standard mathematical [0..n] .

Just insert if (c[k] < 0) c[k] += M; after the line c[k]=...%M , and everything will be fine.

Edit: In fact, it's best to put it at the end of the outermost ( k ) for the loop.