Faktorisierung - Kryptologie - page 190

11 Faktorisierung

Beim RSA-Verfahren werden zwei (große) Primzahlen p und q miteinander mul-
tipliziert, was sehr einfach ist. Die Zahl N pq jedoch wieder in ihre Prim-

teiler zu faktorisieren wird als außerordentlich schwierig angesehen. Dabei ist
aber nicht bekannt, ob das Problem der Faktorisierung tatsächlich schwierig ist. Es
könnte ja durchaus auch sein, daß es eine einfache Methode gibt, Zahlen in ihre
Primfaktoren zu zerlegen, diese bisher nur noch nicht bekannt ist. Kurz gesagt,
das Problem ist in NP , aber es ist nicht bekannt, ob es vielleicht in P liegt.
Neben der (naiven) Probedivision , bei der man einfach sukzessive N durch be-
kannte (aber kleine) Primzahlen teilt, gibt es ausgefeilte Methoden, von denen
wir einige in diesem Kapitel vorstellen. Dabei konzentrieren wir uns nicht auf
Zahlen N , die Produkt von zwei Primzahlen sind, wie es beim RSA-Verfahren
verwendet wird. Wir behandeln das Problem der Zerlegung , d. h. der Faktorisie-
rung ganzer (zusammengesetzter) Zahlen allgemein.
Die Methoden, die man dabei benutzt, greifen zum Teil bekannte Verfahren auf.
Wir werden Pollards

=

-Methode erneut ins Spiel bringen, mit dessen Hilfe wir be-
reits diskrete Logarithmen berechnet haben, und die Kettenbrüche , mit deren Hilfe
wir einen Angriff auf RSA geschildert haben, werden wieder eine Rolle spielen.
Weiter werden wir das Verfahren von Fermat , das quadratische Sieb wie auch die
p −

1 -Methode von Pollard behandeln. Die Idee der letztgenannten Methode von
Pollard lässt sich auf elliptische Kurven übertragen. Damit gewinnt man die el-
liptic curve method , die wir aber erst nach der Einführung von elliptischen Kurven
im letzten Kapitel 14 behandeln werden.

11.1 Prinzipielles Vorgehen

Gegeben ist eine natürliche Zahl N . Nach dem Fundamentalsatz 4.14 der Arith-
metik besitzt N von der Reihenfolge der Faktoren abgesehen genau eine Zerle-
gung in Primzahlen:

= ··· N p 1 p n ,

wobei die Primzahlen p 1 ,..., p n nicht verschieden sein müssen. Um die Prim-
zahlen p 1 ,..., p n zu bestimmen, suchen wir nach einem nichttrivialen Teiler d
von N . Gegebenenfalls wird das Verfahren auf d und d erneut angewendet.
Wir beschränken uns stets darauf zu beschreiben, wie d gefunden werden kann.
Wir sagen dann, wir hätten eine Zerlegung für N gefunden oder N sei zerlegt