Cryptography Reference
In-Depth Information
Weiter gilt
L
p
(
a
)=
a
(
p−
1)
/
2
rmod
p
=(
a
mod
n
)
(
p−
1)
/
2
rmod
p
=L
p
(
a
mod
n
)
, für alle
Primzahlen
p>
2
mit
p | n
. Gleichung (6.3.11) sieht man leicht.
Gleichung (6.3.7) gilt trivialerweise für
n
=1
. Wir betrachten im Folgenden deshalb
nur noch den Fall
n>
2
. Zunächst erinnern wir uns:
L
p
(
1)
(
p−
1)
/
2
rmod
p
für alle
−
1) = (
−
Primzahlen
p>
2
. Also gilt
L
p
(
1
gemäß (6.3.4) genau dann, wenn
p
mod
4=3
.
Es sei nun
n
=
i<r
p
i
mit Primzahlen
p
i
,wobeidie
p
i
nicht paarweise verschieden
sein müssen, und sei
s
die Anzahl der
i
mit
p
i
mod
4=3
. Dann gilt
J
n
(
−
1) = (
−
1)
s
.
−
1) =
−
Weiterhin gilt
n
rmod
4=
i<r
(
p
i
rmod
4) = (
1)
s
, was nach (6.3.4) bedeutet, dass
(
n −
1)
/
2
genau dann gerade ist, wenn
s
gerade ist. Daraus folgt dann die Behauptun
g.
Gleichung (6.3.8) ist schwieriger zu beweisen, weshalb wir hier darauf verzichten.
2
−
Der folgende Satz formuliert nun das quadratische Reziprozitätsgesetz für das Jacobi-
Symbol.
Satz 6.3.11 (quadratisches Reziprozitätsgesetz).
Für ungerade Zahlen
m, n ∈
N
gilt:
1)
m−
1
n−
1
2
J
n
(
m
)=(
−
·
J
m
(
n
)
.
2
Aus den aufgeführten Eigenschaften des Jacobi-Symbols lässt sich nun ein einfacher
Polynomzeitalgorithmus für die Berechnung des Jacobi-Symbols entwickeln. Wir halten
folgenden Satz fest.
Satz 6.3.12.
Algorithmus 6.3 berechnet das Jacobi-Symbol
J
n
(
a
)
in Zeit
O
(log
n
+log
a
)
für alle Zahlen
a
∈
Z
und ungerade Zahlen
n
∈
Z
.
Primzahltests und Faktorisieren
Es ist unbekannt, ob es einen (klassischen) Polynomzeitalgorithmus gibt, sei es auch nur
ein Algorithmus mit erwarteter polynomieller Laufzeit, der die Primfaktorzerlegung einer
zusammengesetzten Zahl berechnet. Es wird allgemein angenommen, dass ein solcher Al-
gorithmus nicht existiert; allerdings gibt es, wie bereits in Abschnitt 1.4 erwähnt, einen
ezienten Faktorisierungsalgorithmus, der auf Quantencomputern beruht. Die Entwick-
lung von Quantencomputern steht jedoch noch am Anfang und es bleibt abzuwarten, ob
diese Computer irgendwann auch in der Praxis eingesetzt werden können. Wir konzentrie-
ren uns in diesem Buch deshalb auf klassische Computer. Die besten bekannten Verfahren
für klassische Computer zur Faktorisierung großer Zahlen basieren auf dem sogenannten
(allgemeinen) Zahlkörpersieb und haben eine heuristisch begründete erwartete Laufzeit
von
O
(
e
d·
(ln
n
)
1
/
3
·
(ln ln
n
)
2
/
3
)
für
d ≈
1
,
95
,wobei
n
die zu faktorisierende Zahl bezeichnet
und
ln
n
den natürlichen Logarithmus von
n
. In der Kryptographie betrachtet man mitt-
lerweile Zahlen in der Größenordnung von
2048
Bits. Für solche Zahlen ergibt sich aus
der oben angegebenen Formel eine erwartete Laufzeit in der Größenordnung von
2
120
Re-
chenschritten. Der Aufwand für die Faktorisierung solcher Zahlen liegt also deutlich über
dem, was nach heutigem Stand der Technik möglich ist. Von Zahlen in der Größenord-
nung von
1024
Bits, eine für asymmetrische Kryptoschemen noch häufig anzutreffende
Größe, wird in aktuellen Standards allerdings abgeraten (siehe Abschnitt 6.8).
2 Siehe zum Beispiel [63] für einen Beweis.
