Zahlentheoretische Grundlagen der Kryptografie

Sätze von Fermat und Euler

 aufwärts

Satz von Euler

Ein wichtiger Satz der Gruppen­theorie sagt Folgendes aus:

Satz:  Sei (G,  • , e) eine endliche Gruppe mit neutralem Element e. Dann gilt für alle a Element G

a|G| = e.

 

Dieser Satz bildet die Grundlage für folgenden Satz von Eulerzur Person.

Satz:  (Euler)

Sei n Element natürliche Zahlen. Dann gilt für alle a Element natürliche Zahlen, die teilerfremd zu n sind

aφ(n)  kongruent  1   (mod n).

Beweis:  Da  kongruent  (mod n) eine Kongruenz­relation ist, also verknüpfungs­treu ist, gilt

aφ(n)  kongruent  (a mod n)φ(n)   (mod n),

d.h. statt mit a können wir auch mit dem Repräsentanten a mod n rechnen. Da ggt(a, n) = ggt(n, a mod n) = 1, gehört a mod n zur Gruppe ganze Zahlenn*, und diese hat φ(n) Elemente. Somit folgt mit dem vorigen Satz die Behauptung.

Satz von Fermat

Ein Spezialfall des Satzes von Euler ist der (historisch wesentlich früher gefundene) kleine Satz von Fermatzur Person:

Satz:  (Fermat)

Sei p eine Primzahl. Dann gilt für alle a Element natürliche Zahlen, die nicht durch p teilbar sind

a p-1  kongruent  1   (mod p).

Der Satz von Fermat folgt unmittelbar aus dem Satz von Euler, da für Primzahlen p gilt φ(p) = p-1.

Modifizierter Satz von Euler

Für das RSA-Ver­schlüsselungsverfahren wird folgende etwas abgeänderte Form des Satzes von Euler benötigt.

Satz:  Sei n = p·q, wobei p und q zwei verschiedene Primzahlen sind. Dann gilt für alle a Element natürliche Zahlen0 und für alle k Element natürliche Zahlen0

ak·φ(n)+1  kongruent  a   (mod n).

Für a mit a teilerfremd zu n ist dieser Satz eine unmittelbare Folgerung aus dem weiter oben angegebenen Satz von Euler. Die Aussage gilt jedoch sogar für beliebige a Element natürliche Zahlen0. Für den Beweis wird zunächst folgender Hilfssatz benötigt.

Hilfssatz:  Seien p, q zwei verschiedene Primzahlen. Dann gilt für alle a, b Element ganze Zahlen

 a kongruent b   (mod p)
 und  a kongruent b   (mod q)
 folgt  a kongruent b   (mod pq).

Beweis:  Nach Definition von  kongruent  ist a – b teilbar durch p und durch q, also auch durch pq.

Es folgt der Beweis des modifizierten Satzes von Euler. Nach Voraus­setzung sind p und q zwei verschiedene Primzahlen.

Beweis:  Sei zunächst anicht kongruent0 (mod p). Dann gilt nach dem Satz von Fermat

a p-1 kongruent 1   (mod p)

und damit, zunächst modulo p gerechnet

a k·φ(n)+1   kongruent   a k(p-1)(q-1)+1   kongruent   a·(a p-1) k(q-1)   kongruent   a·1k(q-1)   kongruent   a   (mod p).

Diese Formel gilt auch für a kongruent 0 (mod p), also insgesamt für alle a Element natürliche Zahlen0.

Mit den gleichen Überlegungen erhält man dasselbe modulo q:

a k·φ(n)+1   kongruent   a   (mod q).

Nach dem Hilfssatz folgt schließlich

a k·φ(n)+1   kongruent   a   (mod pq)

und mit n = p·q folgt die Behauptung.

 

Weiter mit:   [Multiplikativ inverses Element modulo n]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 29.04.2002   Updated: 29.11.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik