I'm trying to understand the NTRU-PKCS and therefor I wanted to code a naive Version of it. Now my Problem:
I tried to calculate the inverse of a Polynomial with an extended Version of euclids Algorithm. For some Polynomials my code works fine, but when I try it with the example from the NTRU-PKCS-Tutorial NTRU-PKCS-Tutorial it fails. The Parameter are $N=11$ and $q = 32$; The Polynomial $f$ is:
$ \begin{equation} f= -x^{10}+x^9+x^6-x^4+x^2+x-1 \end{equation}$
$\begin{equation} f^{-1} \text{ mod }q = 30x^{10}+18x^9+20x^8+22x^7+16x^6+15x^5+4x^4+16x^3+6x^2+9x+5 \end{equation} $
I really dont know why my code dont produce the right $f^{-1}$...
My 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];
}
The output:
========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 ]
It happens, when I hit the 4th time the loop, cuz I have to calculate $2 * x = 1 \text{ mod }32$, but there is no such inverse of $2 \text{ mod }32$. So the error have to happen before, but I really dont know where it happens.
Edit:
This error is not really a coding issue, because when I am calculating it with “Pen and Paper”, I get the exact same problem...
That’s why there has to be something wrong with my understanding of the extended Euclid, but I can't see why...
R_0:= x^N -1
R_1:= f
R_n+1:= R_(n)- R_(n-1) div R(n-2)
looks right to me :/
Edit2:
Thanks for referring to the stackoverflow thread, I coded it like it was there in pseudocode, but it fails at the exact same step :( Here my new code:
public void inverseEuclid(int N, int mod) {
PolynomialMod a= this.clone();
PolynomialMod b= getRing(N,mod);
PolynomialMod u = PolynomialMod.ONE.clone();
u.setNMod(N, mod);
PolynomialMod v1 = PolynomialMod.ZERO.clone();
v1.setNMod(N, mod);
PolynomialMod d = this.clone();
PolynomialMod v3 = b.clone();
while(!v3.equalsZero()) {
System.out.println("========values========");
System.out.println("d : "+d);
System.out.println("v3: "+v3);
PolynomialMod [] div = d.div(v3);
PolynomialMod q = div[0].clone();
System.out.println("q : "+q);
PolynomialMod t3 = div[1].clone();
System.out.println("t3: "+t3);
PolynomialMod t1 = u.sub(q.convolution(v1));
System.out.println("t1: "+t1);
System.out.println("========values========\n\n");
u = v1.clone();
d = v3.clone();
v1= t1.clone();
v3=t3.clone();
u.deleteLeadingZeros();
d.deleteLeadingZeros();
v1.deleteLeadingZeros();
v3.deleteLeadingZeros();
}
PolynomialMod v = d.sub(a.convolution(u)).div(b)[0];
System.out.println("u: "+u);
System.out.println("v: "+v);
System.out.println("d: "+d);
}
And here is my code for the euclidean division. I know this is not a coding-Forum, but I tried to implementations of euclid and I did it on paper, and the same error is ocurring... maybe someone knows what I am doing wrong...
public PolynomialMod[] div(final PolynomialMod other) {
if (other.isZero())
throw new ArithmeticException("division by zero");
final int degreeDifference = this.getDegree() - other.getDegree() + 1;
if (degreeDifference <= 0)
return new PolynomialMod[] { PolynomialMod.ZERO, this };
final PolynomialMod rest = this.clone();
final PolynomialMod quotient = new PolynomialMod(degreeDifference - 1, N, mod);
final int otherDegree = other.getDegree();
final int coeff = other.values.get(otherDegree);
for (int i = degreeDifference - 1; i >= 0; i--) {
final int q = MyMath.divMod(rest.values.get(otherDegree + i), coeff, mod);
quotient.values.set(i, q);
for (int j = 0; j <= otherDegree; j++) {
int restHelp = ((rest.values.get(i + j) - q * other.values.get(j)) + mod) % mod;
rest.values.set(i + j, restHelp);
}
}
return new PolynomialMod[] { new PolynomialMod(quotient.values, N, mod),
new PolynomialMod(rest.values, N, mod) };
}
