Cryptography Reference
In-Depth Information
4.1.2
Sätze von Fermat und Euler, Eulersche -Funktion
4.1.2.1
Die Eulersche -Funktion
Wir betrachten ganze Zahlen z aus dem Intervall [1, n1], welche teilerfremd zu dem Modul n
sind. d.h. der größte gemeinsame Teiler von z und n ist ggT(n, z)=1. Die Menge der zu n tei-
lerfremden Zahlen aus [1, n1] lautet dann formal:
*
¢
{z
[1,n 1]|ggT(n,z)
1}
(4.1-3)
n
Falls n=p eine Primzahl ist, sind alle Zahlen aus [1, p1] teilerfremd zu p. Es ist dann
*
¢
{1, 2 , . . . p
1}
(4.1-4)
p
Die Eulersche Phi-Funktion (n) bezeichnet die Quantität (die Zahl der Elemente) aus
[1, p1], welche teilerfremd zu n sind.
*
-
(n)
|
¢
|
(4.1-5)
n
Für eine Primzahl n=p ist die Zahl der Elemente in (4.1-4) gleich p1. Somit ist
-
(p)
p
1
(4.1-6)
Falls der Modul n sich als Produkt aus zwei verschiedenen Primzahlen zusammensetzt, ergibt
sich die -Funktion zu =(1p)·(1q).
n
p q
wobei
p
q
(4.1-7)
-
(pq) pq1(q )(p ) (p )(q )
(4.1-8)
Zur Ableitung in (4.1-8) müssen wir von den Elementen in [1, p·q1] noch die Elemente ab-
ziehen, die ein Vielfaches von p sind (1p, 2p,...(q-1)p) und die ein Vielfaches von q sind
(1q, 2q,...(p-1)q).
Der Modul n=pq spielt bei dem RSA-Algorithmus (Kap. 4.2) eine wichtige Rolle.
4.1.2.2
Satz von Euler und Fermat
Der Satz von
Euler
lautet:
a
-
(n)
1
(mod n)
für
a
0
und
ggT(n, a)
1
(4.1-9)
Der Satz gilt für alle positiven und ganzzahligen Werte von a, die teilerfremd zu n sind. Wir
wollen den Satz hier nicht beweisen, sondern uns auf anschauliche Beispiele beschränken. Der
Kleine Satz von
Fermat
ergibt sich als Sonderfall, dass der Modul prim und damit (p)=p1
ist.
p1
a
1
(mod p)
für
a
0
und
ggT(p, a)
1
(4.1-10)
Für den Fall n=p=prim ist jedes a aus [1, p1] teilerfremd zu p. Die Eigenschaft, dass eine
Potenz von a modulo n auf den Wert 1 führt, wird in der Kryptographie oft genutzt.
