查找字段F2上的兩個多項式的GCD

Question

我想在模2和字段模3中找到以下多項式（兩個單獨的問題）的GCD。但是我卡在第一個一個是因爲某些原因。

a(x) =x5+x3+x2+ 1, 
b(x) =x3+x   for mod 2 


a(x) = 2x3+2x2+x+1 
b(x) =x2+2   for mod 3 

對於第一個，我試圖表示多項式作爲1的位和0（例如：101101和1010），並試圖使用GCD歐幾里得算法來尋找，但在某些時候它導致零，這如果我正確地進行計算是不可能的。

第二組多項式的，我不知道所有的，因爲它作爲共同efficients超過1

任何幫助將非常感激。

Answer 1

讓

F_1 = X^5 + X^3 + X^2 + 1和

F_2 = X^3 + X

工作模2，我們可以改變符號到

f_1 =（1,0,1,1,0,1）和

f_2 =（1,0,1,0）。

做了長時間的劃分，我們得到了 f_1 = q_2 * f_2 + f_3其中f_3的嚴格程度嚴格低於f_2的程度。

事實證明，

Q_2 =（1,0,0），其是Q_2 = X^2

F_3 =（1,0,1），其F_3 = X^2 + 1

繼續我們得到

F_2 = q_3 * F_3 + F_4

事實證明，

Q_ 3 =（1,0）和

F_4 =（0）

即該歐幾里德算法完成和之間的F_N的最後非零多項式是GCD後者信號。因此f_3是GCD。直接證明f_3確實是一個共同的因數。

對於第二種情況，您使用元組（如上面的（1,0,1）），但這次的座標是0,1或2（餘數爲mod 3）。否則，算法是相同的。

這會增加你的理解，如果你在某種編程語言中實現你的算法。