Mathematische Grundlagen: Unterschied zwischen den Versionen
| Zeile 40: | Zeile 40: | ||
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. | + | 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> |
| + | <br> | ||
| + | Für die Zahlen von Alice würde dies bedeuten:<br> | ||
| + | <math>105 = 90\cdot1 + 15</math><br> | ||
| + | <math>90\ =\ 6\cdot15 +0</math><br> | ||
| + | <math>\Rightarrow ggT(90,105) = 15</math> | ||
| + | <br> | ||
| + | <br> | ||
| + | In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:<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> | ||
| + | <br> | ||
| + | <math>a = q_1\cdot b+r_1 \quad\ \quad\ 0 < r_1< b</math><br> | ||
| + | <math>b = q_2\cdot r_1+ r_2 \quad\ \quad 0 < r_2 < r_1</math><br> | ||
| + | <math>r_1= q_3\cdot r_2 + r_3 \quad \quad 0 < r_3 < r_2</math><br> | ||
| + | <math>\quad \cdot</math><br> | ||
| + | <math>\quad \cdot</math><br> | ||
| + | <math>\quad \cdot</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> | ||
| + | <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| □ ]] | ||
Version vom 2. September 2010, 17:39 Uhr
Aber nun zu den mathematischen Grundlagen, die für RSA relevant sind.
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. Das es zu jeder natürlichen Zahl n eine eindeutige Primfaktorzerlegung gibt, zeigt folgender Satz:
Satz 1.0 (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.
eine Zerlegung von n in echt kleiner positive ganze Zahlen d und 
. 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.
in Primfaktoren 
, so das gilt 
.(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 
von allen 
verschieden. Dies steht aber im Widerspruch dazu, dass dies alles Primelemente sind. Da nämlich z.B. 
, die rechte Seite teilt, so muss
Der größte gemeinsame Teiler ist allgemein wie folgt definiert:
Definition 1.1 Es seien 
. 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.
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 (Euklidischer Algorithmus) Es seien 
. Man bestimmt 
, so dass gilt:
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:
In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:
Algorithmus 1.3 Es seien , ohne Beschränkung der Allgemeinheit* (oBdA.) sei 
(*da Analoges auch für 
gilt). Dann existieren eindeutig bestimmte Zahlen 
und 
mit
Folglich bricht das Verfahren nach endlich vielen Schritten ab, es gilt ggT(a,b)= 
. Denn aus der ersten Gleichung folgt ggT(a,b)=ggT(b, 
), aus der zweiten ggT(b, )=ggT(, 
), usw. aus der letzten Gleichung folgt
ggT(
, ) = ggT (, 
) = □
