Mathematische Grundlagen 2: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
 
(58 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
<div style="text-align:right;">[[Bild:Buch.PNG]][[Benutzer:Deininger_Matthias/Facharbeit/Fachwortverzeichnis| Fachwortverzeichnis]]</div>
 +
===Modulo-Rechnung ===
 
<u>Beispiel:</u><br>
 
<u>Beispiel:</u><br>
 
<br>
 
<br>
 
Um die letzten Details des Treffens zu klären, telefonieren Alice und Bob. Es ist 12 Uhr mittags.<br>
 
Um die letzten Details des Treffens zu klären, telefonieren Alice und Bob. Es ist 12 Uhr mittags.<br>
−
[[Bild:Deininger Matthias_Abt1.jpg]]
+
<div style="text-align:center;position:relative;top:2px;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[[Bild:Telefonkabel.png]]</div>
 +
<table border="1" cellpadding="0" rules="all" style="text-align:center; color:black;margin:auto;font-size:18px; border:2px solid black;">
 +
  <tr>
 +
    <td><span style="white-space:nowrap;">[[Bild:Sprechblase.png]][[Bild:Alice_grinsend.jpg]]</span></td>
 +
    <td>[[Bild:Mallory_mit_Kappe.jpg]]</td>
 +
    <td>[[Bild:Bob_neutral.jpg]]</td>
 +
<td>[[Bild:Uhr_RSA.png]]<br>
 +
  </tr>
 +
</table>
 
Alice sagt: „Wir treffen uns in 48 Stunden bei mir.“  Um wie viel Uhr treffen sich die beiden?<br>
 
Alice sagt: „Wir treffen uns in 48 Stunden bei mir.“  Um wie viel Uhr treffen sich die beiden?<br>
 
<br>
 
<br>
−
Jeder kann mir 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.<br>  
+
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.<br>  
−
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,23], also bei n= 24 h pro Tag nur im Intervall [0,n-1]. 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:<br>
+
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:<br>
 
<br>
 
<br>
−
'''Definition 2.0''' Es seien <math>a,b \in \Z</math> und <math>n\in\N</math>. a heißt kongruent b modulo n (in Zeichen <math>a\equiv_n b</math> oder a mod n = b mod n), wenn es ein <math> k \in\Z</math> gibt mit<br>
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''Definition 2.0'''<ref name="w14">[12, S.35 f.]</ref>Es seien <math>a,b \in \Z</math> und <math>n\in\N</math>. a heißt kongruent b modulo n (in Zeichen <math>a\equiv_n b</math> oder <math>a\equiv b\ mod\ n </math>), wenn es ein <math> k \in\Z</math> gibt mit<br>
 
<br>
 
<br>
 
<math> a-b =k\cdot n </math><br>
 
<math> a-b =k\cdot n </math><br>
−
<br>
+
</div><br>
 
Für unser Beispiel bedeutet dies:<br>
 
Für unser Beispiel bedeutet dies:<br>
−
a = 60, b =12<br>
+
a = 60, b = 12<br>
 
n = 24<br>
 
n = 24<br>
 
<math>60-12 = k\cdot 24 \Rightarrow k = 2</math><br>
 
<math>60-12 = k\cdot 24 \Rightarrow k = 2</math><br>
Zeile 20: Zeile 31:
 
Die Bedingung der Definition ist gleichwertig damit, dass n die Zahl (a-b) teilt.<br>
 
Die Bedingung der Definition ist gleichwertig damit, dass n die Zahl (a-b) teilt.<br>
 
<br>
 
<br>
−
Es zeigt sich, dass modulo n eine Äquivalenzrelation ist, also gilt:<br>
+
Es zeigt sich, dass die Kongruenz bezüglich modulo n eine Äquivalenzrelation<ref name="b4">vgl. [3, S.24]</ref> ist, also gilt:<br>
 
<br>
 
<br>
−
1.''Reflexivität:'' jede ganze Zahl a ist zu sich selbst kongruent modulo n (a ≡ a[mod n]) <br>
+
<div style = "border: 2px solid red; padding:0.75em;">
−
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 60 (mod 24) ; 60 mod 24 = 60 mod 24 <br>
+
1.''Reflexivität:'' Jede ganze Zahl a ist zu sich selbst kongruent modulo n (a ≡ a mod n) <br>
−
2.''Symmetrie:'' aus a ≡ b (mod n) folgt, dass auch b ≡ a (mod n) <br>
+
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 60 mod 24 ; 60 mod 24 = 60 mod 24 <br>
−
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 12 (mod 24) gleich 12 ≡ 60 (mod 24)<br>
+
2.''Symmetrie:'' Aus a ≡ b mod n folgt, dass auch b ≡ a mod n <br>
−
3.''Transitivität:'' aus a ≡ b (mod n) und b ≡ c (mod n) folgt, dass a ≡ c (mod n) gilt.<br>
+
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 12 mod 24 gleich 12 ≡ 60 mod 24<br>
−
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 12 (mod 24) , 12 ≡ 36 (mod 24) => 60 ≡ 36 (mod 24)<br>
+
3.''Transitivität:'' Aus a ≡ b mod n und b ≡ c mod n folgt, dass a ≡ c mod n gilt.<br>
−
<br>
+
&nbsp;&nbsp;&nbsp;Beispiel: 60 ≡ 12 mod 24 , 12 ≡ 36 mod 24 => 60 ≡ 36 mod 24<br>
−
Um den Beweis zu den Äquivalenzrelationen verstehen zu können, solltest du zunächst Definition 2.2 betrachten.<br>
+
</div><br>
 
<popup name="Beweis">
 
<popup name="Beweis">
 
<br>
 
<br>
 +
1.''Reflexivität:''
 +
<br>
 +
<br>
 +
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.
 +
<br>
 +
<br>
 +
2.''Symmetrie:''
 +
<br>
 +
<br>
 +
Nach Definition 2.0 gilt für a ≡ b mod n    <math>\ a-b =k_1\cdot n</math> und für b ≡ a mod n    <math>\ b-a =k_2\cdot n </math> mit geeignetem <math>k_1,k_2 \in \Z </math>.
 +
Damit ergeben sich folgende Gleichungen:
 +
<math>(a-b)\cdot k_2\ =\ (b-a)\cdot k_1</math> somit ist die Gleichung für <math>k_1 = -k_2\ </math> erfüllt und damit die Symmetrie bewiesen.
 +
<br>
 +
<br>
 +
3.''Transitivität:''<br>
 +
<br>
 +
Auch hier gilt für für a ≡ b mod n    <math>\ a-b =k_1\cdot n</math> und für b ≡ c mod n  <math>\ b-c =k_2\cdot n </math> mit geeignetem <math>k_1,k_2 \in \Z </math>.<br>
 +
Zu zeigen ist nun, dass sich auf für a ≡ c mod n eine solche Gleichung der Schreibweise <math>a-c =k_3\cdot n</math> ermitteln lässt.<br>
 +
Dazu formt man die beiden Ausgangsgleichungen derart um, dass sich Folgendes ergibt:<br>
 +
<br>
 +
<math>I.\ a-b =k_1\cdot n</math><br>
 +
<math>II.\ b =k_2\cdot n+c</math><br>
 +
<br>
 +
anschließend setzt man Gleichung II. in Gleichung I. ein und erhält:<br>
 +
<br>
 +
<math>a-(k_2\cdot n+c) =k_1\cdot n</math><br>
 +
<math>a-k_2\cdot n-c =k_1\cdot n</math><br>
 +
<math>a-c =k_1\cdot n+k_2\cdot n </math><br>
 +
<math>a-c =(k_1+k_2)\cdot n </math><br> wobei gilt:
 +
<math>k_1+k_2=\ k_3</math>
 +
somit lässt sich folgern:
 +
<math>a-c =k_3\cdot n </math>□<br>
 
</popup>
 
</popup>
 
<br>
 
<br>
 
<br>
 
<br>
 
Die derzeit effizienteste Umsetzung des Euklidischen Algorithmus lässt sich nun ableiten:
 
Die derzeit effizienteste Umsetzung des Euklidischen Algorithmus lässt sich nun ableiten:
−
Wie in Def. 2.0 beschrieben ist <math>a-b =k\cdot n</math> äquivalent zu  a ≡ b (mod n).
+
Wie in Definition 2.0 beschrieben ist <math>a-b =k\cdot n</math> äquivalent zu  a ≡ b mod n.
−
Der Euklidische Algorithmus (vgl. Algorithmus 1.1) besagt: <math>a= b\cdot q +r</math> mit <math>0 \le r <b</math> umgeformt ergibt dies:<br>
+
Der Euklidische Algorithmus ([[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen#Euklidischer_Algorithmus| vgl. Algorithmus 1.2 ]]) besagt: <math>a= b\cdot q +r</math> mit <math>0 \le r <b</math> umgeformt ergibt dies:<br>
 
<math>a-r = b\cdot q </math><br>
 
<math>a-r = b\cdot q </math><br>
 
folglich lässt sich der Euklidische Algorithmus wie folgt durchführen:<br>
 
folglich lässt sich der Euklidische Algorithmus wie folgt durchführen:<br>
 
<br>
 
<br>
 +
<div style = "border: 2px solid red; padding:0.75em; width:400px">
 
<math>q_1=  b\  mod\ a  </math><br>
 
<math>q_1=  b\  mod\ a  </math><br>
 
<math>q_2=  a\  mod\ q_1</math><br>
 
<math>q_2=  a\  mod\ q_1</math><br>
Zeile 48: Zeile 93:
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad \cdot</math><br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad \cdot</math><br>
 
<math>q_{m+1} = q_{m-1}\ mod\ q_{m}</math><br>
 
<math>q_{m+1} = q_{m-1}\ mod\ q_{m}</math><br>
−
<math>0 =  q_m\ mod\ q_{m+1} </math> <br>
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad \quad 0 =  q_m\ mod\ q_{m+1} </math> <br>
−
<math>ggT(a,b)=\ q_{m+1}</math><br>
+
<math>ggT(a,b)=\ q_{m+1}</math><br></div>
 
<br>
 
<br>
 
Die [[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen| Komplexität ]] des Euklidischen Algorithmus beträgt O (log (n)), dieser gilt damit als effizient.<br>
 
Die [[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen| Komplexität ]] des Euklidischen Algorithmus beträgt O (log (n)), dieser gilt damit als effizient.<br>
Zeile 63: Zeile 108:
 
=> ggT(1911, 1980) = 3<br>
 
=> ggT(1911, 1980) = 3<br>
 
<br>
 
<br>
−
'''Satz 2.1''' Es seien <math>n \in \N</math> und <math>a,a',b,b' \in \Z</math>.  
+
<div style = "border: 2px solid red; padding:0.75em;">
−
Aus <math>a \equiv_n a'</math> und <math>b\equiv_n b'</math> folgen die Relationen:<br>
+
'''Satz 2.1'''<ref name="w14"/>Es seien <math>n \in \N</math> und <math>a,a',b,b' \in \Z</math>.  
 +
Aus <math>a \equiv a'\ mod\ n</math> und <math>b\equiv b'\ mod\ n</math> folgen die Relationen:<br>
 
<br>
 
<br>
 
<math>(a+b)\ mod\ n = (a'+b')\ mod\ n\ und\ (ab)\ mod\ n = (a'b')\ mod\ n</math><br>
 
<math>(a+b)\ mod\ n = (a'+b')\ mod\ n\ und\ (ab)\ mod\ n = (a'b')\ mod\ n</math><br>
Zeile 72: Zeile 118:
 
<br>
 
<br>
 
<math>a^x\ mod\ n = (a')^x\ mod\ n</math><br>
 
<math>a^x\ mod\ n = (a')^x\ mod\ n</math><br>
−
<br>
+
</div><br>
−
''Beweis:'' Nach Def. 2.0 gilt <math>a-a' =k_1\cdot n</math> und <math>b-b' =k_2\cdot n </math>mit geeignetem <math>k_1,k_2 \in \Z </math>.
+
<popup name="Beweis">
 +
<u>Beweis:</u> Nach Definition 2.0 gilt <math>a-a' =k_1\cdot n</math> und <math>b-b' =k_2\cdot n </math>mit geeignetem <math>k_1,k_2 \in \Z </math>.
 
Damit ergeben sich folgende Gleichungen:<br>
 
Damit ergeben sich folgende Gleichungen:<br>
 
<br>
 
<br>
 
<math>(a+b)-(a'+b')=(a-a')+(b-b') =(k_1+k_2)\cdot n </math><br>
 
<math>(a+b)-(a'+b')=(a-a')+(b-b') =(k_1+k_2)\cdot n </math><br>
 
<br>
 
<br>
−
Wiederholtes Addieren ergibt eine Multiplikation, also gilt der Beweises auch für die Multiplikation. Wiederholtes Multiplizieren ist eine Potenzrechnung, also gilt entsprechender Satz auch hier. □<br>
+
Wiederholtes Addieren ergibt eine Multiplikation, also gilt der Beweis auch für die Multiplikation. Wiederholtes Multiplizieren ist eine Potenzrechnung, also gilt entsprechender Satz auch hier. □<br>
 +
</popup>
 
<br>
 
<br>
 
Mit den Zahlen aus dem Beispiel ergibt sich so:<br>  
 
Mit den Zahlen aus dem Beispiel ergibt sich so:<br>  
Zeile 103: Zeile 151:
 
Fasst man alle Zahlen die mod n den gleichen Rest ergeben zusammen, so spricht man von einer Äquivalenzklasse:<br>
 
Fasst man alle Zahlen die mod n den gleichen Rest ergeben zusammen, so spricht man von einer Äquivalenzklasse:<br>
 
<br>
 
<br>
−
'''Definition 2.2''' Die Äquivalenzklasse von a besteht aus allen ganzen Zahlen, die sich durch Addition ganzzahliger Vielfacher von n ergeben, sie ist also<br>
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''Definition 2.2'''<ref name="b4"/> Die Äquivalenzklasse von a besteht aus allen ganzen Zahlen, die sich durch Addition ganzzahliger Vielfacher von n ergeben, sie ist also<br>
 
<br>
 
<br>
 
<div style ="marign:auto;">
 
<div style ="marign:auto;">
−
<math>[a] = \{b:b \equiv a\ (mod\ n)\} = a + n\cdot \Z</math>  oder<br> 
+
<math>[a] := \{a' \in\Z| a'\equiv a\ mod\ n\}</math>
−
<math>[a] = \{a' \in\Z| a'\equiv a\ (mod\ n)\}</math>
+
 
<br>
 
<br>
 +
</div>
 +
</div>
 
<br>
 
<br>
−
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].Analoges gilt für [b].<br>
+
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].<br>
−
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:
+
−
 
+
−
<math>[a]\oplus  [b] = [a+b] und [a] \otimes  [b] = [a\cdot b]</math><br>
+
 
<br>
 
<br>
−
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.<br>
+
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:<br>
 +
<br>
 +
<math>[a]\oplus  [b] = [a+b]\ und\ [a] \otimes  [b] = [a\cdot b]</math><ref name="w14"/> <br>
 +
<br>
 +
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.<br>
 
Sie sendet Bob ein Rätsel:<br>
 
Sie sendet Bob ein Rätsel:<br>
−
'''''„Kannst Du mir sagen, was die modulare Inverse von 13 mod 24 ist?“<br>'''''
+
'''''„Kannst Du mir sagen, was die modulare Inverse zu 13 mod 24 ist?“<br>'''''
−
Bob weiß überhaupt nicht wovon Alice spricht.<br>
+
Bob weiß überhaupt nicht, wovon Alice spricht.<br>
 
Lese einfach den nächsten Abschnitt, so kannst du Alice die korrekte Antwort geben.<br>
 
Lese einfach den nächsten Abschnitt, so kannst du Alice die korrekte Antwort geben.<br>
 
<br>
 
<br>
−
[[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen_3| ''' => weiter zur Berechnung der modularen Inversen''']]
+
[[Bild:Weiter.png|weiter]] [[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen_3| ''' weiter zur Berechnung der modularen Inversen''']]
 +
<br>
 +
<br>
 +
[[Benutzer:Deininger_Matthias/Facharbeit| zurück zur Übersicht]]
 +
----
 +
 
 +
<references />
 +
[[Benutzer:Deininger_Matthias/Facharbeit/Literaturverzeichnis| siehe dazu Literaturverzeichnis]]

Aktuelle Version vom 23. Dezember 2010, 01:51 Uhr

Buch.PNG Fachwortverzeichnis

Modulo-Rechnung

Beispiel:

Um die letzten Details des Treffens zu klären, telefonieren Alice und Bob. Es ist 12 Uhr mittags.

                        Telefonkabel.png
Sprechblase.pngAlice grinsend.jpg Mallory mit Kappe.jpg Bob neutral.jpg Uhr RSA.png

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 a,b \in \Z und n\in\N. a heißt kongruent b modulo n (in Zeichen a\equiv_n b oder a\equiv b\ mod\ n ), wenn es ein k \in\Z gibt mit

a-b =k\cdot n


Für unser Beispiel bedeutet dies:
a = 60, b = 12
n = 24
60-12 = k\cdot 24 \Rightarrow k = 2
60\ mod\ 24 = 12 = 12\ mod\ 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 Definition 2.0 beschrieben ist a-b =k\cdot n äquivalent zu a ≡ b mod n. Der Euklidische Algorithmus ( vgl. Algorithmus 1.2 ) besagt: a= b\cdot q +r mit 0 \le r <b umgeformt ergibt dies:
a-r = b\cdot q
folglich lässt sich der Euklidische Algorithmus wie folgt durchführen:

q_1= b\ mod\ a
q_2= a\ mod\ q_1
q_3= q_1\ mod\ q_2
               \quad \cdot
               \quad \cdot
               \quad \cdot
q_{m+1} = q_{m-1}\ mod\ q_{m}
        \quad \quad 0 = q_m\ mod\ q_{m+1}

ggT(a,b)=\ q_{m+1}


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 n \in \N und a,a',b,b' \in \Z. Aus a \equiv a'\ mod\ n und b\equiv b'\ mod\ n folgen die Relationen:

(a+b)\ mod\ n = (a'+b')\ mod\ n\ und\ (ab)\ mod\ n = (a'b')\ mod\ n
               \quad(a+b) \equiv_n (a'+b')\quad\quad\quad und\quad\quad\quad\ (ab) \equiv_n (a'b')

und daraus folgt:

a^x\ mod\ n = (a')^x\ mod\ n



Mit den Zahlen aus dem Beispiel ergibt sich so:
60-12 = 2\cdot 24
30-6 =1\cdot 24

Addition Multiplikation Potenzierung
(60+30)\ mod\ 24 = (12+6)\ mod\ 24
18 = 18 		(60\cdot 30)\ mod\ 24 = (12\cdot 6)\ mod\ 24
0 = 0		 (60^2)\ mod\ 24 = (12^2)\ mod\ 24

3600\ mod\ 24= 144\ mod\ 24

0 = 0


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

[a] := \{a' \in\Z| a'\equiv a\ mod\ n\}


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:

[a]\oplus [b] = [a+b]\ und\ [a] \otimes [b] = [a\cdot b][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 zu 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 weiter zur Berechnung der modularen Inversen

zurück zur Übersicht

  1. ↑ 1,0 1,1 1,2 [12, S.35 f.]
  2. ↑ 2,0 2,1 vgl. [3, S.24]

siehe dazu Literaturverzeichnis

Von „http://rmg.zum.de/index.php?title=Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen_2&oldid=39668“