Mathematische Grundlagen2: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
Zeile 49: Zeile 49:
 
<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>
 
<math>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>
 
<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 63:
 
=> 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>.
 +
Aus <math>a \equiv_n  a'</math> und <math>b\equiv_n b'</math> folgen die Relationen:<br>
 +
<br>
 +
<math>(a+b)\ mod\ n = (a'+b')\ mod\ n\ und\ (ab)\ mod\ n = (a'b')\ mod\ n</math><br>
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad(a+b) \equiv_n (a'+b')\quad\quad\quad und\quad\quad\quad\ (ab) \equiv_n (a'b')</math><br>
 +
<br>
 +
und daraus folgt:<br>
 +
<br>
 +
<math>a^x\ mod\ n = (a')^x\ mod\ n</math><br>
 +
<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>.
 +
Damit ergeben sich folgende Gleichungen:<br>
 +
<br>
 +
<math>(a+b)-(a'+b')=(a-a')+(b-b') =(k_1+k_2)\cdot n </math><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>

Version vom 2. September 2010, 22:18 Uhr

Beispiel:

Um die letzten Details des Treffens zu klären, telefonieren Alice und Bob. Es ist 12 Uhr mittags.
Deininger Matthias Abt1.jpg Alice sagt: „Wir treffen uns in 48 Stunden bei mir.“ Um wie viel Uhr treffen sich die beiden?

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.
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:

Definition 2.0 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 mod n = 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 (in Zeichen: n|(a-b))

Es zeigt sich, dass modulo n eine Äquivalenzrelation 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)

Um den Beweis zu den Äquivalenzrelationen verstehen zu können, solltest du zunächst Definition 2.2 betrachten.



Die derzeit effizienteste Umsetzung des Euklidischen Algorithmus lässt sich nun ableiten: Wie in Def. 2.0 beschrieben ist a-b =k\cdot n äquivalent zu a ≡ b (mod n). Der Euklidische Algorithmus (vgl. Algorithmus 1.1) 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}
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 Es seien n \in \N und a,a',b,b' \in \Z. Aus a \equiv_n a' und b\equiv_n b' 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

Beweis: Nach Def. 2.0 gilt a-a' =k_1\cdot n und b-b' =k_2\cdot n mit geeignetem k_1,k_2 \in \Z . Damit ergeben sich folgende Gleichungen:

(a+b)-(a'+b')=(a-a')+(b-b') =(k_1+k_2)\cdot n

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. □

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