Модульное сокращение многочленов в NTRUEncrypt

Question

Я реализую алгоритм 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; 

} 

Он basicall взят за полиномиальное а и умножает его б, Resturns дэ результат с, N определяет степень полиномов + 1, в пример выше N = 11; и M - редукция по модулю, в примере выше 3.

Почему я получаю -2, а не 1?

Answer 1

-2 == 1 mod 3, поэтому вычисление прекрасное, но похоже, что оператор модуля Java (остаточный) имеет выходной диапазон [-n .. n] для mod n+1 вместо стандартного математического [0..n].

Просто введите if (c[k] < 0) c[k] += M; после вашей линии c[k]=...%M, и все должно быть в порядке.

Редактировать: на самом деле, лучше всего поставить его в конце самого внешнего (k) для цикла.