Cryptography Reference
In-Depth Information
3.5
Wiederholung Zahlentheorie
Im nächsten Abschnitt werden wir uns klassische Kryptosysteme, in denen einzelne Buch-
staben oder Blöcke von Buchstaben verschlüsselt werden, ansehen. Diese Kryptosysteme
beschreibt man am einfachsten mit Begriffen aus der Zahlentheorie. In diesem Abschnitt
werden wir deshalb einige Begriffe und Sachverhalte aus der Algebra und der (algorithmi-
schen) Zahlentheorie, sofern erforderlich, kurz wiederholen. Für eine eingehendere Einfüh-
rung verweisen wir auf die einschlägige Literatur (siehe etwa [153]). In späteren Kapiteln
werden wir zusätzliches Hintergrundwissen im Bereich der Zahlentheorie benötigen, wel-
ches aber erst dann eingeführt werden wird.
Mit
N
wird die Menge
{
0
,
1
,
2
,...}
der
natürlichen Zahlen
und mit
Z
die Menge
{
der
ganzen Zahlen
bezeichnet. Falls
n
eine positive ganze Zahl
und
a ∈
Z
ist, so werden mit
a
div
n
und
a
mod
n
die eindeutig bestimmten Zahlen
q
und
r
bezeichnet, für die
a
=
nq
+
r
und
r
...,
−
2
,
−
1
,
0
,
1
,
2
,...
}
∈{
0
,...,n
−
1
}
gelten. Die Zahl
a
mod
n
heißt auch
Rest von
a
modulo
n
.
Unter einem
Ring
wollen wir in diesem Buch einen kommutativen Ring mit Eins
verstehen.
Für eine ganze Zahl
n ≥
2
bezeichnet
,die
man zu einem Ring erweitert, indem man eine Addition
+
n
und eine Multiplikation
Z
n
die Menge der Zahlen
{
0
,
1
,...,n−
1
}
·
n
durch
a
+
n
b
=
a
+
b
mod
n
a ·
n
b
=
a · b
mod
n
für
a, b ∈
Z
n
definiert. Man nennt diesen Ring auch den
Restklassenring modulo
n
;jedeZahlin
Z
n
ist
ein Repräsentant einer Restklasse modulo
n
.
Für einen Ring
R
bezeichnet
R
∗
die Menge der Elemente, die ein multiplikatives
Inverses besitzen, d. h.,
R
∗
=
{a ∈ R |∃b
(
b ∈ R ∧ ab
=1)
}
. Die Elemente dieser Menge
werden als
Einheiten
bezeichnet, zusammen mit der Multiplikation des Ringes bildet
diese Menge eine Gruppe, die sogenannte
Einheitengruppe
des Ringes.
Ein von Null verschiedenes Element
a
einesRingesheißt
Nullteiler
,wenneseinvon
Null verschiedenes Element
b
gibt, so dass
ab
=0
gilt. Es gilt:
Lemma 3.5.1.
In jedem endlichen Ring ist jedes Element entweder
0
, eine Einheit od
er
ein Nullteiler.
Dies gilt insbesondere für den Restklassenring
Z
n
. Man beachte, dass die Einschrän-
kung auf endliche Ringe wichtig ist: Im Ring
der ganzen Zahlen (mit der üblichen
Addition und Multiplikation) ist zum Beispiel die Zahl
2
weder
0
, eine Einheit noch ein
Nullteiler. Ein Ring, in dem es keine Nullteiler gibt, heißt
Integritätsring.
Ein Beispiel
für einen solchen Ring ist der Ring
Z
der ganzen Zahlen.
In einem beliebigen Ring
R
ist
a
ein
Teiler
von
b
(kurz:
a
Z
|
b
), wenn es
c
∈
R
mit
ac
=
b
gibt. Ein
größter gemeinsamer Teiler
von Elementen
a, b
R
ist ein Teiler von
a
und
b
,
der von jedem Teiler von
a
und
b
geteilt wird. Ist nun
c
ein größter gemeinsamer Teiler
von
a
und
b
und
e
eine Einheit, dann ist auch
ce
ein größter gemeinsamer Teiler von
a
∈
