※ 引述《GoalBased (Artificail Intelligence)》之銘言：
: ※ [本文轉錄自 ask 看板 #1HTi2kk3 ]
: 作者: GoalBased (Artificail Intelligence) 看板: ask
: 標題: [請問] 數學問題
: 時間: Wed Apr 24 01:11:03 2013
: http://ppt.cc/zkN-
: 題目在上面，
: p1是x^3 / x^3+x+1 的 rem，也就是餘數的意思，
: 不過裡面的例子算出來好像都不是如此，
: 有人知道為什麼嗎?
: 他是怎麼算的呢?
個人覺得應該要解釋一下係數 mod 2 跟 XOR 關係何在 XD

首先這裡所討論的多項式是特別限制在 Z/2Z 下面的

也就是說這個多項式的係數只會是 0 跟 1 運算完要除以 2 取餘數

例如: (x^3) - (x^3 + x + 1) = - x - 1 = x + 1

這樣子的係數的加減運算如果仔細去看它 其實就只是下面這幾條式子而已:

0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0

由於係數只會是 0 或 1

我可以用一個固定長度的二進位數字來表示最多多少次的多項式

像是可以用三位二進位描述一個最多二次的這樣的多項式

(像是書裡用 011 表示 x + x^2 這個樣子)

而上面這些運算如果把 0 當 False, 1 當 True 的話

正好跟邏輯裡的 XOR (互斥或)運算是一模一樣的 (不管加減)

因此這種特別的多項式如果要寫成程式計算時

就會直接用跟它等同的二進位數值去進行 XOR 來運算

(像是書裡接下來可能會講到的檢查碼就會利用這個特性實作)

至於這種多項式的乘除法也跟普通的多項式除法差不多

所以除算可以直接寫長除法 當然裡面的加減就都是這些 XOR 運算了

那你真的把這個長除法寫下來就會變成上一篇回文裡的那個樣子

這就解釋了這裡的餘數是怎麼求出來的

--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.131.54