Berechnung im Galois Feld

19.10.2009, 18:52

mati

Berechnung im Galois Feld

Hallo,

ich bin neu hier und hab natürlich gleich eine frage, da ich mich mit dem Galois Feld nicht wirklich auskenne.

Ich soll im Galois Feld GF( $\begin{eqnarray*} 2^{4} \end{eqnarray*}$ ) folgende Ausdrücke bezüglich des irreduziblen Poliynoms $\begin{eqnarray*} t^{4}+t+1 \end{eqnarray*}$ berechnen:

$\begin{eqnarray*} 2*(t+1) \end{eqnarray*}$ und $\begin{eqnarray*} (t^{3}+t)*(t^{2}+t+1) \end{eqnarray*}$

mir ist klar, was ein Galois Feld ist aber ich bin mir jetzt nicht sicher, wie ich die Ausdrücke bezüglich des irreduziblen Polynoms berechnen soll.

Wikipedia (endliche Felder, Galois, irreduzible Polynome) und http://cryptoman.com hab ich mir schon durchgelesen...

jemand vielleicht eine idee oder noch etwas wo ich suchen könnte?

danke schonmal,

Mati

19.10.2009, 19:01

kiste

Auf diesen Beitrag antworten »

Das heißt nichts anderes als dass du normal rechnen sollst, aber für jedes t^4 kannst du eben -t-1 einsetzen

Die erste Berechnung ist eine reine Verständnisfrage

19.10.2009, 19:39

mati

Auf diesen Beitrag antworten »

hallo kiste,

vielen dank für deine antwort.

leider ist in den berechnungen kein $\begin{eqnarray*} t^{4} \end{eqnarray*}$ vorhanden.

wie soll ich das da ersetzen?

und woher weiss ich das? nehm ich dann einfach wegen dem $\begin{eqnarray*} 2^{4} \end{eqnarray*}$ das $\begin{eqnarray*} t^{4} \end{eqnarray*}$ vom irreduziblen polynom weg oder wie mach ich das?

oder muss ich das gleichsetzen also $\begin{eqnarray*} -t-1=2*(t+1) \end{eqnarray*}$ ?

danke schonmal,

mati

19.10.2009, 19:50

Elvis

Auf diesen Beitrag antworten »

Da 2=-1 ist in $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ , stimmt das schon mal.
Für die 2. Aufgabe empfiehlt sich Ausmultiplizieren, dann bekommst du nicht nur t^4, sonder sogar t^5 Augenzwinkern

19.10.2009, 19:59

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Da 2=-1 ist in $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ , stimmt das schon mal.

Nein!

Und du sollst nichts gleichsetzen sondern nur einfach ausrechnen.
Beachte dabei dass F_16 die Charakteristik 2 hat, was bedeutet das für dich?

19.10.2009, 20:07

Elvis

Auf diesen Beitrag antworten »

Ach du liebe Zeit. Nein ! Natürlich nicht. Ich bin so doof Hammer

, dass ich auf sowas reinfalle.

19.10.2009, 20:49

mati

Auf diesen Beitrag antworten »

hallo,

danke für eure antworten,

aber in den ausdrücken ist doch garkein $\begin{eqnarray*} t^{4} \end{eqnarray*}$ drin, wie kann ich das dann ersetzen und ausrechnen?

ich sehs irgendwie nicht unglücklich

danke für eure hilfe,

mati

19.10.2009, 22:38

kiste

Auf diesen Beitrag antworten »

multiplizier doch erstmal aus und dann sehe weiter.

19.10.2009, 22:53

mati

Auf diesen Beitrag antworten »

hi,

ich hab das jetzt mal ausgerechnet, bin mir aber nicht sicher ob das so richtig ist und warum ich das überhaupt gemacht hab :S

also aus $\begin{eqnarray*} t^{4}+t+1 \end{eqnarray*}$ folgt offensichtlich $\begin{eqnarray*} -t-1 \end{eqnarray*}$

erster Ausdruck: $\begin{eqnarray*} 2*(t+1) = (2t+2) \end{eqnarray*}$ das rechnen wir nun zusammen: $\begin{eqnarray*} (2t+2) + (-t-1) = t+1 \end{eqnarray*}$

zweiter ausdruck:

$\begin{eqnarray*} (t^{3}+t)*(t^{2}+t+1) \end{eqnarray*}$ ausmultipliziert sowas: $\begin{eqnarray*} (t^{5}+t^{4}+2t^{3}+t^{2}+t) \end{eqnarray*}$

und das dann zusammen rechnen

$\begin{eqnarray*} (t^{5}+t^{4}+2t^{3}+t^{2}+t) + (-t-1) \end{eqnarray*}$

ergibt $\begin{eqnarray*} t^{5}+t^{4}+2t^{3}-1 \end{eqnarray*}$

ist das richtig, oder lieg ich voll daneben?

danke schonmal,

Gruss Mati

20.10.2009, 06:33

kiste

Auf diesen Beitrag antworten »

Du musst dir erst einmal klar sein was und wo du genau rechnest!

Es ist $\begin{eqnarray*} \mathbb F_{16} \cong \mathbb F_2[t]/\langle t^4+t+1\rangle \end{eqnarray*}$ . ( $\begin{eqnarray*} \mathbb F_n \end{eqnarray*}$ ist die moderne Schreibweise für GF(n))

Das heißt du rechnest zuerst im Polynomring $\begin{eqnarray*} \mathbb F_2[t] \end{eqnarray*}$ deine Ergebnisse aus. Dann musst du sie in einen Repräsentanten umwandeln. D.h. in ein Polynom von Grad kleiner gleich 3.
Dazu darfst du nutzen dass $\begin{eqnarray*} t^4 + t + 1 = 0 \end{eqnarray*}$ also $\begin{eqnarray*} t^4 = -t - 1 = t + 1 \end{eqnarray*}$ (Warum darf man hier - mit + ersetzen?!)
Also setzt du für jedes $\begin{eqnarray*} t^i \end{eqnarray*}$ mit $\begin{eqnarray*} i\geq 4 \end{eqnarray*}$ eben $\begin{eqnarray*} t^i = t^{i-4}t^4 = t^{i-4}(t+1) \end{eqnarray*}$ ein. Das machst du solange bis du nur noch Grad kleiner gleich 3 hast.

Insbesondere macht es natürlich keinen Sinn irgendwie wild -t-1 irgendwo hinzuschreiben! Also du hast richtig ausmultipliziert, aber das -t-1 bitte weglassen!

Und was soll es heißen dass aus einem Term ein Term folgt? Aus Termen folgt nichts, aus Aussagen folgt etwas!

20.10.2009, 19:05

mati

Auf diesen Beitrag antworten »

Hey, danke für eure antworten, die sache wurde heute in der vorlesung aufgeklärt. ich schreib hier mal meine lösung hin, falls dsa problem noch mehr haben:

also, aus $\begin{eqnarray*} t^{4}+t+1=0 \end{eqnarray*}$ kann man ja errechnen, dass $\begin{eqnarray*} t^{4}=-t-1 \end{eqnarray*}$ ist. Da das Alphabet $\begin{eqnarray*} GF(2^{4}) = {0,1} \end{eqnarray*}$ ist und $\begin{eqnarray*} 1+1=0 \end{eqnarray*}$ (laut galois glaub ich) ist, kann man auch $\begin{eqnarray*} t+1 \end{eqnarray*}$ schreiben.

Man darf maximal ein Polynom der Ordnung 3 haben, darum muss man alle $\begin{eqnarray*} t^{4} \end{eqnarray*}$ mit $\begin{eqnarray*} t+1 \end{eqnarray*}$ ersetzen. Somit wird auch z.b. aus $\begin{eqnarray*} t^{5} = t(t+1) \end{eqnarray*}$ , denn $\begin{eqnarray*} t^{5} = t * t^{4} = t * t * t^{3} = ... \end{eqnarray*}$ .

So dann fängt man an auszumulitiplizieren:

$\begin{eqnarray*} (t^{3}+t) * (t^{2}+t+1) \end{eqnarray*}$
$\begin{eqnarray*} = t^{5}+t^{4}+t^{3}+t^{3}+t^{2}+t \end{eqnarray*}$

wie gesagt, $\begin{eqnarray*} 1+1=0 \end{eqnarray*}$ also ist $\begin{eqnarray*} t^{3}+t^{3}=0 \end{eqnarray*}$ . kann man also streichen.

$\begin{eqnarray*} = t^{5}+t^{4}+t^{2}+t \end{eqnarray*}$

so, jez haben wir noch $\begin{eqnarray*} t^{5} \end{eqnarray*}$ und $\begin{eqnarray*} t^{4} \end{eqnarray*}$ stehen. wir dürfen aber maximal $\begin{eqnarray*} t^{3} \end{eqnarray*}$ haben, also tauschen wir $\begin{eqnarray*} t^{4} \end{eqnarray*}$ mit $\begin{eqnarray*} 1+t \end{eqnarray*}$ aus.

$\begin{eqnarray*} = t(t+1) + t + 1 +t^{2} + t \end{eqnarray*}$

ausgerechnet: $\begin{eqnarray*} = t^{2} + t +t +1 +t^{2} + t \end{eqnarray*}$

die beiden $\begin{eqnarray*} t \end{eqnarray*}$ und die beiden $\begin{eqnarray*} t^{2} \end{eqnarray*}$ verschwinden und es bleibt $\begin{eqnarray*} t+1 \end{eqnarray*}$ übrig.

Bei fehlern bitte berichtigen smile

Gruss, Mati

20.10.2009, 22:21

kiste

Auf diesen Beitrag antworten »

1+1=0 gilt weil die Charakteristik des Körpers 2 ist.
Allgemein gilt in endlichen Körpern der Ordnung p^n dass 0 = 1+1+...+1 (p-mal die 1 addiert)

Neue Frage »

Antworten »

Berechnung im Galois Feld

Verwandte Themen