Mathematische Grundlagen: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
 
(71 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>
 +
===Mathematische Grundlagen===
 +
====Berechnungskomplexität====
 +
In der Kryptographie ist häufig die Rede von effizienten oder uneffizienten Verfahren; Alice hat dazu Folgendes gelesen:<br>
 +
<br>
 +
Die Entscheidung, ob ein Verfahren als effizient gilt oder nicht, beruht lediglich auf der Berechnungskomplexität des Verfahrens und nicht auf den verwendeten Computersystemen.<br>
 +
Die Berechnungskomplexität bezeichnet dabei den Speicherbedarf S und Zeitbedarf T der untersuchten Funktion, was als Laufzeitfunktion bezeichnet wird. Dies kann man mittels der sogenannten „Big-O-Notation“ oder „Groß-O-Schreibweise“ angeben.<br>
 +
<br>
 +
Die „Big-O-Notation“ beruht darauf, dass die Laufzeit einer Funktion hauptsächlich von der größten Potenz abhängig ist und alle anderen Faktoren als trivial gelten können. Folglich wird nur diese größte Potenz der Funktion in der „Big-O-Notation“ berücksichtigt.<br>
 +
Die Laufzeit einer Funktion hängt von der Bitlänge n des verwendeten Schlüssels ab, weshalb diese Größe als Variable n in die „Big-O-Notation“ mit eingeht.<br>
 +
<br>
 +
Beispiel: Die Laufzeitkomplexität einer Funktion lautet: <math>5n^2+3n+1</math>, also würde diese Funktion als „Big-O-Notation“, so angegeben werden: <math>O(n^2)</math><br>
 +
<br>
 +
Um nun zu bestimmen, ob eine Funktion als effizient gilt, unterscheidet man unter anderem:<br>
 +
<table border="1" cellpadding="5" rules="all" style="text-align:center; color:black;margin:auto;font-size:12px; border:2px solid black;">
 +
 +
  <tr>
 +
    <th colspan="2" width="50%" style="border-right-style:solid;">effizient</th>
 +
    <th colspan="2" width="50%">uneffizient </th>
 +
  </tr>
 +
  <tr>
 +
    <td>Konstant</td>
 +
    <td style="border-right-style:solid;"> <math>O(1)\ </math></td>
 +
<td>Polynomial</td>
 +
<td><math>O(n^m),\ m > 6, m = konst.</math></td>
 +
  </tr>
 +
<tr>
 +
    <td>Linear </td>
 +
<td style="border-right-style:solid;"><math>O(n)\ </math> </td>
 +
    <td>Exponentiell </td>
 +
<td><math>O(t^{f(n)}),\ wobei\ t > 1 , t = konst. , f(n) = n^m + ... + a\cdot n+ c, m = konst.</math> </td>
 +
  </tr>
 +
<tr>
 +
    <td> Polynomial</td>
 +
<td style="border-right-style:solid;"><math>O(n^m),\ m\le 6, m = konst.</math></td>
 +
    <td></td>
 +
<td></td>
 +
</tr>
 +
</table><br>
 +
<br>
 +
Was dies für die reale Berechnungszeit bedeutet, zeigt die Tabelle:<br>
 +
<table border="1" cellpadding="5" rules="all" style="text-align:center; color:black;margin:auto;font-size:12px; border:2px solid black;">
 +
 +
<tr>
 +
<th >Klasse</th>
 +
<th style="border-right-width:2px; border-right-style:solid;">Komplexität </th>
 +
<th >Anzahl der Operationen für n = <math>10^9</math></th>
 +
<th style="border-right-width:2px; border-right-style:solid;">Laufzeit*</th>
 +
<th >Anzahl der Operationen für n = <math>10^{10}</math></th>
 +
<th>Laufzeit*</th>
 +
</tr>
 +
<tr>
 +
<td>Konstant</td>
 +
<td style="border-right-width:2px; border-right-style:solid;"> <math>O(1)\ </math></td>
 +
<td>1</td>
 +
<td style="border-right-width:2px; border-right-style:solid;">1 Nanosekunde</td>
 +
<td>1</td>
 +
<td>1 Nanosekunde</td>
 +
</tr>
 +
<tr>
 +
<td>Linear </td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>O(n)\ </math> </td>
 +
<td><math>10^9</math></td>
 +
<td style="border-right-width:2px; border-right-style:solid;">1 Sekunde</td>
 +
<td><math>10^{10}</math></td>
 +
<td>10 Sekunden</td>
 +
</tr>
 +
<tr>
 +
<td> Quadratisch</td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>O(n^2)\ </math></td>
 +
<td><math>10^{18}</math></td>
 +
<td style="border-right-width:2px; border-right-style:solid;"> 32 Jahre</td>
 +
<td><math>10^{20}</math></td>
 +
<td>3171 Jahre</td>
 +
</tr>
 +
<tr>
 +
<td> Kubisch</td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>O(n^3)\ </math></td>
 +
<td><math>10^{27}</math></td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>3 \cdot 10^{10}</math> Jahre <br>(entspricht ungefähr dem Alter des Universums<ref name="t8">Die physikalischen Daten stammen aus [8, S.21].</ref>)</td>
 +
<td><math>10^{30}</math></td>
 +
<td><math>3 \cdot 10^{13}</math> Jahre <br> (entspricht ungefähr dem 1000-fachen <br>des Alters des Universums<ref name="t8"/>)</td>
 +
</tr>
 +
<tr>
 +
<td> Exponentiell</td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>O(2^n)\ </math></td>
 +
<td><math>10^{301030000}</math></td>
 +
<td style="border-right-width:2px; border-right-style:solid;"><math>10^{301029973}</math>-fache <br>des Alters des Universums<ref name="t8"/></td>
 +
<td><math>10^{3010300000}</math></td>
 +
<td><math>10^{3010299973}</math>-fache <br> des Alters des Universums<ref name="t8"/></td>
 +
</tr>
 +
</table>
 +
<div style="text-align:center;"><math>*</math>Laufzeitangaben wurden unter der Annahme das der Computer <math>10^9</math> Operationen pro Sekunde ausführen kann gerundet.</div><br>
 +
 +
<br>
 
Aber nun zu den mathematischen Grundlagen, die für RSA relevant sind.<br>
 
Aber nun zu den mathematischen Grundlagen, die für RSA relevant sind.<br>
 
<br>
 
<br>
 +
====Größter gemeinsamer Teiler====
 +
<div style = "background-color: #BEFF9E; border: 2px solid #E5CC00;border-color: green;">
 
<u>Aufgabe:</u><br>
 
<u>Aufgabe:</u><br>
 
<br>
 
<br>
Zeile 7: Zeile 104:
 
Und es funktioniert tatsächlich, Mallory, der Mathe immer gehasst hat, erkennt nicht, welche Punktzahl Alice erreicht hat.<br>  
 
Und es funktioniert tatsächlich, Mallory, der Mathe immer gehasst hat, erkennt nicht, welche Punktzahl Alice erreicht hat.<br>  
 
<br>
 
<br>
−
Kannst du die Punktzahl von Alice ermitteln?<br>
+
Kannst du die Punktzahl von Alice ermitteln?</div><br>
  
 
<popup name="Lösung">
 
<popup name="Lösung">
Zeile 14: Zeile 111:
 
<math>Primfaktorzerlegung\ von\ 105\ =\ \quad\quad3\cdot5\cdot7 </math><br>
 
<math>Primfaktorzerlegung\ von\ 105\ =\ \quad\quad3\cdot5\cdot7 </math><br>
 
<math>folglich\ ist\ der\ ggT\ (90,105)\ =\ 15\ =3\cdot 5 </math><br><br>
 
<math>folglich\ ist\ der\ ggT\ (90,105)\ =\ 15\ =3\cdot 5 </math><br><br>
−
<math>Alice\ hat\ also\ 15\ Punkte\ in\ ihrer\ letzen\ Matheklausur\ geschrieben.</math>  
+
<math>Alice\ hat\ also\ 15\ Punkte\ in\ ihrer\ letzten\ Matheklausur\ geschrieben.</math>  
 
</popup>
 
</popup>
 
<br>
 
<br>
−
Den größten gemeinsamen Teiler (ggT) von natürlichen Zahlen hast du bereits in der 5.Klasse berechnet. Dazu hast du, wie in obigem Beispiel, Zahlen in ihre Primfaktoren zerlegt und daraus anschließend den ggT ermittelt. Das es zu jeder natürlichen Zahl n eine eindeutige Primfaktorzerlegung gibt, zeigt folgender Satz:
+
Den größten gemeinsamen Teiler (ggT) von natürlichen Zahlen hast du bereits in der 5.Klasse berechnet. Dazu hast du, wie in obigem Beispiel, Zahlen in ihre Primfaktoren zerlegt und daraus anschließend den ggT ermittelt. Dass es zu jeder natürlichen Zahl n eine eindeutige Primfaktorzerlegung gibt, zeigt folgender Satz:<br>
−
 
+
<div style = "border: 2px solid red; padding:0.75em;">
−
'''Satz 1.0''' (Fundamentalsatz der elementaren Zahlentheorie oder Satz über die eindeutige Primfaktorzerlegung)<br>
+
'''Satz 1.0'''<ref>Satz 1.0 und dessen Beweis stammen aus [7, S.62f.].</ref>(Fundamentalsatz der elementaren Zahlentheorie oder Satz über die eindeutige Primfaktorzerlegung)<br>
−
Jede natürliche Zahl n > 1 lässt sich auf eindeutige Weise in ein Produkt von Primfaktoren zerlegen.<br><br>
+
Jede natürliche Zahl n > 1 lässt sich auf eindeutige Weise in ein Produkt von Primfaktoren zerlegen.<br></div><br>
  
 
<popup name="Beweis">
 
<popup name="Beweis">
−
Beweis: Es wird zunächst gezeigt, dass sich jede natürliche Zahl n > 1 als Produkt von Primfaktoren schreiben lässt. Falls n prim ist, ist die Zerlegung gezeigt. Andernfalls besitzt sie einen Teiler d > 1 und es ist <math>d\cdot\frac{n}{d}</math> eine Zerlegung von n in echt kleiner positive ganze Zahlen d und <math>\frac{n}{d}</math>. Falls beide prim sind, so ist die Zerlegung beendet. Im anderen Fall lassen sich sich diese wieder zerlegen und so weiter. Da bei diesem Prozess die Faktoren immer kleiner werden, aber positiv bleiben, muss dieser Prozess irgendwann abbrechen und wir besitzen eine Zerlegung in Primfaktoren.<br>
+
Beweis: Es wird zunächst gezeigt, dass sich jede natürliche Zahl n > 1 als Produkt von Primfaktoren schreiben lässt. Falls n prim ist, ist die Zerlegung gezeigt. Andernfalls besitzt sie einen Teiler d > 1 und es ist <math>d\cdot\frac{n}{d}</math> eine Zerlegung von n in echt kleinere positive ganze Zahlen d und <math>\frac{n}{d}</math>. Falls beide prim sind, so ist die Zerlegung beendet. Im anderen Fall lassen sich diese wieder zerlegen und so weiter. Da bei diesem Prozess die Faktoren immer kleiner werden, aber positiv bleiben, muss dieser Prozess irgendwann abbrechen und wir besitzen eine Zerlegung in Primfaktoren.<br>
 
Zur Eindeutigkeit: Angenommen, man hat zu einer Zahl n zwei Zerlegungen  
 
Zur Eindeutigkeit: Angenommen, man hat zu einer Zahl n zwei Zerlegungen  
 
<math>p_1\cdot p_2\cdot...\cdot p_l=q_1\cdot q_2\cdot...\cdot q_k</math> in Primfaktoren <math>p_r,\ q_r</math>, so das gilt <math>l,k,r\in \N</math>.(Hierbei können Zahlen natürlich auch mehrfach vorkommen.) Man stelle sich vor, man hätte bereits alle gleichen Elemente auf beiden Seiten herausgekürzt. Dann sind alle <math>p_r</math> von allen <math>q_r</math> verschieden. Dies steht aber im Widerspruch dazu, dass dies alles Primelemente sind. Da nämlich z.B. <math>p_1</math>, die rechte Seite teilt, so muss <math>p_1</math>, da es eine Primzahl ist, eine der Zahlen <math> q_r </math> teilen. Da diese aber selbst Primzahlen sind, würde <math>p_1</math> mit dieser übereinstimmen. Widerspruch.[[Benutzer:Deininger_Matthias/Facharbeit/Quod_erat_demonstrandum| □ ]]  
 
<math>p_1\cdot p_2\cdot...\cdot p_l=q_1\cdot q_2\cdot...\cdot q_k</math> in Primfaktoren <math>p_r,\ q_r</math>, so das gilt <math>l,k,r\in \N</math>.(Hierbei können Zahlen natürlich auch mehrfach vorkommen.) Man stelle sich vor, man hätte bereits alle gleichen Elemente auf beiden Seiten herausgekürzt. Dann sind alle <math>p_r</math> von allen <math>q_r</math> verschieden. Dies steht aber im Widerspruch dazu, dass dies alles Primelemente sind. Da nämlich z.B. <math>p_1</math>, die rechte Seite teilt, so muss <math>p_1</math>, da es eine Primzahl ist, eine der Zahlen <math> q_r </math> teilen. Da diese aber selbst Primzahlen sind, würde <math>p_1</math> mit dieser übereinstimmen. Widerspruch.[[Benutzer:Deininger_Matthias/Facharbeit/Quod_erat_demonstrandum| □ ]]  
 
</popup>
 
</popup>
 
<br>
 
<br>
−
Der größte gemeinsame Teiler ist allgemein wie folgt definiert:<br>
+
Der größte gemeinsame Teiler ist allgemein, wie folgt, definiert:<br>
 
<br>
 
<br>
−
'''Definition 1.1''' Es seien <math>a,b \in \Z</math>. Die größte natürliche Zahl, die sowohl a als auch b teilt, heißt größter gemeinsamer Teiler und wird mit ggT(a,b) bezeichnet.<br>
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''Definition 1.1'''<ref name="K3">[1, S.120]</ref> Es seien <math>a,b \in \Z</math>. Die größte natürliche Zahl, die sowohl a als auch b teilt, heißt größter gemeinsamer Teiler und wird mit ggT(a,b) bezeichnet.<br>
 +
</div>
 
<br>
 
<br>
−
Es gibt eine effizientere Methode, als die Primfaktorzerlegung, um den ggT zweier natürlicher Zahlen zu bestimmen und damit die Punktzahl von Alice zu ermitteln. Diese Methode wird als Euklidischer Algorithmus bezeichnet, weil er ca. 300 v. Chr. von Euklid in seinem Buch „Elemente“ beschrieben wurde. Historiker vermuten jedoch, dass Euklid den Algorithmus nicht selbst entdeckt hat und schätzen die Entstehungszeit auf ca. 500 v. Chr.<br>
+
====Euklidischer Algorithmus====
 +
Es gibt eine effizientere Methode als die Primfaktorzerlegung, um den ggT zweier natürlicher Zahlen zu bestimmen und damit die Punktzahl von Alice zu ermitteln. Diese Methode wird als ''Euklidischer Algorithmus'' bezeichnet, weil er ca. 300 v. Chr. von Euklid in seinem Buch „Elemente“ beschrieben wurde. Historiker vermuten jedoch, dass Euklid den Algorithmus nicht selbst entdeckt hat, und schätzen die Entstehungszeit auf ca. 500 v. Chr.<br>
 
Der Algorithmus beruht auf Division mit Rest.<br>
 
Der Algorithmus beruht auf Division mit Rest.<br>
 
<br>
 
<br>
−
'''Algorithmus 1.2''' (Euklidischer Algorithmus) Es seien <math>a,b \in \N</math>. Man bestimmt <math>q,r \in \N_0</math>, so dass gilt:
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''Algorithmus 1.2'''<ref>[2, S.106]</ref> (Euklidischer Algorithmus) Es seien <math>a,b \in \Z</math>. Man bestimmt <math>r \in \N_0,\  p \in \Z</math>, so dass gilt:
  
 
<div style = "marign: auto;"><math>a\ =\ b\cdot p + r\ und\ 0\le r < b</math></div>
 
<div style = "marign: auto;"><math>a\ =\ b\cdot p + r\ und\ 0\le r < b</math></div>
  
−
Dann gilt ggT(a,b) =ggT(b,r).<br>
+
Dann gilt ggT(a,b) = ggT(b,r).<br>
 
Anschließend wendet man das Verfahren auf b und r an. Dies führt man so lange fort, bis man den ggT direkt bestimmen kann.<br>
 
Anschließend wendet man das Verfahren auf b und r an. Dies führt man so lange fort, bis man den ggT direkt bestimmen kann.<br>
 +
</div>
 
<br>
 
<br>
 
Für die Zahlen von Alice würde dies bedeuten:<br>
 
Für die Zahlen von Alice würde dies bedeuten:<br>
Zeile 50: Zeile 152:
 
In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:<br>
 
In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:<br>
 
<br>
 
<br>
−
'''Algorithmus 1.3''' Es seien <math>a,b \in \N</math>, ohne Beschränkung der Allgemeinheit* (oBdA.) sei <math>a\ge b</math> (*da Analoges auch für <math>b\ge a</math> gilt). Dann existieren eindeutig bestimmte Zahlen <math>r_1 > r_2 > r_3 > ... > r_m > r_{m+1} =0\ </math> und <math>q_1,q_2,q_3,...,q_m \in \N_0 </math> mit <br>
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''Algorithmus 1.3''' <ref name="K3"/>Es seien <math>a,b \in \Z</math>, oBdA.* (ohne Beschränkung der Allgemeinheit) sei <math>a\ge b\ge0</math> (*da Analoges auch für <math>b\ge a</math> gilt und da gilt: ggt(a,b) = ggt(a,-b)). Dann existieren eindeutig bestimmte Zahlen <math>r_1 > r_2 > r_3 > ... > r_m > r_{m+1} =0\ </math> und <math>q_1,q_2,q_3,...,q_m \in \N_0 </math> mit <br>
 
<br>
 
<br>
 
<math>a = q_1\cdot b+r_1  \quad\ \quad\ 0 < r_1< b</math><br>
 
<math>a = q_1\cdot b+r_1  \quad\ \quad\ 0 < r_1< b</math><br>
Zeile 60: Zeile 163:
 
<math>r_{m-2}= q_{m-1}\cdot r_{m-1} + r_m  \quad  0 < r_m < r_{m-1}</math><br>
 
<math>r_{m-2}= q_{m-1}\cdot r_{m-1} + r_m  \quad  0 < r_m < r_{m-1}</math><br>
 
<math>r_{m-1}= q_m\cdot r_m + r_{m+1}    \quad\quad  0 = r_{m+1}</math> <br>                     
 
<math>r_{m-1}= q_m\cdot r_m + r_{m+1}    \quad\quad  0 = r_{m+1}</math> <br>                     
 +
 
<br>
 
<br>
−
Folglich bricht das Verfahren nach endlich vielen Schritten ab, es gilt ggT(a,b)= <math>r_m</math>. Denn aus der ersten Gleichung folgt ggT(a,b)=ggT(b, <math>r_1</math>), aus der zweiten ggT(b, <math>r_1</math>)=ggT(<math>r_1</math>, <math>r_2</math>), usw. aus der letzten Gleichung folgt
+
Beweis:<br>Folglich bricht das Verfahren nach endlich vielen Schritten ab, es gilt ggT(a,b) = <math>r_m</math>. Denn aus der ersten Gleichung folgt ggT(a,b) = ggT(b, <math>r_1</math>), aus der zweiten ggT(b, <math>r_1</math>) = ggT(<math>r_1</math>, <math>r_2</math>), usw. aus der letzten Gleichung folgt
−
ggT(<math>r_{m-1}</math>, <math>r_m</math> ) = ggT (<math>r_m</math>, <math>r_{m+1}</math>) = <math>r_m</math> [[Benutzer:Deininger_Matthias/Facharbeit/Quod_erat_demonstrandum|  □  ]]
+
ggT(<math>r_{m-1}</math>, <math>r_m</math> ) = ggT (<math>r_m</math>, <math>r_{m+1}</math>) = <math>r_m</math> [[Benutzer:Deininger_Matthias/Facharbeit/Quod_erat_demonstrandum|  □  ]]<br>
 +
</div>
 +
<br>
 +
<div style = "background-color: #BEFF9E; border: 2px solid #E5CC00;border-color: green;">
 +
<u>Aufgabe:</u><br>
 +
<br>
 +
Da Alice Gefallen an der getarnten Übermittlung von Zahlen gefunden hat und weil sie hofft, den Unbekannten damit zu verwirren, sendet sie auch das genaue Datum ihres jährlichen Treffens im August mit der „ggT-Methode“ an Bob. Beim diesjährigen Treffen möchten die beiden unter anderem die richtige Verwendung des Verschlüsselungsalgorithmus besprechen, den sie anschließend für ihre Kommunikation nutzen wollen. Alice verheimlicht diesmal sogar, dass sie die ggT-Methode verwendet, doch Bob erkennt den zusammenhanglosen Satz als „Chiffre“.<br>
 +
'''''„Bob, bevor ich es wieder vergesse: Das Geburtsjahr meiner Oma ist 1911 und mein großer Bruder ist 1980 geboren.“'''''<br>
 +
<br>
 +
Folglich ist der größte gemeinsame Teiler von 1911 und 1980 gesucht.</div><br>
 +
<br>
 +
<math>1980 = 1911\cdot 1 + 69</math><br>
 +
<math>1911 = 69\cdot 27+48</math><br>
 +
<math>69\quad= 48\cdot 1+21</math><br>
 +
<math>48\quad = 21\cdot 2+6</math><br>
 +
<math>21\quad = 6\cdot 3+3</math><br>
 +
<math>6\ \quad\ = 3\cdot 2 +0</math><br>
 +
<br>
 +
Also ist 3 der größte gemeinsame Teiler von 1911 und 1980, woraus folgt, dass sich Alice und Bob am 03.08 treffen möchten.<br>
 +
Zur Überprüfung hier die Primfaktorenzerlegung von<br>
 +
<math>1911 =\ \quad\quad\quad\quad\quad\ 3\cdot 7\cdot 7\cdot 13</math><br>             
 +
<math>1980=  \quad\quad    2\cdot 2\cdot 3\cdot 3\cdot 5\cdot 11</math><br>
 +
<math>ggT(1911,1980)\ =\ 3</math><br>
 +
<br>
 +
====Erweiterter Euklidischer Algorithmus====
 +
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''[http://de.wikipedia.org/wiki/Hilfssatz Lemma] 1.4''' <ref name="K2">[1, S.121]</ref>(Lemma von Bézout) Zu <math>a,b \in \Z</math> existieren ganze Zahlen x und y mit <math>ggT(a,b) = x \cdot a + y\cdot b</math><br></div>
 +
<br>
 +
<popup name="Beweis">
 +
<br>
 +
Nach Definition 1.1 gilt:<br>
 +
 
 +
Für <math>\frac{a}{y} = ggt(a,b)</math> und für <math>\frac{b}{x} = ggt(a,b)</math> mit geeignetem <math>x,y \in \Z \backslash \{0\}\ und\ a,b \in \Z</math>.<br>
 +
Somit folgt:<br>
 +
<math>\frac{a}{y} = \frac{b}{x} = ggt(a,b)</math><br>
 +
<math>x\cdot a = y\cdot b = ggt(a,b)</math>□
 +
<br>
 +
</popup>
 +
<br>
 +
„Diese Darstellung des größten gemeinsamen Teilers zweier Zahlen heißt auch '''Vielfachsummendarstellung'''. Das Lemma ist eine unmittelbare Folgerung aus dem Euklidischen Algorithmus.[...] Beides zusammen - Euklidischer Algorithmus und Vielfachsummendarstellung – heißt ''' der erweiterterte Euklidische Algorithmus'''.“<ref name="K2"/><br>
 +
<br>
 +
<div style = "background-color: #BEFF9E; border: 2px solid #E5CC00;border-color: green;">
 +
<u>Aufgabe:</u><br>
 +
<br>
 +
Bob übermittelt mit gleichem Verfahren, wie lange er bei Alice bleiben kann.<br>
 +
'''''„Ich werde dich, wie schon vor 350 Tagen, auch diesmal gerne besuchen und die 585 km Anfahrt in Kauf nehmen.“'''''<br>
 +
<br>
 +
Wie lange wird Bob bleiben? Berechne den ggT von 350 und 585 mithilfe des Euklidischen Algorithmus.</div><br>
 +
 
 +
<popup name="Lösung">
 +
<math>585 = 350\cdot 1+ 235</math><br>
 +
<math>350 = 235\cdot 1+ 115</math><br>
 +
<math>235 = 115\cdot 2+5</math><br>
 +
<math>115 = 5\cdot 23+0</math><br>
 +
<math>folglich\ ist\ der\ ggT(350,585)= 5 </math><br><br>
 +
<math>Bob\  will\ also\ 5\ Tage\ bei\ Alice\ bleiben.\ </math><br><br>
 +
<math>Hier\ zur\ Kontrolle\ die\ Primfaktorzerlegung:</math><br>
 +
<math>350 = 2\cdot 5\cdot 5\cdot 7</math><br>
 +
<math>585 = 3\cdot 3\cdot 5\cdot 13</math><br>
 +
<math>ggT(350,585)\ = 5</math>
 +
</popup>
 +
<br>
 +
Nun soll noch die Vielfachsummendarstellung von 585 und 350 bestimmt werden:<br>
 +
<br>
 +
<math>5 = 235-115\cdot 2 =</math><br>
 +
&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad = 235 -(350-235)\cdot2=  3\cdot 235-2\cdot 350=</math><br>
 +
&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad=(585-350)\cdot 3 -2\cdot 350=  \underbrace {3\cdot 585+(-5)\cdot 350}_{Vielfachsummendarstellung}</math><br>
 +
<br>
 +
<br>
 +
Der Euklidische Algorithmus lässt sich mithilfe von Computerprogrammen effizient umsetzen. Um das effizienteste Verfahren zur Umsetzung des Euklidischen Algorithmus kennen zu lernen, benötigst du noch Grundlagen der Modulo-Rechnung, die du auf der nächsten Seite kennen lernen wirst.
 +
<br><br>
 +
[[Bild:Weiter.png|weiter]] [[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen_2| ''' weiter zur Modulo-Rechnung''']]
 +
<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, 00:58 Uhr

Buch.PNG Fachwortverzeichnis

Inhaltsverzeichnis

Mathematische Grundlagen

Berechnungskomplexität

In der Kryptographie ist häufig die Rede von effizienten oder uneffizienten Verfahren; Alice hat dazu Folgendes gelesen:

Die Entscheidung, ob ein Verfahren als effizient gilt oder nicht, beruht lediglich auf der Berechnungskomplexität des Verfahrens und nicht auf den verwendeten Computersystemen.
Die Berechnungskomplexität bezeichnet dabei den Speicherbedarf S und Zeitbedarf T der untersuchten Funktion, was als Laufzeitfunktion bezeichnet wird. Dies kann man mittels der sogenannten „Big-O-Notation“ oder „Groß-O-Schreibweise“ angeben.

Die „Big-O-Notation“ beruht darauf, dass die Laufzeit einer Funktion hauptsächlich von der größten Potenz abhängig ist und alle anderen Faktoren als trivial gelten können. Folglich wird nur diese größte Potenz der Funktion in der „Big-O-Notation“ berücksichtigt.
Die Laufzeit einer Funktion hängt von der Bitlänge n des verwendeten Schlüssels ab, weshalb diese Größe als Variable n in die „Big-O-Notation“ mit eingeht.

Beispiel: Die Laufzeitkomplexität einer Funktion lautet: 5n^2+3n+1, also würde diese Funktion als „Big-O-Notation“, so angegeben werden: O(n^2)

Um nun zu bestimmen, ob eine Funktion als effizient gilt, unterscheidet man unter anderem:

effizient uneffizient
Konstant O(1)\ Polynomial O(n^m),\ m > 6, m = konst.
Linear O(n)\ Exponentiell O(t^{f(n)}),\ wobei\ t > 1 , t = konst. , f(n) = n^m + ... + a\cdot n+ c, m = konst.
Polynomial O(n^m),\ m\le 6, m = konst.


Was dies für die reale Berechnungszeit bedeutet, zeigt die Tabelle:

Klasse Komplexität Anzahl der Operationen für n = 10^9 Laufzeit* Anzahl der Operationen für n = 10^{10} Laufzeit*
Konstant O(1)\ 1 1 Nanosekunde 1 1 Nanosekunde
Linear O(n)\ 10^9 1 Sekunde 10^{10} 10 Sekunden
Quadratisch O(n^2)\ 10^{18} 32 Jahre 10^{20} 3171 Jahre
Kubisch O(n^3)\ 10^{27} 3 \cdot 10^{10} Jahre
(entspricht ungefähr dem Alter des Universums[1])		 10^{30} 3 \cdot 10^{13} Jahre
(entspricht ungefähr dem 1000-fachen
des Alters des Universums[1])
Exponentiell O(2^n)\ 10^{301030000} 10^{301029973}-fache
des Alters des Universums[1]		 10^{3010300000} 10^{3010299973}-fache
des Alters des Universums[1]
*Laufzeitangaben wurden unter der Annahme das der Computer 10^9 Operationen pro Sekunde ausführen kann gerundet.


Aber nun zu den mathematischen Grundlagen, die für RSA relevant sind.

Größter gemeinsamer Teiler

Aufgabe:

Alice möchte Bob die Punktzahl ihrer letzten Matheklausur übersenden. Da sie nun weiß, dass ein Unbekannter ihre Nachrichten liest, versucht sie die Information so zu übersenden, dass Mallory die Punktzahl nicht herausfindet. Weil sie noch kein Verschlüsselungsverfahren einsetzt, versucht sie es wie folgt:
„Meine Punktzahl ist der größte gemeinsame Teiler der Zahlen 90 und 105.“
 Und es funktioniert tatsächlich, Mallory, der Mathe immer gehasst hat, erkennt nicht, welche Punktzahl Alice erreicht hat.

Kannst du die Punktzahl von Alice ermitteln?


Den größten gemeinsamen Teiler (ggT) von natürlichen Zahlen hast du bereits in der 5.Klasse berechnet. Dazu hast du, wie in obigem Beispiel, Zahlen in ihre Primfaktoren zerlegt und daraus anschließend den ggT ermittelt. Dass es zu jeder natürlichen Zahl n eine eindeutige Primfaktorzerlegung gibt, zeigt folgender Satz:

Satz 1.0[2](Fundamentalsatz der elementaren Zahlentheorie oder Satz über die eindeutige Primfaktorzerlegung)

Jede natürliche Zahl n > 1 lässt sich auf eindeutige Weise in ein Produkt von Primfaktoren zerlegen.


Der größte gemeinsame Teiler ist allgemein, wie folgt, definiert:

Definition 1.1[3] Es seien a,b \in \Z. Die größte natürliche Zahl, die sowohl a als auch b teilt, heißt größter gemeinsamer Teiler und wird mit ggT(a,b) bezeichnet.


Euklidischer Algorithmus

Es gibt eine effizientere Methode als die Primfaktorzerlegung, um den ggT zweier natürlicher Zahlen zu bestimmen und damit die Punktzahl von Alice zu ermitteln. Diese Methode wird als Euklidischer Algorithmus bezeichnet, weil er ca. 300 v. Chr. von Euklid in seinem Buch „Elemente“ beschrieben wurde. Historiker vermuten jedoch, dass Euklid den Algorithmus nicht selbst entdeckt hat, und schätzen die Entstehungszeit auf ca. 500 v. Chr.
Der Algorithmus beruht auf Division mit Rest.

Algorithmus 1.2[4] (Euklidischer Algorithmus) Es seien a,b \in \Z. Man bestimmt r \in \N_0,\ p \in \Z, so dass gilt:

a\ =\ b\cdot p + r\ und\ 0\le r < b

Dann gilt ggT(a,b) = ggT(b,r).
Anschließend wendet man das Verfahren auf b und r an. Dies führt man so lange fort, bis man den ggT direkt bestimmen kann.


Für die Zahlen von Alice würde dies bedeuten:
105 = 90\cdot1 + 15
90\ =\ 6\cdot15 +0
\Rightarrow ggT(90,105) = 15

In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:

Algorithmus 1.3 [3]Es seien a,b \in \Z, oBdA.* (ohne Beschränkung der Allgemeinheit) sei a\ge b\ge0 (*da Analoges auch für b\ge a gilt und da gilt: ggt(a,b) = ggt(a,-b)). Dann existieren eindeutig bestimmte Zahlen r_1 > r_2 > r_3 > ... > r_m > r_{m+1} =0\ und q_1,q_2,q_3,...,q_m \in \N_0 mit

a = q_1\cdot b+r_1 \quad\ \quad\ 0 < r_1< b
b = q_2\cdot r_1+ r_2 \quad\ \quad 0 < r_2 < r_1
r_1= q_3\cdot r_2 + r_3 \quad \quad 0 < r_3 < r_2
                                     \quad \cdot
                                     \quad \cdot
                                     \quad \cdot
r_{m-2}= q_{m-1}\cdot r_{m-1} + r_m \quad 0 < r_m < r_{m-1}
r_{m-1}= q_m\cdot r_m + r_{m+1} \quad\quad 0 = r_{m+1}


Beweis:
Folglich bricht das Verfahren nach endlich vielen Schritten ab, es gilt ggT(a,b) = r_m. Denn aus der ersten Gleichung folgt ggT(a,b) = ggT(b, r_1), aus der zweiten ggT(b, r_1) = ggT(r_1, r_2), usw. aus der letzten Gleichung folgt ggT(r_{m-1}, r_m ) = ggT (r_m, r_{m+1}) = r_m □


Aufgabe:

Da Alice Gefallen an der getarnten Übermittlung von Zahlen gefunden hat und weil sie hofft, den Unbekannten damit zu verwirren, sendet sie auch das genaue Datum ihres jährlichen Treffens im August mit der „ggT-Methode“ an Bob. Beim diesjährigen Treffen möchten die beiden unter anderem die richtige Verwendung des Verschlüsselungsalgorithmus besprechen, den sie anschließend für ihre Kommunikation nutzen wollen. Alice verheimlicht diesmal sogar, dass sie die ggT-Methode verwendet, doch Bob erkennt den zusammenhanglosen Satz als „Chiffre“.
„Bob, bevor ich es wieder vergesse: Das Geburtsjahr meiner Oma ist 1911 und mein großer Bruder ist 1980 geboren.“

Folglich ist der größte gemeinsame Teiler von 1911 und 1980 gesucht.


1980 = 1911\cdot 1 + 69
1911 = 69\cdot 27+48
69\quad= 48\cdot 1+21
48\quad = 21\cdot 2+6
21\quad = 6\cdot 3+3
6\ \quad\ = 3\cdot 2 +0

Also ist 3 der größte gemeinsame Teiler von 1911 und 1980, woraus folgt, dass sich Alice und Bob am 03.08 treffen möchten.
Zur Überprüfung hier die Primfaktorenzerlegung von
1911 =\ \quad\quad\quad\quad\quad\ 3\cdot 7\cdot 7\cdot 13
1980= \quad\quad 2\cdot 2\cdot 3\cdot 3\cdot 5\cdot 11
ggT(1911,1980)\ =\ 3

Erweiterter Euklidischer Algorithmus

Lemma 1.4 [5](Lemma von Bézout) Zu a,b \in \Z existieren ganze Zahlen x und y mit ggT(a,b) = x \cdot a + y\cdot b



„Diese Darstellung des größten gemeinsamen Teilers zweier Zahlen heißt auch Vielfachsummendarstellung. Das Lemma ist eine unmittelbare Folgerung aus dem Euklidischen Algorithmus.[...] Beides zusammen - Euklidischer Algorithmus und Vielfachsummendarstellung – heißt der erweiterterte Euklidische Algorithmus.“[5]

Aufgabe:

Bob übermittelt mit gleichem Verfahren, wie lange er bei Alice bleiben kann.
„Ich werde dich, wie schon vor 350 Tagen, auch diesmal gerne besuchen und die 585 km Anfahrt in Kauf nehmen.“

Wie lange wird Bob bleiben? Berechne den ggT von 350 und 585 mithilfe des Euklidischen Algorithmus.


Nun soll noch die Vielfachsummendarstellung von 585 und 350 bestimmt werden:

5 = 235-115\cdot 2 =
    \quad = 235 -(350-235)\cdot2= 3\cdot 235-2\cdot 350=
    \quad=(585-350)\cdot 3 -2\cdot 350= \underbrace {3\cdot 585+(-5)\cdot 350}_{Vielfachsummendarstellung}


Der Euklidische Algorithmus lässt sich mithilfe von Computerprogrammen effizient umsetzen. Um das effizienteste Verfahren zur Umsetzung des Euklidischen Algorithmus kennen zu lernen, benötigst du noch Grundlagen der Modulo-Rechnung, die du auf der nächsten Seite kennen lernen wirst.

weiter weiter zur Modulo-Rechnung

zurück zur Übersicht

  1. ↑ 1,0 1,1 1,2 1,3 Die physikalischen Daten stammen aus [8, S.21].
  2. ↑ Satz 1.0 und dessen Beweis stammen aus [7, S.62f.].
  3. ↑ 3,0 3,1 [1, S.120]
  4. ↑ [2, S.106]
  5. ↑ 5,0 5,1 [1, S.121]

siehe dazu Literaturverzeichnis

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