1

x ^ n–1（mod p）の多項式の結果

http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdfのセクション2.2.7.1で説明されているように、NTRUSignアルゴリズムを実装しています。これには、多項式の結果の計算が含まれます。結果のゼロベクトルを取得し続けますが、これは明らかに正しくありません。

private static CompResResult compResMod(IntegerPolynomial f, int p) {
    int N = f.coeffs.length;
    IntegerPolynomial a = new IntegerPolynomial(N);
    a.coeffs[0] = -1;
    a.coeffs[N-1] = 1;
    IntegerPolynomial b = new IntegerPolynomial(f.coeffs);
    IntegerPolynomial v1 = new IntegerPolynomial(N);
    IntegerPolynomial v2 = new IntegerPolynomial(N);
    v2.coeffs[0] = 1;
    int da = a.degree();
    int db = b.degree();
    int ta = da;
    int c = 0;
    int r = 1;
    while (db > 0) {
        c = invert(b.coeffs[db], p);
        c = (c * a.coeffs[da]) % p;

        IntegerPolynomial cb = b.clone();
        cb.mult(c);
        cb.shift(da - db);
        a.sub(cb, p);

        IntegerPolynomial v2c = v2.clone();
        v2c.mult(c);
        v2c.shift(da - db);
        v1.sub(v2c, p);

        if (a.degree() < db) {
            r *= (int)Math.pow(b.coeffs[db], ta-a.degree());
            r %= p;
            if (ta%2==1 && db%2==1)
                r = (-r) % p;
            IntegerPolynomial temp = a;
            a = b;
            b = temp;
            temp = v1;
            v1 = v2;
            v2 = temp;
            ta = db;
        }
        da = a.degree();
        db = b.degree();
    }
    r *= (int)Math.pow(b.coeffs[0], da);
    r %= p;
    c = invert(b.coeffs[0], p);
    v2.mult(c);
    v2.mult(r);
    v2.mod(p);
    return new CompResResult(v2, r);
}

http://www.crypto.rub.de/imperia/md/content/texte/theses/da_driessen.pdfには、非常によく似た擬似コードがあります。

コードが機能しないのはなぜですか？確認できる中間結果はありますか？

IntegerPolynomialコードはあまり面白くなく、合格した単体テストがあるため、投稿していません。CompResResultは、単純な「Java構造体」です。

4

2 に答える 2

1

別の方法として、 JScienceクラスを検討してくださいPolynomial<R extends Ring<R>>。クラスは汎用でPolynomial<Integer>あるため、実装が簡素化される可能性があります。この例Polynomial<Complex>では、テストの便宜のために使用しています。

于 2011-01-02T20:06:17.320 に答える
0

私の推測では、 (int)Math.pow(b.coeffs[0], da) は 0 に評価されています。デバッガーを使用してこのコードをステップ実行しようとすると、値が毎回ゼロになる理由が表示されるはずです。

于 2011-01-02T19:48:39.097 に答える