Cryptography Reference
In-Depth Information
2.1.2.2
Nachweis für die Erfüllung von Axiom 11
1
Für jedes Element a
0 gibt es mod n ein multiplikativ inverses Element a
,
(2.1-8)
falls n
p eine Pr imzahl ist.
Die Aussage (2.1-8) wollen wir nachweisen und zunächst an zwei Beispielen überprüfen. Dazu
stellen wir eine Multiplikationstafel a·b auf. In ihr stehen links die Werte für a, oben die Werte
für b und im Kreuzungspunkt der Wert für das Produkt a·b.
Beispiel: n=3 (prim), die Elemente sind a,b
{0, 1, 2}
Multiplikationstafel
· 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
Multiplikativ inverse Elemente
a b=a
-1
1 1
2 2
Die Multiplikationstafel zeigt die Besonderheit, dass (2·2) modulo 3 den Wert 1 hat, denn die
Werte 4 und 1 sind modulo 3 kongruent. Die Tafel der multiplikativ inversen Elemente enthält
alle Werte von a0. Das multiplikativ inverse Element z.B. von a=2 findet man in der Multipli-
kationstafel, indem man in der Zeile für a=2 nach dem Produktwert 1 sucht. Der zugehörige
Wert von b (b=2) ist das gesuchte multiplikative Element a
1
. Eine wichtige Eigenschaft der
Multiplikationstafel ist, dass in jeder Zeile für a0 für die Produkte alle Werte {0, 1, 2} genau
einmal auftreten und somit auch der Wert 1. Das Produkt ist kommunikativ, deshalb ist die
Multiplikationstafel bezüglich a und b symmetrisch.
Beispiel: n=4 (nicht prim), die Elemente sind a,b
{0, 1, 2, 3}
Multiplikationstafel
Multiplikativ inverse Elemente
a b=a
-1
1 1
2 existiert nicht
3 3
· 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
In der Multiplikationstafel für n=4 gibt es in der Zeile für a=2 keinen Produktwert 1. Deshalb
existiert für a=2 kein multiplikativ inverses Element. Diese Eigenschaft entspricht damit der
Aussage von (2.1-8). Man beachte ferner: Für die Werte a=1 und a=3 gibt es multiplikativ
inverse Elemente. (Diese Werte von a haben die Eigenschaft, dass sie relativ prim zum Modul
n=4 sind, d.h. keinen gemeinsamen Teiler haben.)
