Я имею дело с полями Галуа $GF(2^{8})$ и нужна помощь в поиске
многочлен $ г ^ {- 1} (х) $ такой, что $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$
- $ т (х) = х ^ {4} + х ^ {2} + 1 $
Таким образом:
- $u(x) = x^{11} + x^{8} + x^{6} + x^{4} + x^{3} + x$
- $д(х) = х^{3} + 1$
- $r(x) = -x^{7} - x^{4} - x^{3} + 1 \mod 2 = x^{7} + x^{4} + x^{3} + 1$
что я пробовал
я пытался выяснить $ г ^ {- 1} (х) $ но не удалось.
Вот что я пробовал:
Из алгоритма Евклида:
\начать{выравнивать*}
u(x) &= q(x) \cdot m(x) + r(x) \
m(x) &= q_{2}(x) \cdot r(x) + r_{2}(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) \ \
&= (х^{2} + 1) \cdot r_{2}(х) + (х^{4} + х^{2}) \
r_{2}(x) &= q_{4}(x) \cdot r_{3}(x) + r_{4}(x) \
&= х \cdot r_{3}(х) + 1 \
r_{3}(x) &= q_{5}(x) \cdot r_{4}(x) + r_{5}(x) \
&= (х^{4} + х^{2}) \cdot r_{4}(х) + 0
\конец{выравнивание*}
У нас есть:
\начать{выравнивать*}
q_{2}(х) &= х \
q_{3}(x) &= x^{2} + 1 \
q_{4}(х) &= х \
q_{5}(x) &= x^{4} + x^{2} \
r_{2}(x) &= x^{5} + x^{3} + 1 \
r_{3}(x) &= x^{4} + x^{2} \
г_{4}(х) &= 1 \
г_{5}(х) &= 0
\конец{выравнивание*}
Таким образом:
\начать{выравнивать*}
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)
\конец{выравнивание*}
Итак, мы получаем:
\начать{выравнивать*}
г ^ {- 1} (х)
& = - q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x) & \mod 2 \
& = - х - х - х (х ^ {2} + 1) & \mod 2 \
& = - х - х - х^{3} - х & \mod 2 \
& = - х^{3} - 3x & \mod 2 \
& = х^{3} + х
\конец{выравнивание*}
Но это неправильно, потому что когда я вычисляю $r^{-1}(x) r(x) \mod m(x)$
результат не 1