Cryptography Reference
In-Depth Information
Wegen
N
kommen höhere Potenzen von 2 nicht vor.
Nun sieben wir beginnend mit 4 (in Zweierschritten), dann mit
a
3
≡
5
(
mod 8
)
=
=
1, mit
b
3
−
1, mit
a
5
=
−
1, mit
b
5
=
−
2 und schließlich mit
a
7
,
b
7
in einem Schritt.
−
−
−
−
−
i
5
4
3
2
1
0
1
2
3
4
5
(
)
−
−
−
−
−
−
f
i
228
189
148
105
60
13
36
87
140
195
252
−
−
−
:4
57
37
15
9
35
63
−
−
:3
19
35
3
65
−
−
:3
63
5
29
21
−
:5
1
13
:5
−
7
7
−
−
1 1
3
Das Sieben mit 9 und 27 haben wir übersprungen. Die verbleibenden Potenzen
von 3 sind bei der Aufstellung der Matrix zu berücksichtigen. Wir geben exem-
plarisch zwei Spalten an:
:7
9
. Insge-
samt findet man sechs. Wendet man die Large Prime Variation mit der Primzahl
13 an, so erhält man eine weitere.
ν
(
−
4
)=(
1, 0, 3, 0, 1
)
und
ν
(
3
)=(
0, 2, 0, 1, 1
)
Bemerkung
Wählt man
B
von der Größenordnung exp
2
log log
N
(und
S
von etwa
der gleichen Größenordnung), so ergibt sich die Laufzeit
O
exp
log
N
·
.
log
N
(
·
)
log log
N
Es gibt eine Reihe von Vereinfachungen für dieses Verfahren.
•
Manchmal werden die Rechnungen beschleunigt, wenn man bei Primzah-
len
>
2 darauf verzichtet, höhere Potenzen zu sieben.
•
Statt
U
(
a
)
durch
p
i
zu dividieren, kann man folgendermaßen vorgehen:
(
)=
|
(
)
|
Setze im zweiten Schritt
U
a
log
f
a
.
Ersetze
U
(
a
)
durch
U
(
a
)
−
log
p
i
.
Dabei kann der Logarithums relativ grob angenähert sein, weil wir ja
wis-
sen
, dass
U
(
)
a
teilbar ist, und das delogarithmierte Ergebnis also ganzzahlig
sein muss.
In Abschnitt 14.3 werden wir das Faktorisierungsverfahren ECM, das auf ellipti-
schen Kurven basiert, behandeln. Kettenbruchmethode, ECM und quadratisches
Sieb haben asymptotisch die gleiche Laufzeit. Diese Laufzeit wird vom derzeiti-
gen Rekordhalter
Zahlkörpersieb
, das wir im Rahmen dieses Buches nicht behan-
deln können, unterboten.
