W ciele GF(25) zdefiniowanym przez wielomian x5+x3+1 wyznaczyć element odwrotny Marta: W ciele GF(25) zdefiniowanym przez wielomian x5+x3+1 wyznaczyć element odwrotny do 10110. Wybierz odpowiedź a. 10000 b. 00010 c. 00100 d. 01000

Wojtek: W tym zadaniu chodzi o użycie rozszerzonego algorytmu Euklidesa. Niech f(x)=x⁵+x³+1, a 10110 zapiszmy jako g(x)=x⁴+x²+x. Następnie zapiszmy równanie NWD(f(x),g(x)) = t(x)*f(x) + u(x)*g(x) Opis działania algorytmu: Przyporządkujmy: a(x)=f(x) b(x)=g(x) 1. Wykonujemy dzielenie a(x)/b(x), z czego wynika, że a(x) = q(x)*b(x)+r(x), gdzie q(x) to wynik dzielenia, r(x) to reszta. Warto przekształcić równanie do postaci r(x)=a(x)−q(x)*b(x) 2. Jeśli r(x)≠0, to a(x):=b(x), b(x):=r(x) i wracamy do kroku 1. W przeciwnym razie kończymy działanie algorytmu. Ostatnia uzyskana niezerowa reszta z dzielenia, to NWD(f(x),g(x)). Jeśli da się policzyć odwrotność g(x), to NWD powinien wynosić 1. Mając ostatnie równanie uzyskane z działania algorytmu, w kolejnych krokach podstawiamy wartości r(x) uzyskane z wcześniejszych równań, przez co powinniśmy uzyskać wynik postaci: NWD(f(x),g(x)) = t(x)*f(x) + u(x)*g(x), zaś u(x) to szukany element odwrotny. Wykonując kolejne dzielenia z rozszerzonego algorytmu Euklidesa uzyskałem równania: (1) x²+1 = x⁵+x³+1 − x*(x⁴+x²+x) (2) x = x⁴+x²+x − x²*(x²+1) (3) 1 = x²+1 − x*x Podstawiam (2) i (1) do równania (3): 1 = (x²+1) − x*x = (x⁵+x³+1) − x*(x⁴+x²+x) − x*[(x⁴+x²+x) − x²*(x²+1)] 1 = (x⁵+x³+1) − x*(x⁴+x²+x) − x*[(x⁴+x²+x) − x²*[(x⁵+x³+1) − x*(x⁴+x²+x)]] z tego uzyskuję 1 = (1+x³)(x⁵+x³+1) + x⁴*(x⁴+x²+x) = t(x)*f(x) + u(x)*g(x) Wynikiem jest u(x)=x⁴. Można sprawdzić, że: [u(x)*g(x)](mod f(x)) = 1

Wojtek: Zapomniałem dodać że w treści zadania raczej powinno być: W ciele GF(2⁵) zdefiniowanym przez wielomian x⁵+x³+1 wyznaczyć...