Modulare Arithmetik - "Hilfe, mein Kopf brummt!"

Modular arithmetic is a system of arithmetic for integers, where numbers wrap around when reaching a certain value, called the modulus.

Modulare Arithmetik, was für ein Brocken an Wort. Mein Ziel ist es für die nächsten Minuten, dir das Thema ein wenig näher bringen. Fangen wir doch mal mit der wichtigsten Frage an, wo nutzen wir diese Mathematik? Laut Wikipedia ist die mod. Arithm. eine der Eckpfeiler der Zahlentheorie und greift nahezu alle Aspekte dieses Gebietes auf. Im Praktischen wird sie in der Kryptografie, IT generell als auch in der Chemie und visuellen und musikalischen Kunst aufgegriffen.

Der ISBN nutzt MA (Modulare Arithmethik) beispielsweise zur Fehlerkorrektur, RSA und DH(Diffie-Hellman) nutzen sie für ihre finiten Felder (auf die Elliptic Curve Verschlüsselungsverfahren aufbauen) ebenso wie AES, IDEA und RC4 für ihre modulare exponentation. Aber genug von Beispielen, wenn du mehr möchtest, werden diese auf Wikipedia[1] zur Genüge erklärt.

Na dann, ab damit!

Grundlegende Syntax von Modulo Operationen

Die Gleichung entspricht  15 mod 7 = 1 und 1 mod 7 = 1
Im Englischen spricht man bei den beiden Ergebnissen von Congurence.

Kongurenz schreibt man auch gerne mit dem Dreistrichgleich an.
(ich nenne das Teil jetzt einfachheitshalber mal so)

Was sagt nun diese Congurence aus? Es sagt aus, dass 15 mod 7 und 1 mod 7 denselben Rest ergeben.

Um das Verhalten in der MA besser verständlich zu machen, nutzt man eine Uhr oder auch ein Riesenrad. Ich finde die Darstellung als einfach verkettete Liste, dessen letzter Pointer wieder auf das erste Element zeigt, jedoch am einfachsten.

Der Wertebereich einer mod n Operation liegt immer zwischen 0 und n-1. Also haben wir bei mod 7 einen W von {0,1,2,3,4,5,6}. Rotationen, oder auch Bewegungen werden in x/n-tel gemessen. Eine ganze Umrundung, sodass man wieder am Beginn landet, wäre also bei mod 7 eine n/n-tel oder 7/7-tel Rotation.

Addieren mit Modulo Operationen

Beginnen wir doch mal mit einer ersten Addition:

Wie kommt man jetzt auf das Ergebnis von 4?
  
>[0][1][2][3][4][5][6]>

Wir beginnen wie es die Syntax von uns verlangt bei 5 und wandern dann um eine Rotation von 6 nach rechts. 
 >[0][1][2][3][4][5][6]>
Rot = Startposition, Blau = Rotationsweg, Pink = Ergebnis/Zielposition

Wenn Rechtsrotation = Addition, dann wird Linksrotation wohl der Subtraktion entsprechen.

<[0][1][2][3][4][5][6]<
<[0][1][2][3][4][5][6]<

Multiplizieren mit Modulo Operationen

Bei der Multiplikation wird zuerst vorgerechnet. Nehmen wir folgende Rechnung als Beispiel:

Hier rechnen wir zuerst die Multiplikation aus, also 5*4=20.
Dann wird 20 mod 7 genommen und wir kommen auf 6.

Bei 5*4 würden wir also 2x ganze Runden (20/7=2,...) drehen.
Die restlichen 6 stellen dann den tatsächlichen Wert an, alle vollen Rotationen kann man also aus der Operation herauskürzen.



Multiplikationen beginnen mit 0. Zur Veranschaulichung, hier die geschleifte Liste:
[0][1][2][3][4][5][6][0][1][2][3][4][5][6][0][1][2][3][4][5][6][0]>
 |.................|  |.................|  |.................|  |..

Dividieren mit Modulo Operationen

Die Division geht das ganze Konzept rückwärts an, aber zuerst unser neues Beispiel:

5 ist hier unsere Zielposition und 2 die Schrittlänge.
Bei der Division möchten wir auf die Anzahl der Schritte(6) kommen.
Wir beginnen bei 5 und schreiten so lange vorwärts bis wir bei 0 ankommen.

Zur Veranschaulichung, die geschleifte Liste:

     |--+--<--+--<--+--<--+--<--+--<--+--|
<[6][0][1][2][3][4][5][6][0][1][2][3][4][5][6] 
..|  |.................|  |.................|


Damit hätten wir ja bereits fast alles durch, fehlt nur noch ein Exponent ^^

 

Exponentiale mit Modulo Operationen

Für Exponenten wie das folgende Beispiel dividieren wir durch das Ergebnis und addieren den Rest.

64 durch 7 ist 9 +1.
Dieses "+1" zieht sich durch alle a^6 (mod 7) durch. Das führt uns zu Fermat's kleiner Theorie.

Fermat's kleine Theorie

Diese Theorie ist eine Methode um Primzahlen zu erkennen und ist auch Basis für die Eulersche Theorie. Um das nun zu verstehen, müssen wir noch schnell die Eigenschaft Coprime oder Teilerfremd[2] kennenlernen, sie besagt, dass eine Zahl kein Vielfaches einer anderen Zahl ist.

Fermat's Theorie besagt:

a^(n-1) = 1 (mod n)

n ist eine Primzahl, wenn man a hoch n-1 nimmt, es durch den Modulo-Faktor n dividiert und ein Rest von 1 heraus kommt. Das trifft jedoch nur zu, wenn a teilerfremd zu n ist!

Fermat war ein ziemlicher Hammer, man nennt ihn ja sogar den Vater der Zahlentheorie. Aber mehr dazu vielleicht in einem anderen Teil. Wir sind hier für heute fertig, und du weißt jetzt mit modularer Arithmetik umzugehen, there you go! c:

Gratuliere, jetzt hast du dir aber wirklich eine Pause verdient! :)


Als Anmerkung muss man bei der Listendarstellung noch hinzufügen, dass die Bezeichnung "Zielposition" etwas verwirrend sein mag. Bei der hier vorliegenden Liste (beginnend mit 0) ist es dennoch korrekt, auch wenn die Bezeichnung "Zielwert" wohl verwirrender aber auch korrekter wäre.

[1]: wikipedia.org
[2]: wikipedia.org