Zahlentheoretische Grundlagen der Kryptografie
Sätze von Fermat und Euler
Satz von Euler
Ein wichtiger Satz der Gruppentheorie sagt Folgendes aus:
Satz: Sei (G, • , e) eine endliche Gruppe mit neutralem Element e. Dann gilt für alle a ∈ G
a|G| = e.
Dieser Satz bildet die Grundlage für folgenden Satz von Euler
.
Satz: (Euler)
Sei n ∈ ℕ. Dann gilt für alle a ∈ ℕ, die teilerfremd zu n sind
aφ(n) ≡ 1 (mod n).
Beweis: Da ≡ (mod n) eine Kongruenzrelation ist, also verknüpfungstreu ist, gilt
aφ(n) ≡ (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 ℤn*, 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 Fermat:
Satz: (Fermat)
Sei p eine Primzahl. Dann gilt für alle a ∈ ℕ, die nicht durch p teilbar sind
a p-1 ≡ 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-Verschlü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 ∈ ℕ0 und für alle k ∈ ℕ0
ak·φ(n)+1 ≡ 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 ∈ ℕ0. 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 ∈ ℤ
| a ≡ b (mod p) | ||
| ∧ | a ≡ b (mod q) | |
| ⇒ | a ≡ b (mod pq). |
Beweis: Nach Definition von ≡ ist a – b teilbar durch p und durch q, also auch durch pq.
Es folgt der Beweis des modifizierten Satzes von Euler. Nach Voraussetzung sind p und q zwei verschiedene Primzahlen.
Beweis: Sei zunächst a
0 (mod p). Dann gilt nach dem Satz von Fermat
a p-1 ≡ 1 (mod p)
und damit, zunächst modulo p gerechnet
a k·φ(n)+1 ≡ a k(p-1)(q-1)+1 ≡ a·(a p-1) k(q-1) ≡ a·1k(q-1) ≡ a (mod p).
Diese Formel gilt auch für a ≡ 0 (mod p), also insgesamt für alle a ∈ ℕ0.
Mit den gleichen Überlegungen erhält man dasselbe modulo q:
a k·φ(n)+1 ≡ a (mod q).
Nach dem Hilfssatz folgt schließlich
a k·φ(n)+1 ≡ a (mod pq)
und mit n = p·q folgt die Behauptung.
Weiter mit: [Multiplikativ inverses Element modulo n] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 29.04.2002 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden