Wie man eine Zahl faktorisiert

Die Sicherheit des RSA-Kryptosystems basiert auf der Schwierigkeit, ganze Zahlen N zu faktorisieren, die das Produkt von zwei großen Primzahlen p und q sind. Wenn p und q gut gewählt sind, dann ist das Faktorisieren von N tatsächlich schwierig, aber es gibt auch Faktorisierungsmethoden, die bei bestimmten Arten von Zahlen sehr schnell arbeiten. Um die Sicherheit eines RSA-Systems zu gewährleisten, muss man sorgfältig ein N wählen, das nicht einer der schnelleren Methoden zum Opfer fällt. Wir werden zuerst die Pollard-Rho- und Pollard- p − 1 Methoden diskutieren. Diese werden nicht nur allgemein zur Faktorisierung verwendet, sondern wurden auch verallgemeinert, um in anderen Angriffen gegen kryptographische Systeme anwendbar zu sein. Danach gehen wir zu CFRAC über, einem Vorläufer der modernsten Faktorisierungsmethode, die das Hauptthema von Kap. 12 ist.