Ich versuche die NTRU-PKCS zu verstehen und wollte eine einfache Version in Java implementieren, daher habe ich eine selbst implementierte Methode (extend euclid) zur Berechnung der Umkehrung eines Polynoms in einem Ring verwendet.Inverse Berechnung von Polynomringen
Meistens funktioniert mein Algorithmus, aber wenn ich das Beispiel aus dem NTRU-PKCS-Tutorial versuche, PKCS-Tutorial schlägt es fehl und ich weiß nicht warum.
Das Beispiel ist:
f: -X^10^9 + 1x + 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 Ring: x^11-1
mein Code:
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];
}
Der Ausgang ist wie:
========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 ]
Das Problem ist: Wenn ich R/newr berechnen jetzt muss ich die Inverse von 2 mod 32, aber da der größte gemeinsame Teiler von 32 und 2 2 nicht 1 ist, finden es gibt keine inverse ...
Haben Ich habe den Algorithmus falsch implementiert?