Cryptography Reference
In-Depth Information
Der Homomorphiesatz.
Ist
ϕ
:
G
→
H ein surjektiver Homomorphismus von der
Gruppe G auf die Gruppe H, so gilt
ϕ
=
G
/ ker
H
.
Nun zu dem angekündigten Satz:
Satz 8.7
Es sei n eine ungerade zusammengesetzte natürliche Zahl. Weiter sei
A
:
=
{
a
∈{
1, . . . ,
n
−
1
}
;
n ist starke Pseudoprimzahl zur Basis a
}
.
−
n
1
Dann gilt:
|
A
|≤
.
4
Beweis.
In
A
existiert auf jeden Fall ein Element
a
, das eine Kongruenz der Art
a
2
r
d
≡−
(
)
∈{
−
}
1
mod
n
für ein
r
0, . . . ,
s
1
erfüllt, da nämlich im Falle
a
d
d
≡
(
)
(
−
)
≡
1
mod
n
auch die Kongruenz
a
−
1
(
mod
n
)
gilt - man beachte, dass
d
ungerade ist.
die größte Zahl mit der Eigenschaft
a
2
k
d
∈{
−
}
≡−
(
)
Es sei
k
0, . . . ,
s
1
1
mod
n
für ein
a
∈
A
. Es gilt dann für alle
a
∈
A
:
a
2
k
d
(
∗
)
≡±
1
(
mod
n
)
.
p
ν
1
p
ν
Z
n
, dabei seien
n
Wir betrachten die folgenden Untergruppen von
=
···
2
k
d
(beachte, dass wegen
die kanonische Primfaktorzerlegung von
n
und
m
:
=
2
s
d
ist):
<
−
=
k
s
die Zahl
m
ein echter Teiler von
n
1
∈
Z
n
;
a
n
−
1
=
{
≡
(
)
}
J
a
1
mod
n
,
=
a
}
,
mod
p
ν
i
i
∈
Z
n
;
a
m
K
≡±
1
(
)
für alle
i
∈{
1, . . . ,
=
a
)
,
∈
Z
n
;
a
m
≡±
(
L
1
mod
n
a
.
∈
Z
n
;
a
m
M
=
≡
1
(
mod
n
)
⊆
Z
n
.Im
⊆
(
∗
)
⊆
⊆
⊆
Offenbar gelten die Inklusionen
A
L
(vgl.
) und
M
L
K
J
n
−
1
4
Folgenden begründen wir
|
L
|≤
, hieraus folgt dann die Behauptung.
Z
p
ν
1
×···×
Z
p
ν
Z
n
mit
Nach Lemma 7.5 dürfen wir
identifizieren. Für die Po-
Z
p
ν
1
×···×
Z
p
ν
a
m
,
m
2
k
d
,in
→
=
tenzabbildung
π
m
:
a
gilt dann:
=
π
−
1
=
π
−
1
=
(
{±
(
)
}
)
(
{
(
±
±
)
}
)
M
ker
π
m
,
L
1, . . . , 1
,
K
1, . . . ,
1
.
m
m
Wir begründen nun die beiden Aussagen:
(1)
|
L
|
=
2
|
M
|
und
2
|
(2)
|
K
|
=
M
|
.
