Я реализую алгоритм 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;
}
Он в основном берется в полином a и умножает его на b, возвращает результат в c, N указывает степень полинома + 1, в приведенном выше примере N = 11; и M - приведение по модулю, в примере выше 3.
Почему я получаю -2, а не 1?
