Я пытаюсь понять NTRU-PKCS и хотел реализовать простую версию на Java, поэтому я использовал самореализованный метод (удлинение евклида) для вычисления инверсии полинома в кольце.Расчет инверсии полиномиальных колец
В большинстве случаев мой алгоритм работает, но когда я пробую пример из NTRU-PKCS-Tutorial PKCS-Tutorial, он терпит неудачу, и я не знаю почему.
Данный пример:
F: -x^10 + 1x^9 + 0x^8 + 0x^7 + 1x^6 + 0x^5-х^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 Кольцо: х^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 равен 2 не 1, то нет инверсных ...
Есть ли Я неправильно использовал алгоритм?