這是一些面試問題中提出的問題。乘以兩個多項式
給出三個多項式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'！ –