Модульная редукция полиномов в NTRUEncrypt - PullRequest
Новая
       17

Модульная редукция полиномов в NTRUEncrypt

4 голосов
/ 24 апреля 2010

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

1 Ответ

4 голосов
/ 24 апреля 2010

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

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

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

...