NTRUE加密中多項式的模塊化縮減

Question

根據NTRU教程，我正在實現NTRUE加密算法，多項式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採取多項式和相乘B，resturns格蘭結果C，N指定多項式+ 1的程度，在上面的例子N = 11; M是減數模，在上面的例子中。

爲什麼我得到-2而不是1？

Answer 1

-2 == 1 mod 3，所以計算很好，但看起來Java的模數（餘數）運算符的輸出範圍爲[-n .. n]（mod n+1），而不是標準數學[0..n]。

只需在c[k]=...%M行後面加上if (c[k] < 0) c[k] += M;，你應該沒問題。

編輯：實際上，最好把它放在最外面（k）for循環的末尾。