Quadratisches Sieb

Das Quadratische Sieb ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen.

Entstehungsgeschichte

Im 17. Jahrhundert entwickelte Pierre de Fermat die nach ihm benannte Faktorisierungsmethode von Fermat. Eine Verbesserung dieser Methode fand Maurice Kraitchik in den 20er Jahren des 20. Jahrhunderts, indem er neben der zu faktorisierenden Zahl auch deren Vielfache betrachtete; anderst ausgedrückt, indem er zu Kongruenzen überging.

Aus diesem Ansatz heraus entwickelte sich die Kettenbruchmethode, die 1970 mit der Faktorisierung der siebten Fermatzahl F₇ durch John Brillhart und Michael Morrison einen entscheidenden Durchbruch in der Geschichte der Faktorisierung erreichte. Dies gelang Brillhart und Morrison, indem sie eine Möglichkeit fanden, mit Hilfe der Linearen Algebra das Verfahren zu systematisieren.

Inspiriert durch das lineare Sieb von Richard Schroeppel konnte Carl Pomerance 1981 eine Beschleunigung des Verfahrens erreichen, indem er ein Siebverfahren an Stelle der bis dato benutzten Probedivision einführte. Durch diese Änderung war es möglich geworden, nunmehr Zahlen mit bis zu 100 Stellen zu faktorisieren.

Kurz darauf fanden Jim Davis und Diane Holdridge bzw. Peter Montgomery unabhängig voneinander eine Variante des Quadratischen Siebs mit mehrfachen Polynomen (genannt MPQS). Eine andere Verbesserung, das so genannte Spezielle Quadratische Sieb, stammt von M. Zhang, welches aber nur auf spezielle Zahlen angewandt werden kann.

1994 gelang es mit Hilfe des Quadratischen Siebs die berühmte 129-stellige Zahl RSA-129 zu faktorisieren.

Funktionsweise

Das Quadratische Sieb lässt sich grob in zwei Schritte aufteilen, den Siebschritt, bei dem Kongrenzen gesucht werden und dem Auswahlschritt, bei dem aus diesen Kongruenzen geeignete ausgewählt werden, mit denen sich die gesuchte Zerlegung finden lässt.

Siebschritt

Im Siebschritt werden Kongruenzen der Form

x² ≡ k (mod n)

gesucht, wobei die Primfaktorzerlegung von k bekannt ist und nur aus kleinen Primzahlen besteht. Hierfür wählt man für x Zahlen knapp über der Wurzel von n aus, reduziert deren Quadrat modulo n und berechnet für diese (vergleichsweise kleinen) Zahlen die Primfaktorzerlegung mittels (unvollständiger) Probedivision aus. Besteht die Primfaktorzerlegung nur aus kleinen Primzahlen, so hat man eine der gesuchten Kongruenzen gefunden.

Aus Geschwindigkeitsgründen ermittelt man zuerst mit Hilfe eines Siebverfahrens, ähnlich dem Sieb des Eratosthenes Zahlen, die nur kleine Primfaktoren besitzen, und führt die Probedivision nur bei diesen Zahlen durch.

Auswahlschritt

Hat man im Siebschritt genügend Kongruenzen gefunden, so kann man aus diesen ein lineares Gleichungssystem über dem endlichen Körper F₂ aufstellen. Aus einer Lösung dieses Gleichungssystems erhält man eine Auswahl der Kongruenzen, die, wenn sie alle miteinander multipliziert werden, gerade eine Kongruenz der Form

u² ≡ v² (mod n)

ergeben. Diese liefert durch Berechnung von ggT(u-v,n) einen Faktor von n, der in mindestens der Hälfte aller Fälle weder 1 noch n ist.

Beispiel

Gesucht ist die Primfaktorzerlegung von 1909. Im Siebschritt berechnet man der Reihe nach:

• 44² ≡ 3·3·3 (mod n)
• 45² ≡ 2·2·29 (mod n)
• 46² ≡ 3·3·23 (mod n)
• 47² ≡ 2·2·3·5·5 (mod n)

Fasst man die erste und die vierte Kongruenz zusammen, so erhält man:

(44·47)² ≡ 3·3·3·2·2·3·5·5 ≡ 90² (mod n)

und mit ggt(44·47-90,1909) = 23 einen Teiler von 1909 und damit die Primfaktorzerlegung 1909=23·83.

Einsatzbereich

Das Quadratische Sieb eignet sich für große Zahlen bis etwa 110 Stellen, die keine Primpotenz sind. Für größere Zahlen ist das Zahlkörpersieb besser geeignet.

Literatur

• Carl Pomerance: A Tale of Two Sieves, Notices of the AMS, 43 (1996) 1473-1485 (Webversion: http://www.ams.org/notices/199612/pomerance.pdf )