Rechnen in Galois-Felder? Wer kennt sich aus?
Nik Wiesel
ich moechte gerne wissen wie man in Galois Feldern rechnet.
Soweit ich das richtig ueberblicke erfuellen Galois-felder die
Koerperaxiome. Es muessen demnach zwei Verknuepfungen definiert sein: eine
"Addition" und eine "Multiplikation".
Die Addition soll wohl einer exclusiv-oder Verknuepfung entsprechen und
damit auch gleich der Subtraktion sein.
Was ich nicht verstehe ist, wie die Multiplikation und die Division
funktioniert. Weiterhin verstehe ich nicht, was die Redewendung bedeuted
die sagt, "das Galois-feld wird durch das Primitive Polynom generiert".
Als Referenz nenne ich hier mal das Buchvon MacWilliams und Sloane mit dem
titel "The Theory of Error Correcting Codes" 2. Neudruck von 1983.
Auf S.82 dieses Buches kann ich der Erklaerung nicht folgen.
Wer kann mir da helfen? Mit moeglichst wenig Fachsprache.
Antworten bitte auch an mich, Danke...
---------------------------------------
Nik Wiesel: uzs...@ibm.rhrz.uni-bonn.de
===============================================================
The above statement is my own opinion and does not represent
the point of view of any organization I am related to.
===============================================================
Lutz Donnerhacke
>Was ich nicht verstehe ist, wie die Multiplikation und die Division
>funktioniert. Weiterhin verstehe ich nicht, was die Redewendung bedeuted
>die sagt, "das Galois-feld wird durch das Primitive Polynom generiert".
Addition und Multiplikation unter Polynomen sei so definiert, wie gewohnt,
d.h. gliedweise bzw. nach Cauchy.
Bei der Addition kann der Grad der Polynome nicht steigen, wohl aber bei der
Multiplikation.
Nehmen wir das Polynom x³-x+1=0 und betrachten die Multiplikation von
x²+x=0 und x²-5=0 im Galoisfeld bzgl. dieses Polynoms:
0 = (x²+x)(x²-5) = x^4+x³-5x²-5x
= x(x-1) + x-1 - 5x² - 5x (Ersetzung aka modulo Polynom)
= -4x²-5x-1
PS:
Galois-Felder sind primäre Felder, d.h. Ringe aus Units.
Units sind Elemente eines Rings, die multiplikativ invertierbar sind.
Ein Ring ist ein Gebilde aus einer Menge, einer Gruppe und einem Monoid,
die beidseitig distributiv verknüpft sind.
Die Gruppe wird als Addition, der Monoid als Multiplikation bezeichnet.
Man kann zeigen, daß die Gruppe immer abelsch ist.
Felder sind somit Gebilde aus einer Menge und beidseitig distributiv
verknüpfter Gruppen.
Markus Kuhn
> ich moechte gerne wissen wie man in Galois Feldern rechnet.
engl. math. "field" -> deutsch "Körper", daher heißt es auch Galois Körper
oder einfach Endlicher Körper.
Literaturtip dazu:
Rudolf Lidl, Harald Niederreiter: Introduction to finite fields
and their applications. Cambridge Univ. Press, 1986,
ISBN 0-521-30706-6.
Kurzzusammenfassung: Galois Körper kann man sich als Arithmetik ueber
Polynomen vorstellen. Die Polynome sind dabei Polynome ueber einem
endlichen Körper (zum Beispiel dem Körper der natürlichen Zahlen
modulo eine Primzahl p, GF(p)), und diese Polynomarithmetik fuehrst du
dann modulo einem irreduziblem Polynom aus. Wenn dieses irreduzible
Polynom (stell dir darunter eine Art "Primpolynom" vor, die genaue
definition ist etwas aufwendiger) den Grad n hat, dann schreibt man fuer
den dadurch erzeugten endlichen Koerper GF(p^n), da er p^n elemente hat.
Bekanntestes Alltagsbeispiel fuer den Einsatz von Galois-Feldern ist
die CRC-Pruefsumme in deinem Modem, deiner Ethernet-Karte, oder
deiner Festplatte. Dabei verwendet man Polynome n-then Grades ueber den Bits 0
und 1, also eine GF(2^n) Arithmetik. Die hat den Vorteil dass sie einfacher
als die Arithmetik der natuerlichen Zahlen in Hardware zu gießen ist,
da der Uebertrag in der Polynomarithmetik wegfaellt, und man die
Division mit einem trivialen linear feedback shift register implementieren
kann (warum wird am schnellsten klar, wenn du von Hand mal binaere
Polynome dividierst und genau aufpasst welcher einfache Algorithmus
dabei eigentlich abläuft).
Hope this helped ...
Markus
--
Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK
email: mkuhn at acm.org, home page: <http://www.cl.cam.ac.uk/~mgk25/>