在伽羅瓦域中求乘法逆28282^8使用擴展的歐幾里得算法
我正在處理伽羅瓦域 $ GF(2^{8}) $ 需要幫助找到多項式 $ r^{-1}(x) $ 這樣 $ r^{-1}(x) r(x) \equiv 1 \mod m(x) $ ， 在哪裡：
- $ m(x) = x^{8} + x^{4} + x^{3} + x + 1 $
- $ r(x) = u(x) - q(x) \cdot m(x) $
- $ u(x) = s(x) \cdot t(x) $
- $ s(x) = x^{7} + x^{5} + x^{4} + x $
- $ t(x) = x^{4} + x^{2} + 1 $
因此：
- $ u(x) = x^{11} + x^{8} + x^{6} + x^{4} + x^{3} + x $
- $ q(x) = x^{3} + 1 $
- $ r(x) = -x^{7} - x^{4} - x^{3} + 1 \mod 2 = x^{7} + x^{4} + x^{3} + 1 $
我試過的
我試圖找出 $ r^{-1}(x) $ 但失敗了。
這是我嘗試過的：
來自歐幾里得算法：
$$ \begin{align*} u(x) &= q(x) \cdot m(x) + r(x) \ m(x) &= q_{2}(x) \cdot r(x) + r_{2}(x) \ &= x \cdot r(x) + (-x^{5} + x^{3} + 1 \mod 2) \ &= x \cdot r(x) + ( x^{5} + x^{3} + 1) \ r(x) &= q_{3}(x) \cdot r_{2}(x) + r_{3}(x) \ &= (x^{2} - 1 \mod 2) \cdot r_{2}(x) + (x^{4} + 2 x^{3} - x^{2} + 2 \mod 2) \ &= (x^{2} + 1) \cdot r_{2}(x) + (x^{4} + x^{2}) \ r_{2}(x) &= q_{4}(x) \cdot r_{3}(x) + r_{4}(x) \ &= x \cdot r_{3}(x) + 1 \ r_{3}(x) &= q_{5}(x) \cdot r_{4}(x) + r_{5}(x) \ &= (x^{4} + x^{2}) \cdot r_{4}(x) + 0 \end{align*} $$
我們有：
$$ \begin{align*} q_{2}(x) &= x \ q_{3}(x) &= x^{2} + 1 \ q_{4}(x) &= x \ q_{5}(x) &= x^{4} + x^{2} \ r_{2}(x) &= x^{5} + x^{3} + 1 \ r_{3}(x) &= x^{4} + x^{2} \ r_{4}(x) &= 1 \ r_{5}(x) &= 0 \end{align*} $$
因此：
$$ \begin{align*} 1 &= r_{4}(x) \ &= r_{2}(x) - q_{4}(x)r_{3}(x) \ &= r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) r_{2}(x) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) \big(m(x) - q_{2}(x)r(x)\big) \ &= \Big(-q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x)\Big) r(x) + \Big(1 + q_{r}(x)\Big) m(x) \end{align*} $$
所以，我們得到：
$$ \begin{align*} r^{-1}(x) & = - q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x) & \mod 2 \ & = - x - x - x(x^{2} + 1) & \mod 2 \ & = - x - x - x^{3} - x & \mod 2 \ & = - x^{3} - 3x & \mod 2 \ & = x^{3} + x \end{align*} $$
但是，這是錯誤的，因為當我計算 $ r^{-1}(x) r(x) \mod m(x) $ 結果不是 1
問題是在哪裡 $$ r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big) $$變成$$ \big(-q_{4}(x)\big) r(x) +\big(1 + q_{3}(x)\big) r_{2}(x) $$那應該是什麼時候$$ \big(-q_{4}(x)\big) r(x) +\big(1 + q_{4}(x)\cdot q_{3}(x)\big) r_{2}(x) $$
獨立地，我認為最好使用那裡簡單得多的算法，它只需要跟踪 4 個變數。