Puncte:0

Găsiți inversul multiplicativ în câmpul Galois $2^8$ folosind algoritmi extinși Euclides

drapel sx

Am de-a face cu câmpurile Galois $GF(2^{8})$ și au nevoie de ajutor pentru a găsi a polinom $r^{-1}(x)$ astfel încât $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, Unde:

  • $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$

Prin urmare:

  • $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$

ce am incercat

Am încercat să aflu $r^{-1}(x)$ dar a eșuat.

Iată ce am încercat:

Din algoritmul lui Euclides:

\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*}

Avem:

\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*}

Prin urmare:

\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*}

Deci, obținem:

\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*}

Dar, acest lucru este greșit pentru că atunci când calculez $r^{-1}(x) r(x) \mod m(x)$ rezultatul nu este 1

drapel us
de unde vine "modul 2"?
blackyellow avatar
drapel sx
@SamGinrich modul 2 este pentru că suntem în $GF(2^n)$
drapel us
$GF(2^n)$ este ceva modulo $m(x)$
blackyellow avatar
drapel sx
Scuze, nu am inteles ce am gresit..Am probleme cu înțelegerea algoritmului (de aceea am nevoie de ajutor). Am calculat $\mod 2$ pentru că am crezut că coeficienții polinomi trebuie să fie în $\{0,1\}$ deoarece avem de-a face cu octeți. Dacă îmi poți explica ce am greșit, aș aprecia!
fgrieu avatar
drapel ng
Bănuiesc că se dorește inversul polinom al lui $s(x)\cdot t(x)$ modulo $m(x)$, iar pentru aceasta definiți $r(x)=s(x)\cdot t(x)\ bmod m(x)$. Fără această definiție nu reușesc să înțeleg _astfel_ $u(x)=s(x)\cdot t(x)$.
blackyellow avatar
drapel sx
@fgrieu Am uitat sa mentionez ca $u(x) = s(x) \cdot t(x)$ pentru ca este definit asa in problema
Puncte:1
drapel ng

O problemă este unde $$r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big)$$devine$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{3}(x)\big) r_{2}(x)$$când ar trebui să fie$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{4}(x)\cdot q_{3}(x)\big) r_{2}( x)$$


În mod independent, cred că cel mai bine ar fi să folosiți algoritmul semnificativ mai simplu Acolo, care trebuie să țină evidența doar a 4 variabile.

blackyellow avatar
drapel sx
Mulțumesc! Acolo am greșit! Dumnezeu să vă binecuvânteze pentru că aveam atât de mult stres cu această întrebare...
blackyellow avatar
drapel sx
Apropo, am implementat algoritmul mai simplu despre care ai vorbit în locul celui pe care îl foloseam anterior.... mulțumesc!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.