Modular Reduction of Polynomials in NTRUEncrypt

Question

Hello everyone. 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?

Answer 1

-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] for mod n+1, instead of the standard mathematical [0..n].

Just stick an if (c[k] < 0) c[k] += M; after your c[k]=...%M line, and you should be fine.

Edit: actually, best to put it right at the end of the outermost (k) for-loop.