NTRU: Possible misunderstending of division and euclidean algorithm for polynomials

Question

Please consider this answer before reading

I am trying to find GCD of two polynomials, but I have some troubles understanding division and euclidean algorithms:

1) In description of division algorithm it is stated that polynomial b must be of degree N-1, but when finding the inverse of polynomial we must pass $x^N - 1$ as b

2) If previous condition is ignored, division algorithm still won't work properly because of the next condition:

deg r >= N

if N is taken from parameter set, it doesn't make sence, because NTRU operates with polynomials of degree less than N.

So, consider next scenario:

$N = 11$

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

$b = x^N - 1 = x^{11} - 1$

Division algorithm would return quontient = 0 and remainder = a, since degree of a is less than N.

And the result will be the same regardless of the value of a.

What am I missing? I doubt that such basic algorithm could be documented wrong, so please help me understand what did I get wrong.

Answer 1

I am trying to find GCD of two polynomials

If you are trying to find the GCD, it turns out that trying to perform divisions is the wrong way (the referenced question was talking about computing inverses - a rather different problem).

The first thing you need to ask is "what ring or field are the polynomials defined over?". If it is, in fact, a field, then it is easy; you can follow this procedure:

GCD( Polynomial P, Polynomial Q ) {
    for (;;) {
        if (deg(P) < deg(Q))
            swap P, Q
        deg_p = deg(P);
        lead_p = P[deg_p];   /* The leading coefficient of P */
        deg_q = deg(Q)'
        lead_q = Q[deg_q];   /* The leading coefficient of Q */
        X := (x ** (deg_p - deg_q); /* A polynomial with the coefficient */
                             /* deg_p-deg_q set */
        (P, Q) := (Q, lead_q*P - lead_p*X*Q);
        if (Q == 0) {        /* If Q is the all-zero polynomial */
            return P;
        }
 }

This function decreases deg(P)+deg(Q) each iteration, and so it is guaranteed to terminate. In addition, all the operations can be done fairly easily (the computation of X*Q can be done by shifting all the coefficients of Q leftward deg_p-deg_q places).

And, if the polynomial is defined over a field, it can be shown that this always returns a correct value.

On the other hand, sometimes NTRU works in polynomials over the field $\mathbb{Z}_3$, and sometimes in polynomials over the ring $\mathbb{Z}_q$, for $q = 2048$ or $4096$; this ring has noninvertible elements, with muck things up a bit.

Now, if you are working over $\mathbb{Z}_q[X]$, I believe that the above algorithm will return something related to the actual GCD (however, it's not guaranteed that $P$ and $Q$ will both be multiples of the result); depending on what you're doing with the GCD, it might be good enough...