Cryptography Reference
In-Depth Information
Überprüfen Sie das Ergebnis durch Multiplikation: b(x)·a(x)={11100001}·{00001101}
Lösung
11100001 • 1101
11100001
11100001
11100001
10001101101 ...Ergebnis der Multiplikation
100011011
...modulo {100011011}
1
...das Produkt ergibt erwartungsgemäß den Wert 1.
Übung 3
Berechnen Sie zu dem Element a(x)={00000111} das multiplikativ inverse Element a
1
(x) =
b(x) in GF(2
8
) bezüglich M(x)={100011011}.
Lösung
ggT({100011011},{111})
ggT({111},{11}) {11}={100011011}-{111}·{1101000} *)
ggT({11},{1}) {1}={111}-{11}·{10} **)
Durch Einsetzen von *) in **) ergibt sich:
{1}{111}+{100011011}·{10}+{111}·{1101000}·{10} (mod 2),
{1}{111}·
{11010001}
(mod{100011011}.
Zur Erinnerung: Addition und Subtraktion sind mod 2 das Gleiche.
Das Ergebnis ist b(x)={11010001}.
Übung 4
Die beiden Polynome P
1
(x)={110001} und P
2
(x)={111001001} sind nicht relativ prim zuei-
nander, d.h. sie haben ein nicht-triviales gemeinsames Teilpolynom. Bestimmen Sie dieses mit
Hilfe des erweiterten Euklidischen Algorithmus.
Lösung
ggT({111001001},{110001})
ggT({110001},{10010}) {10010}={111001001}mod{110001}
ggT({10010},{111}) {111}={110001}{10010}
ggT({111},{0}) D.h. das Ergebnis ist ggT={111}.
Der größte gemeinsame Teiler von {111001001} und {110001} ist {111}.
