Das Zahlkörpersieb: Geschichte
Aus Wikibooks
[Bearbeiten] Die Geschichte des Zahlkörpersiebs
[Bearbeiten] Pierre de Fermat
Im Jahre 1643 schrieb Pierre de Fermat in einem Brief, dessen Empfänger nicht mehr ermittelt werden kann, vermutlich aber an Mersenne oder Frenicle, dass er ein neues Verfahren gefunden habe, um Zahlen zu faktorisieren.
Die Idee hinter Fermats Verfahren ist einfach: Man versucht die zu faktorisierende Zahl n als Differenz von zwei Quadratzahlen darzustellen. Mit Hilfe der dritten binomischen Formel erhält man daraus sofort eine Faktorisierung der Zahl n:
- n = x2 - y2 = (x - y)(x + y)
Um eine solche Darstellung zu finden, berechnete Fermat für x, beginnend bei 
, die Zahl Q(x): = x2 - n und überprüfte, ob es sich dabei um eine Quadratzahl handle. Hierfür verwendete er einige Tricks. So kannte er die quadratischen Reste modulo 100 auswendig, weswegen er sich bei der Berechnung auf die letzten beiden Ziffern beschränken konnte. Des Weiteren nutzte er aus, dass sich durch Q(x + 1) = x2 + 2x + 1 - n = Q(x) + 2x + 1 die jeweils nächste Zahl rein durch Additionen berechnen lässt.
[Bearbeiten] Maurice Kraitchik
Für fast dreieinhalb Jahrhunderte gab es keine nennenswerten Verbesserungen dieses Verfahrens, bis 1926 Maurice Kraitchik in einer Arbeit zwei neue Ideen vorstellte.
Zum einen lässt Kraitchik es zu, dass nicht n selber als Differenz von zwei Quadraten dargestellt wird, sondern auch Vielfache davon. Anders ausgedrückt betrachtet Kraitchik Kongruenzen der Form
.
Aus so einer Kongruenz erhält man einen Faktor von n, indem man ggT(x - y,n) berechnet (oder ggT(x + y,n)).
Beispiel: Hat man die Kongruenz 
, so erhält man ggT(106 - 17,3649) = 89 und damit einen Faktor. (Es ist 
)
Der Übergang zu den Kongruenzen hat aber den Nachteil, dass es auch passieren kann, dass man nur einen trivialen Teiler erhält. Es lässt sich aber beweisen, dass dies bei zufällig ausgewählten Kongruenzen nur in maximal der Hälfte aller Fälle passiert.
Beispiel: Die Kongruenz 
liefert den Faktor ggT(1826 - 1823,3649) = 1.
Die zweite Verbesserung von Kraitchik ist ein Verfahren zur Konstruktion dieser Kongruenz. Dabei nutzt Kraitchik aus, dass es sehr einfach ist, Kongruenzen der Form 
zu finden, nämlich einfach indem man die Gleichungen Q(x): = x2 - n, die bereits Fermat benutzt hat, umwandelt in 
. Hat man hinreichend viele dieser Kongruenzen, bei denen y sich leicht faktorisieren lässt, etwa durch Probedivision, so kann man geeignete dieser Kongruenzen so kombinieren, dass man eine gesuchte Kongruenz erhält.
Beispiel: Um 1909 zu faktorisieren berechnet man der Reihe nach, jeweils modulo 1909:
Die zweite und die dritte Kongruenz sind ungeeignet, da diese eine zu große Primzahl in der Faktorisierung enthalten. Aber aus der ersten und der letzten Kongruenz kann man eine gesuchte Kongruenz erhalten, indem man diese beiden multipliziert:
Und wie oben gesehen kann man daraus einen Teiler von 1909 bestimmen: 
