乘两个多项式 [英] Multiplying two polynomials
问题描述
这是问一些面试问题的问题。
This is a question asked in some interview questions.
鉴于3多项式函数f（x），G（x）时，H（X），其中所述共同有效的是二进制。得到[F（X）*克（x）的]的mod H（X）[所有在操作二进制合作效率]
Given three polynomials f(x), g(x), h(x) where the co-efficient are binary. Give [f(x)*g(x)] mod h(x) [All operation in binary co-efficient]
多项式在本格式给出...×3 + X + 1被给定为1011。写一个程序的char * multmod（字符*楼的char *克，字符* H），将输出多项式...（F * G）MOD ^ h
Polynomials are given in this format… x3 + x + 1 is given as "1011". Write a program char* multmod (char *f, char *g, char *h) that will output polynomial… (f*g) mod h
可能是什么方法呢？ 我们可以做一些在位的水平？
What could be the approach? can we do something at bit level?
推荐答案
激励
二进制系数这里指的系数模2，在该领域Z_2，或只取上的值0和1和操作像位。这并不意味着系数是任意整数重新psented在基地二期$ P $。它们的是的二进制（取恰好两个值），而不是简单地被前pressed在二进制数字系统。
Binary coefficients here means that the coefficients are modulo 2, in the field Z_2, or just take on the values 0 and 1 and operate like bits. It does not mean the coefficients are arbitrary integers represented in base two. They are binary (take on exactly two values), as opposed to simply being expressed in a binary numeral system.
通过此牢牢记住，这个问题很容易回答，是的，XOR和（左）移位位运算就足够了。虽然不要求回答这个问题，这个问题是由加密动机。它展示了一些位操作的散列常用的一些加密方案和抽象代数之间的联系，使有关有限域上多项式的结果可以在密码分析加以利用。服用该产品模另一个多项式是prevent从过去一定限度生长的结果的程度。在机器寄存器的操作做到这一点，自然溢流。
With this firmly in mind, this question is fairly easy to answer, and yes, bitwise operations of XOR and (left) shifts will suffice. Though not required to answer this question, this question is motivated by cryptography. It demonstrates the link between some bitwise operations commonly used in hashing and some encryption schemes and abstract algebra, so that results about polynomials over finite fields can be leveraged in cryptanalysis. Taking the product modulo another polynomial is to prevent the degree of the result from growing past a certain limit. Operations on machine registers do this naturally as overflow.
添加
首先，让我们来谈谈另外。由于系数是模2，加入 X + X = 2X = 0X = 0 ，因为 2的mod 2 = 0 。因此，每当有两个相同的术语，它们取消，并且当只有一个它仍然存在。这是相同的行为 XOR 。例如，添加（X ^ 4 + X ^ 2 + 1）+（X ^ 3 + X ^ 2）：
First let’s talk about addition. As the coefficients are modulo 2, adding x + x = 2x = 0x = 0 since 2 mod 2 = 0. So, whenever there is two of the same term, they cancel, and when there is only one it persists. This is the same behavior as XOR. For example, adding (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)
，或用小型系数只有符号，
or, using the compact coefficient only notation,
10101 XOR 01100 = 11001
乘
乘用 X 由一个增加每学期的力量。在紧凑的符号，这等同于左按位移
Multiplication by x increases the power of each term by one. In the compact notation, this is equivalent to left bitwise shift.
(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）由克每一项（x）的分开，各自为相当于换档，然后添加，添加等同于异或运算。让我们乘（X ^ 4 + X ^ 2 + 1）*（X ^ 3 + X ^ 2）
So, to multiply polynomials f(x) * g(x) we can multiply f(x) by each term of g(x) separately, each being equivalent to a shift, and then add, the addition being equivalent to XOR. Let’s multiply (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
Reduction modulo h(x) is also fairly easy. It certainly does not require you to remember how to do long division. Like multiplication, we’ll do it term by term. Let’s continue with the same example, and take it modulo 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 的 H（X），这里5，那么就没有什么工作要做，因为 H（X）将不分 X ^ñ。
Now, if the degree, n, of x^n is smaller than that of h(x), here 5, then there is nothing to be done because h(x) won’t divide 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）分歧 H（x）的其余条款下颚。我们已经超调，而不是下颚并不重要，也没有对余下的迹象，因为 -1 MOD 2 = 1 。在这里，
When then degrees are equal, we can say h(x) divides x^n one time, and we have overshot by the remaining terms of h(x). That we’ve overshot instead of undershot hardly matters, nor does the sign on remainder since -1 mod 2 = 1. Here,
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 =度（H）。在紧凑的形式，这相当于关闭 N 个位，这可以通过异或的再presentation做ħ （X）与再presentation X ^ñ：
In general, [x^n mod h(x)] = [h(x)-x^n] when n = degree(h). In compact form, this is equivalent to turning off the nth bit, which can be done by XOR-ing the representation of h(x) with the representation of x^n:
00100010 XOR 00100000 = 00000010.
在大的程度H（X）我们可以乘 H（X）按 X ^氏/ code>让度的比赛，并继续为在现有情况下。
When x^n has a degree larger than h(x) we can multiply h(x) by x^k to make the degrees match, and proceed as in the prior case.
的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^6 = (x^5 + x)*x – (x)*x = -x^2, so [x^6 mod (x^5+x)] = x^2, or 00000100, or in compact form (00100010 << 1) XOR (00100000 << 1) = 00000100
但是，更有效的，只是转移了previous的答案，我们将做 X ^ 7 ：
But, more efficiently, just shift the previous answer, which we’ll do for x^7:
[x^7 mod (x^5+x)] = x^3, or 00001000
所以收集，我们需要添加这些结果，这是异或在紧凑型重presentation。
So to collect, we need to add these results, which is XOR-ing in the compact representation.
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
结束语
我们可以问<一个href="http://www.wolframalpha.com/input/?i=%28%28x%5E4+%2B+x%5E2+%2B+1%29+*+%28x%5E3+%2B+x%5E2%29%29++%2F+%28x%5E5%2Bx%29"相对=nofollow> Wolfram Alpha的通过长除法来验证这个结果对我们来说。给定的剩余部分 X ^ 4 - X ，相当于 X ^ 4 + X 时，系数是模2。
We can ask Wolfram Alpha to verify this result for us by long division. The remainder given is x^4 - x, which is equivalent to x^4 + x when the coefficients are modulo 2.
术语逐术语乘法和模步骤可以被组合，例如通过用x 和模的产品，为更有效的算法，这将是一个转变和XOR如果该产品的程度至少是 h的（X）。然后通过重复的结果，用x 和模产品，并记录下答案乘法 X ^ 2 。如此反复......
The term-by-term multiplication and modulo steps may be combined, e.g. multiply by x and modulo the product, for a more efficient algorithm, which will be a shift and XOR if the product’s degree is at least that of h(x). Then repeat on the result, multiply by x and modulo the product, and record that answer for multiplication by x^2. And so forth...
这篇关于乘两个多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
