这是一些面试问题中提出的问题。乘以两个多项式
给出三个多项式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
可能是什么方法？ 我们可以在比特级别做些什么吗？
这是一个知识问题。基本上，除非你像高斯一样聪明，或者你已经知道同余数学，也就是所谓的“模数算术”，否则你就被搞砸了。你可能想阅读一本关于这个东西的书，那就是艾伦比的“计算数论导论”。
最终关键的知识是可以通过几种方法来计算一致性，其中最好的方法是相当古老的“平方和乘法”方法。基本上，无论何时你有一个二进制1，你都是正方形和多个，但是当你有一个0时，你只是方形。完整的算法和解释在p。 79艾伦比。
另一种方法是使用Chinese Remainder Thereom，这可能是提问者的目标。
你在哪里申请？国家安全局？洛斯阿拉莫斯？这是一个相当棘手的问题。
伟大的，downvoted是唯一的人谁真正回答了这个问题。这里要明确一点：毫无疑问，面试官正在期待利用广场和乘法算法，正如我上面所说的。在RSA /密码算法内部使用平方和乘法来进行快速模运算。请参阅页码。 225对该算法和RSA应用的描述：Implementation of Multinomial Standard Product for RSA State。面试官可能在RSA工作，这就是为什么他知道这种方法。
在我的这一天，这将是一个高中水平的问题。如果你知道如何分解两个多项式并得到一个余数，这很容易回答。从那里到NSA有很长的路要走。 –
@ n.m。 - 正好。你使这种听起来比泰勒真实得多。在我的11年级代数考试中，我有其中的一个。 – IVlad
这其实很简单。然而，它与密码学和国家安全局高度相关......如果你注意系数是二进制的（即，在Z_2中并减少模2本身）的事实，那么你会看到加法是异或乘以x^n是一个位移。 –
你实质上是在做什么是二元操作。 你可以看看你的CPU如何实现这样的操作。
http://en.wikipedia.org/wiki/Multiplication_algorithm http://en.wikipedia.org/wiki/Modulo_operation
你没有得到它 – Alexander
你能告诉我我是错的还是我没有得到它？这会有所帮助。 我真的没有多想，我在10秒内回答。多项式实际上受到限制，所以您可以将其实质上表示为二进制数字，并仅使用由cpu实现的二进制操作的算法。 – 2012-11-05 14:41:14
这看起来像一个简单的多项式乘法和长除法问题。只需乘以多项式，然后将它们分开。乘法是两个嵌套的for循环非常简单的，长期的划分请参见：
动机这里
二进制系数是指系数是模2，在现场Z_2，或者只取值0和1并像位一样操作。这并不意味着系数是以二为底的任意整数。它们的是二进制（取正好两个值），而不是简单地用二进制数字系统表示。
考虑到这一点，这个问题很容易回答，是的，XOR和（左）移位的按位操作就足够了。虽然不需要回答这个问题，但这个问题是由密码学激发的。它演示了散列中常用的一些按位运算与一些加密方案和抽象代数之间的联系，以便在密码分析中可以利用有限域上多项式的结果。以乘积为模的另一个多项式是防止结果的程度超过一定的限制。机器寄存器上的操作自然会造成溢出。
加成
首先让我们来谈谈另外。由于系数是模2，因此从2 mod 2 = 0开始加x + x = 2x = 0x = 0。所以，只要有两个相同的术语，它们就会取消，而只有一个它会一直存在。这与XOR的行为相同。例如，通过加入x(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
乘法
乘法由一个增加了每个术语的功率。在紧凑的表示法中，这相当于向左按位移。
(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)我们可以通过g(x)分开，各自为相当于移位的每个术语相乘f(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
一般而言，[X^N模H（X）] = [H（X）-x^N]时n = degree(h)。在紧凑的形式，这等同于关闭n个比特，其可以通过异或的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，相当于当系数以2为模时x^4 + x。
可以组合例如逐项乘法和模数步骤。乘以x并对该产品进行取模，得到更有效的算法，如果产品的度数至少为h(x)，则该算法将是移位和XOR。然后重复结果，乘以x并对产品进行取模，并记录该乘法的答案为x^2。等等......
*注意：以下主要问题是针对原始海报的。*您可以添加两个多项式吗？二元多项式的运算如何与正则多项式上的运算不同？你可以用'x^17'乘以一个任意的多项式吗？你知道如何做多项式长分工吗？ –
是的，XOR和shift的二进制操作应该可以做到。有些缺失的是系数是_binary_，也就是说在字段Z_2中。这意味着'（x^3 + x^2 + 1）+（x^2）=（x^3 + 2x^2 + 1）=（x^3 + 1）'或'1101 XOR 0100 = 1001'！ –