Cryptography Reference
In-Depth Information
1.7.1 Der Matrizenring über
R
Ein Element
u
des Ringes
R
heißt
Einheit
, wenn es
v
1. Man
sagt auch,
u
sei
invertierbar.
Die Menge aller Einheiten bildet eine Gruppe
R
×
,
genannt die
Einheitengruppe.
Die Einheitengruppe von
∈
R
gibt mit
uv
=
Z
×
=
{±
.
Aus der linearen Algebra sind Matrizen über einem Körper
K
bekannt. Es wur-
den Addition, Multiplikation und auch die Determinante von quadratischen Ma-
trizen eingeführt. Für jedes
Z
ist z. B.
1
}
K
×
,
∈
N
(
+
·
)
ist
,
ein Ring mit Einselement
I
- die
×
-Matrix
M
über dem Körper
K
ist bekannt-
lich genau dann invertierbar, wenn die Determinante det
M
ungleich 0, d. h. eine
Einheit in
K
ist.
Für die Definitionen war es nicht entscheidend, dass
K
ein Körper ist, diese Defi-
nitionen sind auch für einen Ring
R
möglich. Und man erhält dasselbe Resultat.
Wir bezeichnen den Ring der
-Einheitsmatrix. Und eine
×
-Matrizen über
R
mit der bekannten Addition
und Multiplikation von Matrizen mit
R
×
. Und eine Matrix
M
×
R
×
ist genau
dann invertierbar, wenn die Determinante det
M
in
R
×
liegt, d. h. eine Einheit in
R
ist. Das zeigt man wie in der linearen Algebra mithilfe der Adjunkten. Auch
die meisten Sätze zu Matrizen über einem Körper
K
bleiben im Falle eines Ringes
R
richtig. So gelten etwa
•
∈
der
Laplace'sche Entwicklungssatz
für die Determinante und
•
das
Invertierbarkeitskriterium
für Matrizen: Eine Matrix ist genau dann in-
vertierbar, wenn ihre Spalten linear unabhängig sind.
Beispiel
Wir betrachten zwei Matrizen über dem Ring
Z
8
=
{
(
Z
8
,
+
·
)
}
,
; es gilt
1, 3, 5, 7
.
Wegen
⎛
⎞
det
2
2
3
0
3
⎝
⎠
=
=
−
1
=
7 und det
0
1
1
4
1
1
0
2
0
ist die erste Matrix invertierbar, die zweite jedoch nicht. Es gilt:
⎛
⎞
⎛
⎞
⎛
⎞
⎛
⎞
2
0
0
3
1
2
0
1
0
0
0
0
⎝
⎠
+
⎝
⎠
+
⎝
⎠
=
⎝
⎠
.
2
4
4
Daher sind die Spalten der Matrix linear abhängig.
1.7.2 Affine Abbildungen
R
×
und einen Vektor
v
R
erklären wir die affine Abbil-
Für eine Matrix
M
∈
∈
dung
:
R
→
R
f
.
(
M
,
v
)
x
→
Mx
+
v