NTRUEncrypt에서 다항식의 모듈 환원

Question

NTRU 튜토리얼에 따르면 NTRU 튜토리얼에 따르면 다항식 f는 f * g = 1 mod x, 기본적으로 다항식에 역 모듈로 x 나는 개념을 얻는다. 그러나 예제에서 우리가 제공하는 다항식 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; 

} 

이것은 다항식 A의 촬영 및 b를 승산 basicall가 C로 TEH 결과 resturns, N은에서는, 다항식 + 1 정도를 지정 위의 예 N = 11; M은 3보다 큰 위도의 모듈로입니다.

왜 -2가 아닌 1이됩니까?

Answer 1

-2 == 1 mod 3이므로 계산은 문제가 없지만 Java 모듈러스 (나머지) 연산자의 표준 출력은 [0..n] 대신 mod n+1 인 경우 [-n .. n]입니다.

c[k]=...%M 줄 뒤에 if (c[k] < 0) c[k] += M;을 붙이면 문제가 없습니다.

편집 : 실제로 가장 바깥 쪽 (k) for 루프 끝 부분에 넣는 것이 가장 좋습니다.