Что такое определение усеченного многочлена?

Question

В NTRUEncryption я видел перемиримых многочленов, но я не могу понять вычисление trunacated полиномов.
Итак, может рассказать мне кто-нибудь. Как мы вычисляем усеченный многочлен?

Answer 1

Полиномы усекаются в том смысле, что они имеют только коэффициенты до некоторой степени.

Вот как усечение произведение двух усеченных многочленов (сумма тривиальна):

Предположим, у вас есть два усеченных полиномов, то есть два полинома степени не выше, чем n-1

a = a[0] + a[1]X + ... + a[n-1]X^(n-1) 
b = b[0] + b[1]X + ... + b[n-1]X^(n-1) 

Тогда их «усеченное» произведение определяются как полином

a * b = c[0] + c[1]X + ... +c[n-1]X^(n-1) 

где c[k] коэффициенты вычислили s follow:

1. Обратный b[0]..b[n-1] для получения b[n-1]..b[0].
2. Поворот результат шага 1 выше k+1 раз вправо и получить b[k]..b[0]b[n-1]..b[k+1]
3. Обозначим с b_k[0]..b_k[n-1] массив рассчитывается 2.

Теперь определим

c[k] = a[0]b_k[0] + a[1]b_k[1] + ... + a[n-1]b_k[n-1]. 

Эта операция также может быть сделанные путем умножения многочленов a и b обычным способом, а затем обрезание результата до степени n-1. Причина вышеизложенного алгоритма заключается в том, чтобы избежать вычисления коэффициентов, которые не будут использоваться в конечном результате.