这是一些面试问题中提出的问题。
给定三个多项式 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
可能是什么方法？我们可以在位级别做点什么吗？
问问题
9745 次
4 回答
17
动机
这里的二进制系数意味着系数是模 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将每一项的幂增加一。在紧凑表示法中，这相当于左移。
(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，这里是 5，那么就没有什么可做的了，因为不会除。x^nh(x)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 mod h(x)] = [h(x)-x^n] 当n = degree(h). 在紧凑的形式中，这相当于关闭第nth 位，这可以通过将 的表示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) 异或 (00100000 << 1) = 00000100
但是，更有效的是，只需转换先前的答案，我们将这样做x^7：
[x^7 mod (x^5+x)] = x^3, or 00001000
所以为了收集，我们需要将这些结果相加，这在紧凑表示中是 XOR-ing。
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。等等……
于 2012-11-05T00:36:49.600 回答
0
这是一个知识问题。基本上，除非你要么像高斯一样聪明，或者你已经知道同余数学，也称为“模算术”，否则你就完蛋了。你可能想读一本书来了解这些东西是 Allenby 的“Introduction to Number Theory with Computing”。
最终的关键知识是可以通过多种方法计算同余，其中最好的是相当古老的“平方和乘法”方法。基本上，每当你有一个二进制 1 时，你都是平方和倍数，但是当你有一个 0 时，你只是平方。完整的算法和解释在第页。艾伦比 79 号。
另一种方法是使用中文剩余Thereom，这可能是提问者的目标。
你在哪里申请？国家安全局？洛斯阿拉莫斯？这是一个相当棘手的问题。
太好了，因为是唯一真正回答问题的人而被否决。在这里要明确一点：毫无疑问，面试官期待利用平方和乘法算法，正如我上面所说的。在 RSA/密码算法中使用平方和乘法来进行快速模运算。见第 225 用于描述该算法和 RSA 应用程序：RSA 状态的多项标准产品的实现。面试官可能在 RSA 上工作，这就是他知道这种方法的原因。
于 2012-11-02T21:00:16.767 回答
0
你本质上在做的是二进制操作。你可以看看你的 CPU 是如何实现这样的操作的。
http://en.wikipedia.org/wiki/Multiplication_algorithm http://en.wikipedia.org/wiki/Modulo_operation
于 2012-11-02T21:02:10.340 回答
0
这看起来像一个简单的多项式乘法和长除法问题。只需将多项式相乘，然后将它们相除。使用两个嵌套的 for 循环，乘法非常简单，对于长除法，请参见：
于 2012-11-02T21:25:43.883 回答