NTRUEncrypt：无法使用开源标准算法中描述的正确找到两个多项式的 GCD，无法定义是否存在 poly 的倒数

Question

我已经按照 onboard security resourses 中的描述实现了多项式的逆运算算法，但这些算法意味着我想要求逆的多边形的 GCD 和 X^N - 1 是 1。

为了正确实现 NTRU，我需要随机生成小多项式并定义它们的逆是否存在，目前我没有这样的功能。为了让它工作，我尝试按照 documentation 中所述为 NTRU 开源项目实施欧几里德算法。但是我发现有些事情非常不一致，这让我很不爽。除法和欧几里德算法可以在命名文档的第 19 页找到。

因此，在除法算法中，输入是多项式 a 和 b。规定多项式 b 的次数必须为 N-1。

除法算法的伪代码（取自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

为了找到两个多项式的 GCD，必须使用输入 a（某个多项式）和 X^N-1 调用欧几里德算法。然后将这些输入传递给除法算法。

问题是：如果明确规定第二个参数应该是阶数为N-1的poly，X^N - 1如何传递给除法算法？

忽略这个问题，还有不懂的地方：

除法算法中的N是什么？是NTRU参数的N还是多项式b的次数？
无论哪种方式，条件 c) 怎么可能为真？ NTRU 使用次数小于 N

对于更大的上下文，这是我的欧几里德和除法算法的 C++ 实现。给定输入 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 在除法算法中进入死循环

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

此外，此列表中使用的多项式运算可在 github page

中找到

Answer 1

我不小心用谷歌搜索了 the answer。我真的不需要计算 GCD 来选择随机可逆多项式，我只需要为我的随机多边形选择正确数量的 1 和 0（对于二进制）或 -1、0 和 1（对于三元）。

拜托，这个问题已经解决了。

NTRUEncrypt：无法使用开源标准算法中描述的正确找到两个多项式的 GCD，无法定义是否存在 poly 的倒数

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

c++

cryptography

ntruencrypt

polynomials