1
$\begingroup$

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) };
}
$\endgroup$
  • 1
    $\begingroup$ 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/…. $\endgroup$ – William Whyte Jun 15 '16 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$ – fkraiem Jun 18 '16 at 15:56
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – user2979446 Jun 21 '16 at 10:09
  • $\begingroup$ 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. $\endgroup$ – zhenfei zhang Jun 21 '16 at 13:52
  • $\begingroup$ 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 $\endgroup$ – user2979446 Jun 21 '16 at 14:39
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.