Рейтинг:0

Найдите мультипликативное обратное в поле Галуа $2^8$, используя расширенные алгоритмы Евклида

флаг sx

Я имею дело с полями Галуа $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

флаг us
откуда "мод 2"?
blackyellow avatar
флаг sx
@SamGinrich мод 2 потому что мы в $GF(2^n)$
флаг us
$GF(2^n)$ есть что-то по модулю $m(x)$
blackyellow avatar
флаг sx
Извините, я не понял, что я сделал не так..У меня проблемы с пониманием алгоритма (поэтому мне нужна помощь). Я вычислил $\mod 2$, потому что думал, что полиномиальные коэффициенты должны быть в $\{0,1\}$, поскольку мы имеем дело с байтами. Если вы можете объяснить, что я сделал неправильно, я был бы признателен!
fgrieu avatar
флаг ng
Я предполагаю, что требуется многочлен, обратный $s(x)\cdot t(x)$ по модулю $m(x)$, и для этого вы определяете $r(x)=s(x)\cdot t(x)\ bmod m(x)$. Без этого определения я не могу понять _thus_ $u(x)=s(x)\cdot t(x)$.
blackyellow avatar
флаг sx
@fgrieu Я забыл упомянуть, что $u(x) = s(x) \cdot t(x)$, потому что так определено в задаче
Рейтинг:1
флаг ng

Проблема в том, где $$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}( х)$$


Независимо, я думаю, было бы лучше использовать значительно более простой алгоритм там, который должен отслеживать только 4 переменные.

blackyellow avatar
флаг sx
Спасибо! Вот где я ошибся! Благослови вас Бог, потому что у меня было так много стресса с этим вопросом ...
blackyellow avatar
флаг sx
Кстати, я реализовал более простой алгоритм, о котором вы говорили, вместо того, который я использовал ранее.... спасибо!

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.