Restklassenringe

Im ersten Semester lernt man im Informatikstudium Restklassenringe kennen. Diese bilden die mathematische Basis für diverse Kryptographie (beispielsweise RSA), aber auch anderes Zeug wie CRC. Gestern hatte ich im Forum mal ne oberflächliche Einführung in das Thema gegeben. Und damit das nicht verloren geht, will ich das hier nochmal posten. Wer also kein Informatik studiert, aber aus welchen Gründen auch immer wissen will, was modulare Arithmetik ist und wie man in Restklassenringen rechnet, hier eine knappe Einführung.

Höhere Mathematik für programmierende Nicht-Akademiker — Heute: Restklassenringe

Grundlagen: Algebraische Strukturen

In der Mathematik basiert alles auf Mengen (Mengenlehre, Schnittmenge, Teilmenge, Vereinigungsmenge und so). Mit den Elementen einer Menge kann man rechnen, d.h. es gibt verschiedene Operationen, die auf der Menge definiert sind.

Aus der Schule kennen wir die Menge der Reellen Zahlen: \mathbb{R}. Aus der Menge der Reellen Zahlen \mathbb{R} machen wir eine algebraische Struktur, indem wir ihr Operationen spendieren: (\mathbb{R}, +, \cdot)

Wendet man eine der Operationen auf ein Element der Menge an, erhält man als Ergebnis wieder ein Element der Menge. 2+3 = 5 und 2 \cdot 3 = 6 (5 und 6 sind wieder reelle Zahlen). Das nennt man Abgeschlossenheit.

Es gibt verschiedene Arten von algebraischen Strukturen für die jeweils andere Anforderungen gelten. So gibt es beispielsweise Gruppen, Ringe und Körper. Die Unterschiede sind hier erstmal nicht weiter wichtig.

Beispiel

Man kann nicht nur mit den Reellen Zahlen rechnen, sondern beispielsweise auch mit Natürlichen Zahlen (\mathbb{N}). Das haben wir in der Grundschule gelernt. Wir haben da erfahren, dass 5-7 „nicht geht“. Später haben wir negative Zahlen kennen gelernt und auf einmal ging das doch. Trotzdem haben uns unsere Lehrer in der Grundschule nicht angelogen. 5-7 geht wirklich nicht — in der Halbgruppe (\mathbb{N}, +).

In der Programmierung begegnen uns ständig solche algebraischen Strukturen. (\texttt{String}, +) ist z.B. auch eine Halbgruppe. Wir können Strings konkatenieren und erhalten wieder Strings (String ist abgeschlossen bezüglich der Operation +) und + ist assoziativ: ('a' + 'b') + 'c' = 'a' + ('b' + 'c'). Diese zwei Eigenschaften brauchen wir um (\itexttt{String}, +) Halbgruppe nennen zu können. Außerdem haben wir noch den Leerstring als neutrales Element. 'a' + '' = 'a'. Wir dürfen (\texttt{String}, +) deshalb sogar einen „Monoid“ nennen.

Inverse Elemente

Die Operationen - und / haben wir oben nicht etwa vergessen. Sie ergeben sich quasi automatisch aus + und \cdot. 7 - 5 ist nämlich nichts anderes als 7 + (-5), wobei -5 das inverse Element (bezüglich der Addition) von 5 ist. Das inverse Element bezüglich der Multiplikation wäre \frac{1}{5}, d.h. 0,2. Ein Element verknüpft mit seinem inversen ergibt immer das neurale Element (bezüglich der Operation). 5 + (-5) = 0 (additiv inverses) 5 \cdot 0,2 = 1 (multiplikativ inverses).

Restklassenringe

Ein Restklassenring ist eine algebraische Struktur, bei der die Menge Restklassen sind. Eine Restklasse ist z.B. \mathbb{Z}/24\mathbb{Z}. \mathbb{Z}/24\mathbb{Z} hat genau 24 Elemente, nämlich die Zahlen 0 bis 23. Definiert man noch Addition und Multiplikation, erhält man einen Restklassenring: (\mathbb{Z}/24\mathbb{Z}, +, \cdot).

In einem Restklassenring rechnet es sich in etwa so, wie mit Uhrzeiten. Nach 23 Uhr kommt wieder 0 Uhr:

20 (Uhr) + 7 (Stunden) = 27 (Uhr) = 3 (Uhr)

oder mathematisch geschrieben:

 20 + 7 (\mod 24) = 27 (\mod 24) = 3 (\mod 24)

Die Modulooperation gibt also an, in welchem Restklassenring du dich befindest. Hier in \mathbb{Z}/24\mathbb{Z}. Alle „Zahlen“ die den selben Rest beim Teilen durch 24 aufweisen sind in der selben Restklasse und damit „gleich“. Also:

27 = 3 (\mod 24)

Um entsprechend einfacher rechnen zu können, benutzt du die Modulo-Operation und erhältst immer eine Zahl zwischen 0 und 23:

27 \mod 24 = 3

Genau so ist es mit den negativen Zahlen:

0 (Uhr) – 1 (Stunde) = -1 (Uhr) = 23 Uhr

oder mathematisch:

0 - 1 (\mod 24) = -1 (\mod 24) = 23 (\mod 24)

Achtung

Die Modulo-Operation ist nicht in jeder Programmiersprache gleich definiert. Manchmal entspricht sie der oben verwendeten mathematischen Definition, manchmal ist es anders. Will man in Restklassenringen rechnen, muss man das für negative Zahlen bedenken und ggf. Korrekturen vornehmen. http://en.wikipedia.org/wiki/Modulo_operation#Common_pitfalls

Ausblick

Alle Restklassenringe \mathbb{Z}/p\mathbb{Z} mit einer Primzahl p, sind nicht nur Ringe, sondern Körper, d.h. jedes Element hat ein multiplikatives inverses Element. Das ist in der Kryptographie wichtig und wird u.a. bei RSA verwendet.

2 Kommentare


  1. Vielen Dank dafür 🙂 – das war mit Abstand die einfachste Erklärung, für Restklassen, die ich finden konnte! Ist zwar ein klein bisschen zu allgemein für nicht-informatik-mathematik, aber den Rest kann ich mir (hoffentlich^^) herleiten :).

    Werde noch mehr durch dein Blog stöbern und gucken, was ich sonst noch finden kann :D.


  2. Super danke! Viel verständlicher als in der Vorlesung 😀

Comments are closed, but trackbacks and pingbacks are open.