我试图了解 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模 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 的最大公约数是 2 而不是 1，所以没有倒数...
我是否错误地执行了算法？