计算多项式除法的余数

Question

下面的代码是否实现了f•g取模多项式乘法的模约化x^p−x−1?正如我们所知，为了获得模约化，我们首先将多项式 f 和 g 相乘，然后除以 x^p−x−1，余数就是结果h = f•g.

我看不出下面的代码是如何做到这一点的。多项式的次数最多为 p−1，即它们看起来像 f(x) = 1+x −x²+....−x^p−1 表示为数组 f[p] = {1, 1, -1,... -1}。而数组h = fg[p+p-2]代表f和g的乘积。

谁能给我解释一下？

for (i = p+p-2;i >= p;--i) 
{
    fg[i-p] = fg[i-p]+fg[i];
    fg[i-p+1] = fg[i-p+1]+fg[i];
}
for (i = 0;i < p;++i) h[i] = fg[i];

Answer 1

Does the following code stand for modular reduction of the polynomial multiplication of f.g by mod (x^p-x-1)?

是的。

The degree of the polynomials are at most p-1, i.e., they look like f(x)= 1+x-x^2+....-x^{p-1} which is shown as an array f[p]={1,1,-1,...,-1}.

不，约化多项式的次数最多为p−1，但这是减少乘法结果的代码。两个阶数为 p−1 的多项式相乘，产生一个阶数为 2p−2 的多项式，这个的工作代码是取余数模 x^p−x−1.

为此，i 遍历从 2p−2（写作 p+p-2）到 p[= 的度数108=]。它从 2p−2 开始，因为这是产品中可能存在的最高程度，它在 p 处停止，因为这是有一个可以减去其倍数的商的最低程度。

然后，对于每个度数 i，它减去 x^{p[= 的倍数113=]−x−1：令c为x^的系数i、fg[i]。然后这段代码减去c•x^i−p•(x^p− x−1) = c•xⁱ − c•x^{i− p+1} − c•x^i−p:}

减去c•xⁱ在 fg[i] 中会产生零。这可以通过忽略索引 p 及以上的系数来实现；它们不会被最后的循环复制到 h 结果中。

− c•x^i−p+1减去c(fg[i])的系数加上x^i−p+1,在代码fg[i-p+1] = fg[i-p+1]+fg[i];.

− c•x^i−p减去c（fg[i]）到x[的系数=91=]i−p,在代码中fg[i-p] = fg[i-p]+fg[i];.

当第一个 for 循环完成时，多项式的所有倍数都已从初始乘积中减去，只剩下余数。

然后for (i = 0;i < p;++i) h[i] = fg[i];简单地将新系数复制到h。

计算多项式除法的余数

Computing remainder of polynomial division

c

modular

reduction