Mathematische Grundlagen 2: Unterschied zwischen den Versionen
Zeile 46: | Zeile 46: | ||
<br> | <br> | ||
<br> | <br> | ||
− | Nach | + | Nach Definition 2.0 gilt für a ≡ a mod n <math>a-a =k_1\cdot n\ </math> mit geeignetem <math>k_1 \in \Z </math>. |
Für <math>k_1 = 0\ </math> ist die Gleichung erfüllt. | Für <math>k_1 = 0\ </math> ist die Gleichung erfüllt. | ||
<br> | <br> |
Version vom 23. Dezember 2010, 02:08 Uhr
Modulo-Rechnung
Beispiel:
Um die letzten Details des Treffens zu klären, telefonieren Alice und Bob. Es ist 12 Uhr mittags.
![]() ![]() |
![]() |
![]() |
![]() |
Alice sagt: „Wir treffen uns in 48 Stunden bei mir.“ Um wie viel Uhr treffen sich die beiden?
Jeder kann sofort im Kopf die Lösung ausrechnen. Selbst Mallory hat ermitteln können, dass sich die beiden genau zwei Tage darauf zur selben Uhrzeit wieder treffen.
Doch wieso ist es dann nicht 60 Uhr? Dies hängt damit zusammen, dass unsere Stundenzählung nach 24 Stunden wieder bei null beginnt, mathematisch ausgedrückt, gibt es nur die Stunden im Intervall [0,n-1], also bei n = 24 h pro Tag nur im Intervall [0,23]. Doch wie erhalten wir nun das obige Ergebnis? Wir teilen die Zahl 60 einfach so oft durch 24, bis wir einen ganzzahligen Rest erhalten, der in obigem Intervall liegt. Mathematisch bezeichnet man dieses Teilen als Modulo-Rechnung. Doch eigentlich macht man dabei nichts anderes, wie wir beim Berechnen der Uhrzeit ausgeführt haben. Die Modulo-Rechnung ist korrekt mathematisch wie folgt definiert:
Definition 2.0[1]Es seien und
. a heißt kongruent b modulo n (in Zeichen
oder
), wenn es ein
gibt mit
Für unser Beispiel bedeutet dies:
a = 60, b = 12
n = 24
Die Bedingung der Definition ist gleichwertig damit, dass n die Zahl (a-b) teilt.
Es zeigt sich, dass die Kongruenz bezüglich modulo n eine Äquivalenzrelation[2] ist, also gilt:
1.Reflexivität: Jede ganze Zahl a ist zu sich selbst kongruent modulo n (a ≡ a mod n)
Beispiel: 60 ≡ 60 mod 24 ; 60 mod 24 = 60 mod 24
2.Symmetrie: Aus a ≡ b mod n folgt, dass auch b ≡ a mod n
Beispiel: 60 ≡ 12 mod 24 gleich 12 ≡ 60 mod 24
3.Transitivität: Aus a ≡ b mod n und b ≡ c mod n folgt, dass a ≡ c mod n gilt.
Beispiel: 60 ≡ 12 mod 24 , 12 ≡ 36 mod 24 => 60 ≡ 36 mod 24
Die derzeit effizienteste Umsetzung des Euklidischen Algorithmus lässt sich nun ableiten:
Wie in Def. 2.0 beschrieben ist äquivalent zu a ≡ b mod n.
Der Euklidische Algorithmus ( vgl. Algorithmus 1.2 ) besagt:
mit
umgeformt ergibt dies:
folglich lässt sich der Euklidische Algorithmus wie folgt durchführen:
![ggT(a,b)=\ q_{m+1}](/images/math/7/0/1/701c0944f61897413348459fae08290d.png)
Die Komplexität des Euklidischen Algorithmus beträgt O (log (n)), dieser gilt damit als effizient.
Rechnen wir hier nochmals mit den Zahlen 1980 und 1911:
69 = 1980 mod 1911
48 = 1911 mod 69
21 = 69 mod 48
6 = 48 mod 21
3 = 21 mod 6
0 = 6 mod 3
=> ggT(1911, 1980) = 3
Satz 2.1[1]Es seien und
.
Aus
und
folgen die Relationen:
und daraus folgt:
Mit den Zahlen aus dem Beispiel ergibt sich so:
Addition | Multiplikation | Potenzierung |
---|---|---|
![]() ![]() |
![]() ![]() |
![]()
![]() |
Fasst man alle Zahlen die mod n den gleichen Rest ergeben zusammen, so spricht man von einer Äquivalenzklasse:
Definition 2.2[2] Die Äquivalenzklasse von a besteht aus allen ganzen Zahlen, die sich durch Addition ganzzahliger Vielfacher von n ergeben, sie ist also
Man nennt sie Äquivalenzklasse, Kongruenzklasse oder auch Restklasse von a mod n. Dabei heißt a Repräsentant der Klasse [a]. Jedes a' ist ein Repräsentant bzw. Vertreter von [a].
Da wegen Satz 2.1 die Definition unabhängig von den jeweils gewählten Repräsentanten ist, kann man eindeutig eine Addition und Multiplikation zweier Restklassen definieren:
[1]
Im Gegensatz zu Bob, beschäftigt sich Alice bereits vor ihrem Treffen mit den zur Auswahl stehenden Verschlüsselungsalgorithmen und erlernt die nötigen mathematischen Grundlagen.
Sie sendet Bob ein Rätsel:
„Kannst Du mir sagen, was die modulare Inverse von 13 mod 24 ist?“
Bob weiß überhaupt nicht, wovon Alice spricht.
Lese einfach den nächsten Abschnitt, so kannst du Alice die korrekte Antwort geben.
weiter zur Berechnung der modularen Inversen
zurück zur Übersicht