Reducción modular de polinomios en NTRUEncrypt

Question

Estoy implementar el algoritmo de NTRUEncrypt, según un tutorial NTRU, un polinomio f tiene una inversa g tal que f * g = 1 mod x, básicamente el polinomio multiplica por su inversa reducida modulo x da 1. I obtener el concepto, pero en un ejemplo que proporcionan, una f = -1 + X + X^2 - X4 + X6 + X9 - X10 polinómica que vamos a representar como el [-1,1,1,0,-1,0,1,0,0,1,-1] matriz tiene un g inversa de [1,2,0,2,2,1,0,2,1,2,0], por lo que cuando se multiplican ellos y reducimos el resultado de módulo 3 obtenemos 1, sin embargo, cuando se utiliza el algoritmo NTRU para multiplicar y reducirlos consigo -2.

Aquí está mi algoritmo para multiplicar los escritos en 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;

}

basicall tomada en una y lo multiplica B polinomio, Resturns teh resultado en C, N especifica el grado de los polinomios + 1, en teh ejemplo anterior N = 11; y M es el módulo reuction, en teh exampel arriba 3.

¿Por qué recibo -2 y no 1?

Answer 1

-2 == 1 mod 3, por lo que el cálculo está muy bien, pero parece que el módulo (resto) operador de Java tiene un rango de salida de [-n .. n] para mod n+1, en lugar de la [0..n] matemática estándar.

Sólo se adhieren una if (c[k] < 0) c[k] += M; después de su línea de c[k]=...%M, y que debe estar bien.

Edit:. En realidad, mejor dicho de la derecha al final de la más externa (k) para-loop