私は NTRU-PKCS を理解しようとしており、Java で単純なバージョンを実装したかったため、リング内の多項式の逆数を計算するために自己実装メソッド (euclid を拡張) を使用しました。
ほとんどの場合、私のアルゴリズムは機能しますが、NTRU-PKCS-Tutorial PKCS-Tutorialの例を試すと失敗し、その理由がわかりません。
例は次のとおりです。
f: -x^10+1x^9+0x^8+0x^7+1x^6+0x^5-x^4+0x^3+1x^2+1x^1-x^0 f^-1 mod 32: 30x^10+18x^9+20x^8+22x^7+16x^6+15x^5+4x^4+16x^3+6x^2+9x^1+5x^0 リング: x^ 11-1
私のコードは次のとおりです。
public PolynomialMod inverse(int N, int mod) {
int loop = 0;
PolynomialMod G = PolynomialMod.ZERO.clone();
G.setNMod(N, mod);
PolynomialMod newG = (PolynomialMod) PolynomialMod.ONE.clone();
newG.setNMod(N, mod);
int[] coeffR = { 1, 1, 0, 1, 1, 0, 0, 0, 1 };
PolynomialMod quotient = null;
PolynomialMod newR = this.clone();
PolynomialMod R = this.getRing(N, mod);
R.setNMod(N, mod);
newR.setNMod(N, mod);
while (!newR.equalsZero()) {
if (DEBUG && loop != 0)
System.out.println("loop: " + loop);
if (DEBUG && loop == 0)
System.out.println("========Initial Values========");
if (DEBUG)
System.out.println("R : " + R);
if (DEBUG)
System.out.println("newR: " + newR);
if (DEBUG)
System.out.println("Quotient: " + quotient);
if (DEBUG)
System.out.println("G : " + G);
if (DEBUG)
System.out.println("newG: " + newG);
if (DEBUG && loop == 0)
System.out.println("========Initial Values========");
if (DEBUG)
System.out.println("\n");
quotient = R.div(newR)[0];
PolynomialMod help = R.clone();
R = newR.clone();
PolynomialMod times = quotient.times(newR);
times.reduceBetweenZeroAndQ();
newR = help.sub(times);
newR.deleteLeadingZeros();
newR.degree = newR.values.size() - 1;
help = G.clone();
G = newG.clone();
PolynomialMod times2 = quotient.times(newG);
times2.reduceBetweenZeroAndQ();
newG = help.sub(times2);
loop++;
}
if (R.getDegree() > 0)
throw new ArithmeticException("irreducible or multiple");
return G.div(R)[0];
}
出力は次のようになります。
========Initial Values========
R : [ -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
newR: [ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 ]
Quotient: null
G : [ 0 ]
newG: [ 1 ]
========Initial Values========
loop: 1
R : [ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 ]
newR: [ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 ]
Quotient: [ 31, 31 ]
G : [ 1 ]
newG: [ 1, 1 ]
loop: 2
R : [ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 ]
newR: [ 1, 31, 31, 1, 1, 0, 31, 0, 1 ]
Quotient: [ 1, 31 ]
G : [ 1, 1 ]
newG: [ 0, 0, 1 ]
loop: 3
R : [ 1, 31, 31, 1, 1, 0, 31, 0, 1 ]
newR: [ 30, 31, 3, 2, 30, 30, 1, 2 ]
Quotient: [ 0, 1 ]
G : [ 0, 0, 1 ]
newG: [ 1, 1, 0, 31 ]
問題は、R/newR を計算する場合、2 mod 32 の逆数を見つける必要がありますが、32 と 2 の最大公約数は 1 ではなく 2 であるため、逆数はありません...
アルゴリズムを間違って実装しましたか?