NTRUEncrypt: can't properly find GCD of two polynomials using decribed in open source standard algorithms, fail to define if inverse of poly exists

Question

I've implemented algorithms for finding an inverse of a polynomial as described at onboard security resourses, but these algorithms imply that GCD of poly that I want to invert and X^N - 1 is 1.

For proper NTRU implementation I need to randomly generate small polynomials and define if their inverse exist, for now I don't have such functionality. In order to get it work i tried to implement Euclidean algorithm as described in documentation for NTRU Open Source project. But I found some things very inconsistent which bugs me off. Division and Euclidean algorithms can be found on page 19 of named document.

So, in division algorithm the inputs are polynomials a and b. It is stated that polynomial b must be of degree N-1.

Pseudocode for division algorithm (taken from this answer):

a)  Set r := a and q := 0
b)  Set u := (b_N)^–1 mod p
c)  While deg r >= N do
    1)    Set d := deg r(X)
    2)    Set v := u × r_d × X^(d–N)
    3)    Set r := r – v × b
    4)    Set q := q + v
d)  Return q, r

In order to find GCD of two polynomials, one must call Euclidean algorithm with inputs a (some polynomial) and X^N-1. These inputs are then passed to division algorighm.

Question is: how can X^N - 1 be passed into division algorithm if it is clearly stated that second parameter should be poly with degree N-1 ?

Ignoring this issue, there's still things I do not understand:

1. what is N in division algorithm? Is it N from NTRU parameters or is it degree of polynomial b?
2. either way, how can condition c) ever be true? NTRU operates with polynomials of degree less than N

For the greater context, here is my C++ implementation of Euclidean and Division algorithms. Given the inputs a = {-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}, b = {-1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1}, p = 3 and N = 11 it enters endless loop inside division algorithm

using tPoly = std::deque<int>;

std::pair<tPoly, tPoly> divisionAlg(tPoly a, tPoly b, int p, int N)
{
    tPoly r = a;
    tPoly q{0};
    int b_degree = degree(b);
    int u = Helper::getInverseNumber(b[b_degree], p);

    while (degree(r) >= N)
    {
        int d = degree(r);
        tPoly v = genXDegreePoly(d-N); // X^(d-N)
        v[d-N] = u*r[d]; // coefficient of v
        r -= multiply(v, b, N);
        q += v;
    }
    return {q, r};
}

struct sEucl
{
    sEucl(int U=0, int V=0, int D=0)
        : u{U}
        , v{V}
        , d{D}
    {}

    tPoly u;
    tPoly v;
    tPoly d;
};

sEucl euclidean(tPoly a, tPoly b, int p, int N)
{
    sEucl res;
    if ((degree(b) == 0) && (b[0] == 0))
    {
        res = sEucl(1, 0);
        res.d = a;
        Helper::printPoly(res.d);
        return res;
    }

    tPoly u{1};
    tPoly d = a;
    tPoly v1{0};
    tPoly v3 = b;

    while ((0 != degree(v3)) && (0 != v3[0]))
    {
        std::pair<tPoly, tPoly> division = divisionAlg(d, v3, p, N);
        tPoly q = division.first;
        tPoly t3 = division.second;
        tPoly t1 = u;
        t1 -= PolyMath::multiply(q, v1, N);
        u = v1;
        d = v3;
        v1 = t1;
        v3 = t3;
    }
    d -= multiply(a, u, N);
    tPoly v = divide(d, b).first;

    res.u = u;
    res.v = v;
    res.d = d;
    return res;
}

Additionally, polynomial operations used in this listing may be found at github page

Answer 1

I accidentally googled the answer. I don't really need to calculate GCD to pick a random invertable polynomial, I just need to choose the right amount of 1 and 0 (for binary) or -1, 0 and 1 (for ternary) for my random poly.

Please, consider this question solved.