Quadratisches Sieb

Das Quadratische Sieb ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer ganzer Zahlen. Mittels der Faktorisierung können alle zusammengesetzen Zahlen eindeutig als Produkt von Primzahlen geschrieben werden. Alle ganzen Zahlen größer als eins sind entweder selbst Primzahlen oder können als das Produkt von Primzahlen dargestellt werden.

Entstehungsgeschichte

Die wesentlichen Grundlagen des Verfahrens gehen auf Pierre de Fermat (1607 bis 1665) zurück. In einer Veröffentlichung von 1926 wurden wesentliche Verbesserungen des Fermatschen Verfahrens durch Maurice Kraitchik eingeführt. Das Verfahren, wie es hier dargestellt wird, entspricht weitgehend der Idee von Kraitchik.

In einigen Details wurden Verbesserungen von John Brillhart und Michael Morrison, Richard Schroeppel und 1981 durch Carl Pomerance vorgeschlagen. 1994 gelang es, mit Hilfe des Quadratischen Siebs die berühmte 129-stellige Zahl RSA-129 zu faktorisieren.

Mehr zur Geschichte des Quadratischen Siebs findet sich im Artikel Geschichte der Faktorisierungsverfahren.

Grundlegendes Prinzip

Gesucht ist eine Zerlegung einer natürlichen Zahl $n$ in Ihre Primfaktoren. Die Idee des Quadratischen Siebs besteht darin, Zahlen $x$ und $y$ zu finden, so dass sich ihre Quadrate nur um ein Vielfaches von n unterscheiden. In der Zahlentheorie kann dieser Sachverhalt als Kongruenz $x^{2}\equiv y^{2}{\pmod {n}}$ beschrieben werden.

Falls es gelingt solche Zahlen x und y zu finden kann, kann damit oft auch echte Teiler von n bestimmen. Denn es gilt

$x^{2}-y^{2}=k\cdot n=(x+y)\cdot (x-y)$

mit einer ganzen Zahl k. Falls die Primfaktoren p und q Teiler von n sind, ist auch einer der Faktoren auf der rechten Seite der Gleichung ein Vielfaches der Primzahl p bzw. der Primzahl q. In etwa 50 % der Fälle werden die beiden Primfaktoren p,q nicht beide im gleichen Faktor enthalten sein. In diesem Fall liefern die größten gemeinsamen Teiler ggT($x+y,n$) und der ggT($x-y,n$) Vielfache der beiden Faktoren p und q, die echte Teiler von n sind. Falls die Zerlegung von n nur aus den beiden Faktoren besteht, hat man die Primfaktorenzerlegung bereits gefunden. Ist dies nicht der Fall, können die gefundenen Teiler von n erneut in Faktoren zerlegt werden.

Mit dem Quadratischen Sieb versucht man nun, möglichst effizient solche Werte x und y zu finden, um letztlich echte Teiler von n angeben zu können. Der Algorithmus lässt sich dabei in zwei Schritte aufteilen, den Siebschritt, bei dem Quadratische Reste berechnet und in ihre Primfaktoren zerlegt werden, und dem Auswahlschritt, bei dem aus diesen Zerlegungen geeignete ausgewählt werden, mit denen sich die gesuchte Zerlegung finden lässt.

Berechnung Quadratischer Reste

Zur Bestimmung eines echten Teilers von n, werden zunächst Zahlen qr, die Reste der Divison durch n, verschiedenener Quadratzahlen

$qr=x^{2}\mod n$

berechnet. Zu diesem Zweck werden Zahlen x mit $x^{2}$ größer n ausgewählt. Derartige Zahlen qr werden als Quadratischer Reste modulo n bezeichnet. In einigen Fällen kann die Primfaktorzerlegung von der Quadratischen Reste relativ leicht gefunden werden. Dies ist dann der Fall, wenn nur kleine Primzahlen Teiler von qr sind. In der Zahlentheorie werden solche Zahlen als glatte Zahlen bezeichnet. Exakter ausgedrückt ist der qr bezüglich einer festen Schranke glatt, wenn alle Primzahlen in der Faktorisierung von qr nicht größer als diese Schranke sind. Die Berechung ist auch für große Zahlen effizient. Die Werte für x können fortlaufend

$x,x+1,x+2,...$

knapp über der Wurzel von n auswählt werden. Mittels der Probedivision kann die Primfaktorenzerlegung für glatte Zahlen berechnet werden. Besteht die Primfaktorzerlegung nur aus geraden Potenzen der Primfaktoren, so hat man mit der Wurzel aus qr bereits eine Zahl y mit der gewünschten Eigenschaft

$(x-y)\cdot (x+y)=k\cdot n$

gefunden. Ist dies nicht der Fall, können durch Multiplikation verschiedener Quadratischer Reste solche Zahlen konstruiert werden.

Zur Beschleunigung des Verfahrens können die Primzahlen bis zu einer Schranke für die Probedivision vorab mittelts eines Algorithmus, ähnlich dem Sieb des Eratosthenes, berechnet werden.

Zahlenbeispiel

Gesucht sei die Primfaktorzerlegung der Zahl 1909. Die Quadratwurzel aus 1909 ist ungefähr 43,7. Wir berechnen die Quadratischen Reste daher für x= 44, 45, 46 und 47 und bestimmen die Primfaktorzerlegung dieser glatten Zahlen z.B. durch Probedivision.

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

Gesucht ist nun eine Quadratzahl, die sich als Produkt dieser Zahlen darstellen lässt. Eine Zahl ist dann eine Quadratzahl, wenn jede Primzahl nicht oder mit einem geraden Exponenten in der Zerlegung auftritt. Wir betrachten daher nur die Primfaktoren mit ungeraden Exponenten. Die Multiplikation zwei Zahlen ist auf die Addition der Exponenten zurüchzuführen. In diesem Beispiel ist leicht zu erkennen, dass durch Multiplikation der ersten und der vierten Zerlegung nur noch gerade Exponenten auftreten.

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

und mit ggT(44·47-90,1909) = 23 einen Teiler von 1909 und damit die Zerlegung 1909=23·83. Da sowohl 23 als auch 83 Primzahlen sind, ist gleichzeitig auch schon die Primfaktorzerlegung gefunden.

Anwendung auf große Zahlen

Im vorherigen Zahlenbeispiel konnten wir ohne Schwierigkeiten für alle berechneten Quadratischen Reste die Primfaktorenzerlegung finden und bereits nach der Berechnung von vier Zerlegungen eine Quadratzahl konstruieren. Insbesondere bei größeren Zahlen sind nicht alle Quadratischen Reste glatt und eventell viele Zerlegungen notwendig, um eine Quadratzahl konstruieren zu können. Falls ein Quadratischer Rest nicht glatt ist, wird er nicht weiter berücksichtigt.

Es ist lediglich notwendig festzustellen, welche Primfaktoren in der Zerlegung einen ungeraden Exponenten haben, um eine Quadratzahl ermitteln zu können. Für jede der Primzahlen kleiner oder gleich einer Schranke S kann eine 1 bei einem ungeraden Exponenten und sonst eine 0 notiert werden. Für jede Zerlegung entsteht so ein Spaltenvektor mit den Werten 0 und 1. Die Länge dieses Vektors ist durch die Anzahl der Primzahlen gegeben.

Falls eine Primzahl nicht bzw. nur mit geraden Exponenten in den verschiedenen Zerlegungen der Quadratischen Reste auftritt, braucht die Primzahl nicht berüchsichtigt werden.

Die Suche nach Faktoren, die eine Quadratzahl ergeben ist damit auf die Lösung eines homogenen linearen Gleichungssystems über dem endlichen Körper F₂ zurückzuführen. Die rechte Seite des Gleichungssytems ist der Nullvektor, da eine Quadratzahl gesucht ist, die nur gerade Exponenten, entsprechend der 0, aufweist. Jede Primzahl entspricht einer linearen Gleichungen. Die Lösung gibt die Zerlegungen an, die multiplziert werden, um eine Quadratzahl zu erhalten. Die 1 bedeutet, dass der Quadratische Rest multipliziert wird und die 0 bedeutet, dass die Zerlegung nicht berücksichtigt wird. Eine Quadratzahl entspricht einer nicht trivialen Lösung, da das Produkt mindestens eine der Zerlegungen enthalten muss.

Zur Lösung des Gleichungsystems können Verfahren der Linearen Algebra angewendet werden.

Wahl der Schranke

Eine Zerlegung kann dann gefunden werden, falls genügend glatte Quadratische Reste bezüglich einer Schranke S gefunden werden können. Da die Berechnung der Quadratischen Reste und die Probedivision durch die Primzahlen kleiner S effizient ist, kann eine große Zahl Quadratischer Reste faktoriesiert werden, sofern glatte Zahlen nicht zu selten auftreten. Es genügt jedoch, wenn z.B. nur einer von etwa 10.000 Resten, glatt bezüglich einer Schranke ist. Dies ist der Fall, falls die Schranke S hinreichend groß gewählt wird.

Die praktisch mögliche Größe der Schranke S ist jedoch durch die Kapazität der eingesetzen Hardware und Software begrenzt.

Dynamische Faktorbasis

Das Verfahren wird wesentlich durch die Speicherkapazität für eine hinreichend große Faktorbasis, den Primzahlen kleiner oder gleich S begrenzt. Es ist jedoch nicht notwendig alle Primzahlen bis zu einer Schranke S zu speichern. Wir haben uns bereits überlegt, dass Primfaktoren, die in keiner Zerlegung mit einem ungeraden Exponenten auftreten, nicht berücksichtigt werden brauchen.

Es ist daher sinnvoll zunächst nur die Primzahlen bis zu einer relativ kleinen Schranke, z.B. 1000, zu berechnen. Im Laufe der Berechnung können weitere Primfaktoren aufgenommen werden. Es ist dabei nur erforderlich, die Faktoren unterhalb einer größeren Schranke S2 mit ungeradem Exponenten zu berücksichtigen.

Die Berechnung der Zerlegungen wird jedoch zeitaufwendig, falls die Schranke S2 sehr groß gewählt wird. Es ist jedoch nicht notwendig, dass die Faktorbasis nur Primzahlen enthält. Daher genügt es eine Probedivision für alle Faktoren in der Faktorbasis vorzunehmen.

Jetzt wird es jedoch zeitaufwendig für alle Faktoren eine Probedivision durchzuführen, falls sehr viele Faktoren in die Basis aufgenommen werden. Dabei ist es aber hilfreich, dass die meisten zusammengesetzen Zahlen bereits relativ kleine Teiler haben. Falls keine "kleinen" Teiler gefunden werden können, handelt es sich mit höherer Wahrscheinlichkeit, um eine Primzahl. Es gibt effiziente Tests, die es erlauben für solche Kandidaten zu prüfen, ob es sich tatsächlich um Primzahlen handelt. Ist dies der Fall, kann die Probedivision abgebrochen werden.

Falls nach Division durch die Primzahlen aus der Faktorbasis noch ein Faktor verbleibt, kann geprüft werden, ob es sich bei diesem Faktor um eine Quadratzahl handelt. Da eine Quadratzahl nur gerade Exponenten in der Zerlegung aufweist, braucht dieser Faktor nicht in die Faktorbasis aufgenommen werden.

Faktorisierung einer 200 stelligen Zahl

Wir nehmen an die eine 200-stellige Zahl n, wie RSA-200, sei das Produkt zweier unbekannter Primzahlen p und q mit etwa 100 Stellen.

$n=p\cdot q$

Wir starten mit einer Faktorbasis der Primzahlen kleiner 1000, die wir dynamisch erweitern. Die berechneten Quadratischen Reste haben ca. 100 Stellen. Die Wahrscheinlichkeit, dass ein Quadratischer Rest eine Primzahl ist, beträgt nur etwa 1/230.

Dies Wahrscheinlichkeit ist näherungsweise durch

$P={\frac {1}{ln(n)}}$

gegeben. Dabei ist ln(n), der natürliche Logarithmus etwa 2,3 mal der Anzahl der Stellen. Falls der Quadratischer Rest keine Primzahl ist, kann er folglich als Produkt zweier Faktoren geschrieben werden. Diese Faktoren zerfallen jeweils mit einer Wahrscheinlichkeit von etwa 114/115 in weitere Faktoren. Falls sich eine glatte Zahl ergeben soll, müssen beide Faktoren teilbar sein. Die Wahrscheinlichkeit dafür beträgt etwa 113/115.

In einem vereinfachten Modell, gehen wir davon aus, dass mit der Wahrscheinlichkeit

$P={\frac {1}{ln(n)}}\approx {\frac {1}{2,3\cdot Dezmalstellen}}$

eine Zahl in etwa gleich große Teiler geteilt werden kann, d.h. in Teiler mit der halben Anzahl an Stellen.

Nach 4 solchen Teilungsschritten ergeben sich 16 Teiler, die nur je ein 1/16 der Stellen haben. Diese Zahlen sind glatt bezüglich einer Schranke von etwa 10 Millionen. Die Wahrscheinlichkeit, dass alle 8 etwa 15-stelligen Zahlen aus denen die 16 glatten Faktoren hervorgegangen sind, tatsächlich teilbar sind ergibt sich in unserem Modell zu.

$P=\left(1-{\frac {1}{ln(10^{14})}}\right)^{8}\approx 0,77$

Diese heuristische Betrachtung führt zu dem Ergebnis, dass mit einer nicht zu vernachlässigen Wahrscheinlichkeit, glatte Zahlen mit etwas 8-stelligen Faktoren gefunden werden könnten.

Es erscheint daher durchaus denkbar eine 200-stellige Zahl mit diesem Verfahren zu faktorisieren.

Für eine 10.000-stellige Zahl ist dies jedoch ohne eine grundlegend neue Idee für ein Faktorisierungsverfahren weitgehend ausgeschlossen. Seit 1926 sind jedoch offenbar keine grundlegend neuen Ideen veröffentlicht worden.

Berechnung kleiner Quadratischer Reste

Grundsätzlich können zunächst einmal beliebige Zahlen mit

$x^{2}>{\sqrt {n}}$

zur Berechnung der Quadratischen Reste benutzt werden. Falls die daraus resultierenden Quadratischen Reste

$x^{2}\mod n$

jedoch sehr große Zahlen sind, ist die Wahrscheinlichkeit geeignete Zerlegungen zu finden gering. Es ist daher naheliegend das kleinste $x_{1}$ mit

${x_{1}}^{2}>{\sqrt {n}}$

zu verwenden und anschließend zu den Zahlen

$x_{1}+1,x_{1}+2,x_{1}+3,x_{1}+4,...$

überzugehen. Wegen der Rekursionsbeziehung

$(x+1)^{2}=x^{2}+(2x+1)\approx x^{2}+2{\sqrt {n}}$

werden diese Zahlen bei großem n jedoch rasch erheblich größer. Daher ist es zumindest nach der Berechnung einer größeren Anzahl solcher Reste, sinnvoll einen neuen Startwert für die Folge zu verwenden.

Dazu kann das kleinste $x_{k}$ mit

$x_{k}^{2}>k\cdot n$

verwendet werden. Bei k > 1 können auch die Werte

$x_{k}-1,x_{k}-2,x_{1}-3,x_{k}-4,...$

verwendet werden. In diesem Fall sind die Quadratischen Reste jedoch nicht besonders klein.

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 )
• Richard Crandall, Carl Pomerance: Prime Numbers, A Computational Perspective, Springer, 2001, ISBN 0-387-94777-9

Weblinks

• http://www.thorstenreinecke.de/qsieve/ - Eine Implementierung des Quadratischen Siebs unter GPL