RSA, DHM und ihre Grundlagen

Lernpfad erstellt und betreut von:

Harald Burgsteiner

E-mail: harald.burgsteiner@fh-joanneum.at
Steckbrief
Kurs-Informationen
Ansicht mit Navigations-Frame
Lernpfadseite als User öffnen (Login)
Lernpfadseite bearbeiten (Autor)

Übersicht:       
Hilfe
1. Teilbarkeit von ganzen Zahlen
2. Restklassenkörper
3. RSA Algorithmus
4. DHM KEX
5. Literatur

Teilbarkeit von ganzen Zahlen
 
1.1 Grundlagen der Zahlenmengen

Bevor wir uns mit der Teilbarkeit von ganzen Zahlen beschäftigen, ist es wichtig, sich nochmals über die Menge der ganzen Zahlen klar zu werden. Wiederhole dieses Thema anhand des Kapitels 2 des Lernpfads von Gabriel Ranz.

Mache auch den dortigen kleinen Abschlusstest in Abschnitt 2.6!


 
1.2 Definition

Sind a und b Zahlen aus der Menge der ganzen Zahlen, so heißt a durch b teilbar (oder "b teilt a", geschrieben b|a), wenn es eine ganze Zahl q gibt, so dass a = b*q ist.

Mache Dir klar, dass es hier ausschließlich um den Zusammenhang von ganzen Zahlen geht. Natürlich kann man in den reellen Zahlen jede Zahl durch ein reellwertiges Vielfaches einer anderen erhalten. Hier ist die Frage, ob eine ganze Zahl a ein ganzzahliges Vielfaches einer anderen ganzen Zahl ist.

Die Zahlen können natürlich auch negativ sein! Der obige Zusammenhang gilt natürlich auch z.B. für a = -15, b = 3 und q = -5.

Überlege Dir 5 Beispiele von Zahlenpaaren von denen jeweils eine Zahl die andere teilt, bestimme bei jedem Paar das q und schreibe Sie in Deinem Lerntagebuch auf!


Lernstoff, Eintrag in das Lerntagebuch
 
1.3 Teilbarkeitsregeln

Man kann sich aufgrund der Definition von Teilbarkeit leicht überlegen, was daraus alles für mehr als 2 Zahlen folgt.

  • Gilt c|b und b|a, so gilt auch c|a.

    Überlege kurz selbst warum dies so ist!

    Beweis: dies folgt aus der obigen Definition. Aus c|b folgt, dass b = q1*c und aus b|a folgt, dass a = q2*b. Setzt man nun die erste Gleichung in die zweite ein, so ergibt sich a = q2*q1*c. Da q1 und q2 ganze Zahlen sind, ist auch deren Produkt eine ganze Zahl und somit steht hier die Definition der Teilbarkeit von a durch c, also c|a

  • Gilt b1|a1 und b2|a2, so gilt auch b1*b2|a1*a2

  • Gilt b|a und a|b, so gilt a=b oder a=-b.

Überlege Dir aufgrund der obigen Definition Beweise für die beiden letzten Aussagen und schreibe Sie in Deinem Lerntagebuch auf!


Lernstoff, Eintrag in das Lerntagebuch, Übungsaufgaben
 
1.4 Ganzzahlige Division mit Rest

Wahrscheinlich ist Dir bei der ersten Aufgabe aufgefallen, dass nicht jedes Paar von ganzen Zahlen teilbare Zahlen ergibt. Bei solchen Paaren ergibt sich ein Rest. Für jedes Zahlenpaar ist diese Division mit Rest allerdings eindeutig, d.h.

Für 2 ganze Zahlen a,b mit b ungleich 0 gibt es genau eine Darstellung a = b*q + r mit ganzen Zahlen q und r mit 0 ≤ r < |b|.

Dabei heißen a Dividend, b Divisor, q Quotient und r der Rest der Division von a durch b. Wir bezeichnen q mit a/b ("ganzzahlige Divison") und r mit a mod b (sprich "a modulo b").

Finde für b=5 verschiedene Zahlen a, so dass sich unterschiedliche Reste ergeben! Wie viele verschiedene Reste kannst Du finden und warum?


Lernstoff, Eintrag in das Lerntagebuch
 
1.5 Primzahlen

Ein wichtige Teilmenge der natürlichen Zahlen sind die sogenannten Primzahlen. Das sind diejenigen natürlichen Zahlen größer als 1, die eben keinen Teiler haben - außer die trivialen wie 1 und sich selbst.

Diese Primzahlen spielen in der Mathematik eine wichtige Rolle. Ohne Beweis sei hier angeführt, dass z.B. jede natürliche Zahl die keine Primzahl ist, als eindeutiges Produkt von Primzahlen dargestellt werden kann. Außerdem bilden sie die Grundlage für die sogenannten Restklassenkörper, mit denen wir uns im nächsten Kapitel beschäftigen werden.

Was genau sind nun Primzahlen?Teste dich selbst!


Lernstoff, Selfchecking Test
 
1.6 Selbstevaluierung

Kennst du dich nun mit Teilbarkeit aus? Mache den Test!


Selfchecking Test
 
Lernpfadseite als User öffnen (Login)

Falls Sie noch kein registrierter User sind, können Sie sich einen neuen Zugang anlegen. Als registrierter User können Sie ein persönliches Lerntagebuch zu diesem Lernpfad anlegen.

 Zur Galerie
 Zu den Mathematischen Hintergründen
 Zum Lexikon
 Zu den interaktiven Tests
 Zu den Mathe-Links und Online-Werkzeugen
 Zur Welcome Page
   Übersicht über die Lernpfade
 Open Studio Materialien
 Open Studio Eingang
 Neuen Zugang anlegen
 Login