4

NTRUチュートリアルによると、NTRUEncryptアルゴリズムを実装しています。多項式fには、f * g = 1 mod xのような逆gがあり、基本的に多項式にその逆縮小モジュロ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 の例では、剰余の法です。

1 ではなく -2 になるのはなぜですか?

4

1 に答える 1

4

-2 == 1 mod 3 であるため、計算は問題ありませんが、Java のモジュラス (剰余) 演算子の出力範囲は、標準の数学ではなく[-n .. n]forのようです。 mod n+1[0..n]

if (c[k] < 0) c[k] += M;ラインの後に を付けるだけc[k]=...%Mで問題ありません。

編集：実際には、最も外側の（k）forループの最後に配置するのが最善です。

于 2010-04-24T13:10:29.767 に答える