Я реализовал алгоритмы для нахождения обратного полинома, как описано в бортовых ресурсах безопасности , но эти алгоритмы подразумевают, что GCD для поли, который я хочу инвертировать, а X ^ N - 1 - 1.
Для правильной реализации NTRU мне нужно случайным образом сгенерировать небольшие полиномы и определить, существуют ли их обратные, пока у меня нет такой функциональности.
Чтобы заставить его работать, я попытался реализовать евклидов алгоритм, как описано в документации для проекта с открытым исходным кодом NTRU. Но я нашел кое-что очень противоречивое, что отвлекает меня.
Алгоритмы деления и евклидова алгоритма можно найти на странице 19 названного документа.
Итак, в алгоритме деления входные данные являются полиномами a и b. Утверждается, что многочлен b должен иметь степень N-1.
Псевдокод для алгоритма деления (взято из этот ответ ):
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. Эти входы затем передаются в алгоритм деления.
Вопрос : как можно передать X ^ N - 1 в алгоритм деления, если четко указано, что второй параметр должен быть поли со степенью N-1?
Игнорируя эту проблему, есть вещи, которые я не понимаю:
- что такое N в алгоритме деления? Это N из параметров NTRU или степень полинома 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 и 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