cryptography - 截断多项式的定义是什么？

Question

在 NTRUEncryption 中，我看到了截断多项式，但我无法理解截断多项式计算。
那么，谁能告诉我我们如何计算截断多项式？

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]系数计算如下：

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。采用上述算法的原因是为了避免计算最终结果中不会用到的系数。