algorithm - 两个多项式相乘

Question

这是一些面试问题中会问到的问题。

给定三个多项式 f(x)、g(x)、h(x)，其中系数是二进制的。给出 [f(x)*g(x)] mod h(x) [二进制系数中的所有运算]

多项式以这种格式给出…… x3 + x + 1 给出为“1011”。编写一个程序 char* multmod (char *f, char *g, char *h) 将输出多项式… (f*g) mod h

可能的方法是什么？
我们可以在位级别做点什么吗？

Answer 1

动机

这里的二进制系数意味着系数是模 2，在字段 Z_2 中，或者只是取值 0 和 1 并像位一样操作。这并不意味着系数是以二为底表示的任意整数。它们是二进制的(正好取两个值)，而不是简单地用二进制数字系统表示。

牢记这一点，这个问题很容易回答，是的，异或和(左)移位的按位运算就足够了。虽然不需要回答这个问题，但这个问题是由密码学引起的。它演示了散列中常用的一些按位运算与一些加密方案和抽象代数之间的联系，因此可以在密码分析中利用有关有限域上多项式的结果。将乘积取模另一个多项式是为了防止结果的次数超过某个限制。机器寄存器上的操作很自然地作为溢出来完成。

添加

先来说说加法。由于系数是模 2，添加 x + x = 2x = 0x = 0自 2 mod 2 = 0 .因此，只要有两个相同的术语，它们就会取消，而当只有一个时，它会持续存在。这与 XOR 的行为相同.例如，添加 (x^4 + x^2 + 1) + (x^3 + x^2):

(1x^4+0x^3+1x^2+0x^1+1x^0)+(0x^4+1x^3+1x^2+0x^1+0x^0) = (1x^4+1x^3+0x^2+0x^1+1x^0) 

或者，仅使用紧凑系数表示法，

10101 XOR 01100 = 11001

乘法

乘以 x将每个项的幂增加 1。在紧凑表示法中，这等效于左移。

(1x^4+0x^3+1x^2+0x^1+1x^0) * x = (1x^5+0x^4+1x^3+0x^2+1x^1+0x^0)
10101 << 1 = 101010

因此，要乘以多项式 f(x) * g(x)我们可以相乘 f(x)按每期g(x)分别，每个相当于一个移位，然后相加，加法相当于异或。让我们相乘 (x^4 + x^2 + 1) * (x^3 + x^2)

(x^4 + x^2 + 1) * (x^3 + x^2) = (x^4 + x^2 + 1)*x^3 + (x^4 + x^2 + 1) *x^2
(10101 << 3) XOR (10101 << 2) = 10101000 XOR 01010100 = 11111100

所以，答案是x^7 + x^6 + x^5 + x^4 + x^3 + x^2 .

减模

减模h(x)也相当容易。它当然不需要你记住如何做长除法。像乘法一样，我们将逐项进行。让我们继续同一个例子，取模 h(x) = x^5 + x

(x^7 + ... + x^2) mod (x^5+x) = [x^7 mod (x^5+x)] + ... + [x^2 mod (x^5+x)]

现在，如果度数，n , 的 x^n小于h(x) ，这里是5，那就没什么可做的了，因为h(x)不会分x^n .

[x^2 mod (x^5+x)] = x^2 or 00000100
[x^3 mod (x^5+x)] = x^3 or 00001000
[x^4 mod (x^5+x)] = x^4 or 00010000

当度数相等时，我们可以说 h(x)分x^n一次，我们超过了 h(x) 的剩余条款.我们超过而不是低于几乎无关紧要，自 -1 mod 2 = 1 起余数的符号也不重要。 .这里，

x^5 = (x^5 + x) – x, so
[x^5 mod (x^5+x)] = x, or 00000010

一般来说，当n = degree(h)时，[x^n mod h(x)] = [h(x)-x^n] .在紧凑形式中，这相当于关闭 n第 1 位，可以通过对 h(x) 的表示进行异或来完成与 x^n 的代表:

00100010 XOR 00100000 = 00000010.

当x^n度数大于 h(x)我们可以相乘 h(x)来自 x^k使度数匹配，并按照前面的情况进行。

x^6 = (x^5 + x)*x – (x)*x = -x^2，所以
[x^6 mod (x^5+x)] = x^2，或 00000100，或紧凑形式
(00100010 << 1) XOR (00100000 << 1) = 00000100

但是，更有效的是，只需改变之前的答案，我们将为 x^7 做这件事。 :

[x^7 mod (x^5+x)] = x^3, or 00001000

所以为了收集，我们需要将这些结果相加，这就是紧凑表示中的异或运算。

x^2 + x^3 + x^4 + x + x^2 + x^3 = x^4 + 2x^3 + 2x^2 + x = x^4 + x, or
00000100 XOR 00001000 XOR 00010000 XOR 00000010 XOR 00000100 XOR 00001000 = 00010010

结语

我们可以问Wolfram Alpha通过长除法为我们验证这个结果。给出的余数是 x^4 - x ，相当于 x^4 + x当系数为模 2 时。

可以组合逐项乘法和取模步骤，例如乘以 x并对乘积求模，以获得更有效的算法，如果乘积的度数至少为 h(x)，则该算法将是移位和异或。 .然后对结果重复，乘以 x并对乘积求模，并记录乘以 x^2 的答案.等等……