Mathematische Grundlagen 3: Unterschied zwischen den Versionen

Version vom 23. Dezember 2010, 02:06 Uhr

Fachwortverzeichnis

Modulare Inverse

In der 6. Klasse hast du dich schon einmal mit Kehrwerten beschäftigt. Bei der Zahl 2 ist der Kehrwert bezüglich der Multiplikation 0,5. , den Kehrwert kann man auch als multiplikative Inverse bezeichnen. Im Folgenden gilt es zu untersuchen, ob auch modulare Inversen existieren und, wenn ja, unter welchen Bedingungen, wenn wir nur ganzzahlige Inverse betrachten möchten. Aus den Angaben von Alice folgt: Wie für den Kehrwert, so gilt auch für die modulare Inverse, dass das Resultat 1 ergeben muss.

Allgemein gilt also:	Alternative Schreibweise für die modulare Inverse:

Diese Gleichungen sind äquivalent zu:
diese Schreibweise erinnert an Lemma 1.4, wonach man vermuten kann, dass die Gleichung nur für ggT(a,n) = 1 gilt.

Für die Aufgabe von Alice gilt somit:




Falls eine Lösung existiert, soll nun eine ganze Zahl x gefunden werden, so dass die Gleichung erfüllt ist. Wie du anhand von Alices Beispiel selbst überprüfen kannst, ist dies bereits bei so kleinen Zahlen ziemlich schwierig.
Deshalb betrachten wir nun den Satz von der modularen Inversen und werden darauf einen Algorithmus kennen lernen, mithilfe dessen sich die modulo Inverse, die auch als multiplikative Inverse bezeichnet werden kann, relativ einfach berechnen lässt.

Wie du bereits aus Abschnitt 1 weißt, lässt sich der ggT zweier Zahlen mithilfe des Euklidischen Algorithmus bestimmen.

Bei den von Alice gewählten Zahlen gilt ggT(13,24) = 1, also existiert eine modulare Inverse, da lässt sich obiger Algorithmus hier anwenden, um die modulare Inverse zu 13 mod 24 zu bestimmen.
Gesucht sind x und y, für die gilt:
1 = 13x + 24y

Lösung anzeigen

Lösung verstecken

Euklidischer Algorithmus:	alternativ:
11 = 24 mod 13 2  = 13 mod 11 1  = 11 mod 2 0  = 2 mod 1

Vielfachsummendarstellung:

    
    

Also gilt:

Antwort auf die Frage von Alice: Die modulo Inverse zu 13 mod 24 ist 13.

Alice beschäftigt sich jetzt mit dem Satz von Fermat, sowie dem Satz von Euler, weil sie gelesen hat, dass diese Sätze elementar für das RSA-Kryptosystem sind. Folglich solltest auch du diese beiden Sätze kennenlernen, bevor du dich dem RSA-Kryptosystem zuwendest.

Kleiner Satz von Fermat

Alice wählt sich p = 5 und a = 4, um den Satz zu testen.
Somit gilt nach dem kleinen Satz von Fermat:


Beim Satz von Fermat handelt es sich lediglich um einen Sonderfall des Satzes von Euler:

Satz von Euler

Satz 2.6^[2] (Satz von Euler) Es sei , so gilt für jedes a mit ggT(a,n) = 1:

Hierbei bezeichnet die Anzahl der zu n teilerfremden Zahlen aus der Menge {1,2,...,n-1}. Wenn p eine Primzahl ist, so gilt: , für zwei voneinander verschiedene Primzahlen p,q gilt folglich:

weiter zum RSA-Algorithmus

zurück zur Übersicht

1. ↑ ^{1,0 1,1} [2, S.107]
2. ↑ ^{2,0 2,1} Satz 2.5, der zugehörige Beweis und Satz 2.6 wurden [10, S.5] entnommen. Der Beweis zu Satz 2.6 wurde analog zum Beweis von Satz 2.5 entwickelt.

siehe dazu Literaturverzeichnis