# Calculating Polynomial Inverse with extended euclid in java

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:

$$$f= -x^{10}+x^9+x^6-x^4+x^2+x-1$$$

$$$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$$$

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.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();

}
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) };
}

• I think this is on-topic because the asker says they get the same result with pencil and paper. I would refer them to stackoverflow.com/questions/2421409/…. Jun 15 '16 at 19:24
• What does it mean to take the inverse of a polynomial modulo an integer? -1 for general cluelessness, I'm sick of silly questions like that from people who just have no idea what they are doing. Jun 18 '16 at 15:56

newR: [ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 ]

This polynomial is $f = -x^{10} + x^9 + x^6 - x^4 + x^2 + x - 1$ where you wanted:

$f=x^{10}+x^9+x^6−x^4+x^2+x−1$

The sign for the $x^{10}$ was opposite.

Your algorithm/code is actually correct. See the following calculation from sage:

sage: f

-x^10 + x^9 + x^6 - x^4 + x^2 + x - 1

sage: f_inv

30*x^10 + 18*x^9 + 20*x^8 + 22*x^7 + 16*x^6 + 15*x^5 + 4*x^4 + 16*x^3 + 6*x^2 + 9*x + 5

sage: (f*f_inv)%(x^11-1)%32

1

• Thanks for your help, but this was only a type O in this forum, 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 ] newR is -x^10 (-x^0+x^+x^2+0x^3-x^4+0x^5+x^6+0x^7+0x^8+0x^9-x^10) Jun 21 '16 at 10:09
• Sorry I do not understand your comment. Can you explain a bit more? PS: if you correct this typo, you algorithm/code is correct. See the last part of my post. I did the calculation and it gives the right answer. Jun 21 '16 at 13:52
• I found my mistake... I did the extended Euclid right, but I didnt choose the right Polynomial ring... If I do this with q = 32 it's q= 2^5 so I have to calculate the Inverse in the Ring (R/2R) / (x^N -1). That was the Problem the whole time :( I did not really understand what I was doing, now I ve a clue, when I reduce the coefficiants modulo 32 my algorithm fails, I ve to do it modulo 2 and after that I have to lift it to mod 32, as it is mentioned in 6.3.3.4 from the IEEE standard 1363.1-2008. Thanks for your help Jun 21 '16 at 14:39

The Problem was as following:

The code works vor Polynomimals f(x) mod p, where p is prime (or gcd(p,coeff(f(x))) = 1), but I wanted the inverse modulo 32, which is in fact: 2^5, so I had to calculate the inverse mod 2 and then lift it to 2^5

The solution was in thread: inverse of polynomials