0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer. Let me explain my motivation. The reason I brought up division is because it is used in extended euclidean algorithm, which is used in polynomial inversion. I managed to perform inversion of a polynomial, but before finding an inverse of some polynomial A, I need to ensure that GCD(A, X^N - 1) is a polynomial with degree 0, which is why I need euclidean and division algorithms. $\endgroup$ – Iskorka May 5 at 21:15
  • $\begingroup$ I will try proposed function and let you know of the result, thank you $\endgroup$ – Iskorka May 5 at 21:17
  • $\begingroup$ So i tried it and the result is the same as in linked algorithm: given the input P = some polynomial (deg(a) < N) and Q = x^N - 1, output will be P. According to the inverse algorithm, it means that there is no inverse for this polynomial (since GCD(P, Q) is not a constant poly). But THERE IS an inverse. $\endgroup$ – Iskorka May 6 at 13:40

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.