Cryptography Reference
In-Depth Information
11.2 Pollards
-Methode *
Bei der Bestimmung diskreter Logorithmen haben wir neben dem Baby-Step-
Giant-Step-Algorithmus Pollards
-Methode in Abschnitt 10.3 beschrieben. Bei
der Methode von Pollard wurde eine (unendliche) Zufallsfolge
(
)
x i
in einer end-
lichen Menge gebildet. Dass es bei einer solchen Folge Indizes i
=
j mit x i =
x j
(
=
)
gibt, ist klar - wir nennen ein solches Tripel
einen Treffer -, der
Clou an der Methode war, dass ein solcher Treffer relativ schnell bestimmt wer-
den kann. In diesem Sinne ist Pollards
x i
x j , i , j
-Methode ein Suchalgorithmus, der aus
einer (unendlichen) Folge
in einer endlichen Menge einen Treffer bestimmt.
Wir können diesen Algorithmus auch für andere Probleme benutzen, etwa zum
Bestimmen von Teilern einer natürlichen Zahl.
(
x i )
11.2.1 Die Idee
Die zusammengesetzte natürliche Zahl N wird von einer - uns unbekannten -
Primzahl p geteilt. Wir suchen zwei ganze Zahlen x und y mit
(
)
(
)
x
y
mod N
und x
y
mod p
.
Angenommen, wir haben solche Zahlen x und y gefunden. Es ist dann
=
(
)
d
ggT
x
y , N
ein nichttrivialer Teiler von N , da:
|
|
|
=
Aus p
x
y und p
N folgt p
d , sodass d
1 gilt, und
=
aus N
x
y folgt d
N .
Wie oben bemerkt ist dann eine Zerlegung von N gefunden, auf die der Algorith-
mus ggf. erneut angewendet werden kann.
11.2.2 Konstruktion der Zahlen x und y
Die Zahlen x und y finden wir mit dem Algorithmus von Pollard. Dabei bilden
wir im Wesentlichen in der endlichen Menge
Z p , wobei p ein unbekannter Prim-
(
)
teiler von N ist, eine (unendliche) Folge
x i
. Für einen Treffer gilt dann die ge-
wünschte Kongruenz:
(
)
=
(
) >
x i
x j
mod p
,d.h. d
ggT
x i
x j , N
1.
Gilt zudem die Inkongruenz x i
x j (
mod N
)
, so folgt d
=
N .
Search WWH ::




Custom Search