Diskussion:Kettenbruchmethode

Der erste und der letzte Absatz sind spitze so, aber der zweite (i. e. der relevante) ist völlig unverständlich. Wie genau sieht denn die Methode aus? --Scherben 20:54, 11. Okt 2005 (CEST)

Ich habe einen Quelle gefunden, wo die Methode beschrieben ist. http://christianroepke.de/studium/krypto2/Seminararbeit-Kettenbrueche.pdf

Vielleicht schreibt ja jemand eine Zusammenfassung für Wikipedia.

Franz Scheerer

Ich habe gerade festgestellt, dass unter dem angegebenen Link nichts mehr zu finden ist. Der Beitrag wurde wohl entfernt. Offenbar handelt es sich bei der Kettenbruchmethode im Prinzip auch um eine Variante der bereits 1926 von Maurice Kraitchik vorgeschlagenen Methode zur Faktorisierung, d.h. der Bestimmung der Primfaktorzerlegung großer ganzer Zahlen.

Das Prinzip

Zur Faktorisierung der Zahl n werden Zahlen x,y gesucht, so dass n Teiler von $x^{2}-y^{2}$ ist, da damit eine Faktorisierung der Form

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

angegeben werden kann, die in 50 % der Fälle echte Teiler von n als ggT(x+y,n) und ggT(x-y,n) liefern. Quadiert man verschiedene Zahlen und bildet den Rest der Division durch n, kann häufig durch geeignete Auswahl dieser Zahlen eine Quadratzahl gefunden werden, die das Produkt der Reste ist. Damit sind Zahlen mit der gesuchten Eigenschaft gefunden. Eine geeigente Auswahl kann mit Methoden der linearen Algebra aus der Primfaktorenzerlegung der Reste bestimmt werden.

Offenbar arbeiten praktisch alle Verfahren, die zur Faktorisierung großer Zahlen - 100 Stellen und mehr - nach diesem Grundprinzip.

Unklares im Abschnitt _Geschichte_

In dem Abschnitt über Fermats Faktorisierungsmethode steht einmal: x² - y² = N, darunter steht aber über die Verallgemeinerung des Fermatschen Verfahrens, dass die Summe von x² und y² nicht mehr gleich N zu sein braucht.

Ohne dass ich das Fermat-Verfahren nachgeschlagen habe, habe ich den Fehler bemerkt. Ich würde das korrigieren, falls keine Einwände kommen, und nachdem ich das Fermat-Verfahren nachgeschlagen habe :-) Captainsurak 21:42, 25. Jan. 2009 (CET)

Ich habe es korrigiert. -- Stefan Birkner 07:42, 26. Jan. 2009 (CET)

Denkfehler in Funktionsweise?

Es wird im Artikel meines Erachtens viel zu knapp erläutert, wie die Kettenbruchmethode funktionieren soll. Unter anderem ist da zu lesen, dass die generierten y Werte mit (y = p² - q² * N) mit hoher Wahrscheinlichkeit glatte Werte bezüglich der Faktorbasis sein sollen, weil sie angeblich relativ klein sind, da der rationale Bruch p/q ja eine beste Näherung für sqrt(n) sein soll.

Nur gibt es da leider folgendes inhaltliches Problem: Eine beste Näherung p/q ist um so besser, je größer der Zähler p und der Nenner q ist. Da p und q aber bei jeder weiteren Iteration für die beste Näherung quadratisch wachsen, haben p und q nach jeder neuen Iteration fast doppelt so viele Stellen wie vorher. Da es aber, egal wie gut die Approximation von sqrt(n) auch immer ist, zwischen einer Approximation von sqrt(n) und sqrt(n) selbst, immer eine gewisse Differenz d mit (d # 0) geben wird, ist also (y = p² - q² * n) nicht gleich 0 sondern gleich (q² * (2 * d * sqrt(n) + d²)). Weil aber das q wie bereits erwähnt sehr schnell wächst, ist ein Ausdruck der sogar noch q² als Faktor enthält, wohl niemals relativ klein und damit höchstwahrscheinlich auch kein glatter Wert bezüglich der Faktorbasis.

Zur besseren Veranschaulichung ein kleines Beispiel: Sei n ein "nur" 60 Bit langer Wert mit (n = 653.561.795.862.618.001). Dann ist sqrt(n) = 8,084316890514733...e+08.

Die folgende Tabelle zeigt nur die ersten vier Iterationen des in der Wikipedia erklärten Heron-Verfahrens, welches rationale Brüche p/q als gute Approximation zu sqrt(n) liefert. (Die beiden Initialwerte p₀ und q₀ sind nur äußerst grobe Schätzungen.)

i	p	q
0	536.870.912	1
1	941.792.172.014.329.745	1.073.741.824
2	1.640.477.944.306.951.389.874.470.170.941.780.001	2.022.483.289.215.176.349.067.509.760
3	5.364.522.319.086.298.768.076.536.718.626.890.580.243.066.383.451.417.841.609.159.678.375.617.601	6.635.678.457.373.747.854.676.366.272.315.686.316.583.306.625.087.669.781.680.619.520
4	57.555.882.104.862.648.235.954.212.381.695.563.512.498.146.306.635.397.650.016.765.063.218.287.538.595.345.339.867.595.965.900.081.571.813.663.715.557.857.725.214.648.397.921.952.022.773.225.601	71.194.490.373.723.222.734.626.206.800.096.156.771.475.117.819.440.094.558.004.615.733.277.866.490.823.661.623.530.730.304.570.251.418.620.045.144.805.179.487.437.565.224.592.343.040
...	...	...

Die (noch nicht einmal gute) Approximation p/q hat nach nur vier Iterationen folgenden Wert p/q = 808431689.0637597381236757847739989260102135342385448665552053712799597210921673958571931565661857155758457797....

Der zugehörige reguläre endliche Kettenbruch K hat folgenden Wert K = [808431689; 15, 1, 2, 6, 8, 5, 4, 15, 1, 1, 1, 5, 1, 1, 1, 16, 9, 3, 4, 4, 2, 3, 1, 11, 10, 1, 3, 1, 1, 1, 20, 3, 10, 4, 4, 6, 1, 3, 2, 1, 4, 10, 1, 8, 3, 1, 1, 7, 1, 1, 1, 1, 7, 5, 5, 1, 4, 1, 2, 5, 1, 14, 3, 1, 8, 1, 2, 1, 2, 1, 1, 8, 3, 1, 2, 38, 6, 1, 8, 4, 1, 4, 3, 133, 1, 1, 1, 1, 1, 1, 5, 1, 1, 3, 1, 2, 25, 1, 5, 1, 2, 1, 2, 1, 2, 1, 99, 5, 2, 1, 1, 1, 2, 2, 1, 11, 1, 3, 10, 2, 18, 1, 1, 27, 1, 1, 3, 2, 4, 11, 1, 18, 1, 9, 1, 1, 1, 3, 6, 1, 1, 11, 1, 533, 3, 1, 2, 6, 1, 37, 2, 1, 5, 3, 1, 3, 1, 3, 1, 5, 1, 18, 2, 1, 1, 4, 2, 4, 1, 2, 1, 1, 6, 1, 20, 1, 1, 10, 1, 5, 1, 1, 1, 1, 3, 1, 1, 1, 2, 16, 23, 1, 2, 2, 2, 1, 2, 1, 1, 1, 3, 8, 3, 1, 1, 9, 2, 4, 2, 2, 2, 2, 4, 1, 1, 1, 1, 1, 1, 3, 1, 4, 1, 4, 1, 10, 1, 3, 1, 1, 2, 1, 6, 1, 1, 17, 16, 1, 1, 1, 1, 2, 10, 1, 2, 2, 1, 5, 3, 3, 18, 7, 1, 1, 2, 1, 10, 1, 1, 3, 1, 2, 9, 1, 2, 13, 1, 7, 2, 1, 6, 21, 2, 1, 1, 2, 12, 1, 1, 59, 1, 4, 1, 22].

Die folgende Tabelle listet die y-Werte auf, die sich aus der i-ten Konvergenten des obigen regulären Kettenbruch ergeben.

i	y
1	-5.527.262.671
2	+4.564.142.369
3	-44.133.092.787
4	+1.763.942.681.477
5	-117.400.691.213.235
6	+3.080.686.779.096.712
7	-54.219.541.250.157.515
8	+12.590.201.701.906.381.357
9	-14.296.855.762.917.387.240
10	+53.719.895.388.397.379.679
...	...
284	+100.691.403.249.918.521.126.516.703.890.362.936.862.559.967.155.273.491.817.766.959.595.427.738.992.324.140.931.914.806.640.845.202.754.897.967.835.935.608.402.519.747.072.482.402.171.444.853.338.822.562.155.573.742.577.218.677.298.931.168.592.044.034.395.797.176.919.150.762.303.951.663.858.994.089.370.995.412.742.612.278.099.981.423.676.152.184.943.678.502.896.896.569.601

Und das sind bei mir keine betragsmäßig "relativ kleinen" Werte, denn schon abs(y₁) ist viel größer als sqrt(n) und abs(y₈) ist viel größer als n. Von y₂₈₄ ganz zu schweigen. Die y-Werte werden noch viel größer, wenn man bessere Approximationen p/q (durch mehr Iterationen des Heron-Verfahrens) für sqrt(n) verwendet, da p und q dann ja noch viel größer sind.

Kann mir nun jemand in meinen Überlegungen bzw. in meinem Beispiel einen Denkfehler nachweisen, oder gibt es tatsächlich einen Denkfehler in der im Artikel beschriebenen Funktionsweise? Wie kommt man also nun tatsächlich zu den betragsmäßig relativ kleinen y-Werten?

--Aragorn321 (Diskussion) 14:58, 7. Jul. 2013 (CEST)

Laut Maple stimmt deine Kettenbruchentwicklung nicht:

> N := 653561795862618001;
> numtheory:-cfrac(sqrt(N),20,'quotients');
       [808431689, 19, 2, 2, 1, 19, 3, 2, 18, 6, 1, 1, 1, 1, 27, 3, 1, 5, 8, 1, 9, ...]

Damit müssten dann die y-Werte deutlich kleiner sein. -- HilberTraum (Diskussion) 20:11, 7. Jul. 2013 (CEST)

Vielen Dank für die schnelle Reaktion und Sorry - der Denkfehler war, wie zu erwarten, wieder mal auf meiner Seite. Ich hatte in der Wikipedia (d.h. auch bei der Kettenbruchentwicklung !!!) keinen Algorithmus gefunden, der aus einer Quadratwurzel einen periodischen und regulären Kettenbruch macht. Also hatte ich versucht, unter Zeitdruck, selbst nachzudenken ...

Da ich zum einen das Heron-Verfahren kannte, welches einen rationalen Bruch der Form (p/q) als Approximation der Quadratwurzel liefert und es zum anderen (leider nur auf der englischen Web-Site zu den Kettenbrüchen) ein effizientes Verfahren gibt, wie man aus einem rationalen Bruch einen regulären aber endlichen Kettenbruch machen kann, dachte ich fälschlicherweise, diese beiden Verfahren einfach kombinieren zu können.

Nun ja, wenn die Approximation (p/q) wirklich gut ist, ist die Abweichung zur Quadratwurzel tatsächlich sehr klein und man kann eine kleinere Menge von y-Werten generieren, die bezüglich der Faktorbasis auch glatt sind. Aber weil die Approximation eben doch keinen periodischen und regulärer Kettenbruch repräsentiert, wird die Abweichung zur Quadratwurzel irgendwann so groß, dass die generierten y-Werte nicht mehr alternierende Vorzeichen haben, sondern nur noch positiv sind und dann natürlich größenmäßig regelrecht explodieren.

Nun habe ich mir doch die Mühe gemacht, einen ineinander verzahnten Algorithmus zu entwickeln und zu implementieren, der in jeder Runde sowohl den nächsten Wert des regulären und periodischen Kettenbruches als auch dessen Konvergente erzeugt. Damit bleiben alle bisher erzeugten y-Werte tatsächlich betragsmäßig klein und haben auch stets ein alternierendes Vorzeichen und die Größenexplosion bleibt auch aus.

Es wäre aus meiner Sicht äußerst nützlich, wenn man einen Link zu einem Algorithmus einbauen könnte, der aus einer Quadratwurzel einen regulären und periodischen Kettenbruch erzeugt. Dann kommt hoffentlich auch keiner mehr auf die Schnapsidee, nur mit einer Approximation der Quadratwurzel aus dem Heron-Verfahren zu arbeiten.

Wenn meine geistigen Irrungen auch nicht als pädagogisches Paradebeispiel für wie-man-es-besser-nicht-machen-sollte brauchbar sind, können sie selbstverständlich wieder von der Diskussionseite gelöscht werden. Vielen Dank!

--Aragorn321 (Diskussion) 19:37, 9. Jul. 2013 (CEST)

Schau mal hier en:Methods of computing square roots#Continued fraction expansion habe ich in der englischen Wikipedia einen Algorithmus zur Berechnung der Kettenbruchentwicklung von Quadratwurzeln gefunden. -- HilberTraum (Diskussion) 20:59, 9. Jul. 2013 (CEST)

Vielen Dank für den Link aus der Wikipedia! Ich hatte schon immer ein Problem damit, etwas (insbesondere im Internet) zu finden, wenn es nicht systematisch (also irgend einer inneren Ordnung folgend) aufgehoben ist. Dass auch andere den Artikel an dieser Stelle schon lange deplaziert finden, zeigt ja der Vorschlag vom Dezember 2011, diesen Artikelteil doch lieber zu den Kettenbrüchen zu verschieben.

Ich hatte zum Erzeugen von periodischen regulären Kettenbrüche etwas Brauchbares gefunden unter dem folgenden Link: http://matheplanet.com/default3.html?call=viewtopic.php?topic=105433&ref=http%3A%2F%2Fwww.google.de%2Furl%3Fsa%3Dt%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dweb%26cd%3D4%26ved%3D0CD8QFjAD Es ist interessant für mich, mit was sich heutzutage Schüler der 8ten bis 10ten Klassen alles beschäftigen. Kettenbrüche waren zu meiner Schulzeit und auch im Studium definitiv nicht im Lehrplan. Allerdings gab es zu meiner Zeit auch bei weitem nicht so viele funktionale Analphabeten, die Jahr für Jahr trotz 10jähriger Schulbildung in die Gesellschaft entlassen werden ...

Inzwischen habe ich ein anders Problem bei der Kettenbruchmethode festgestellt, welches sich aber vermutlich nicht so einfach lösen lassen wird, wie das letzte hausgemachte (siehe oben). Zwar bleiben hier im Gengensatz zur Dixon-Methode oder zum Quadratischen Sieb die generierten y-Werte alle schön klein, was auch die Wahrscheinlichkeit von glatten Zahlen auf Dauer schön stabil hält, aber der Zähler p_i und der Nenner q_i der i-ten Konvergenten des schrittweise erzeugten Kettenbruches zur Wurzel von N wachsen ungefähr mit dem Faktor sqrt(2) zur Anzahl der generierten y-Werte (also: i * sqrt(2)). Nach (i = 50.000) generierten y-Werten haben p_i und q_i eine Länge von ca. 75.000 Bit. Zur Erzeugung der y-Werte werden davon aber auch noch die Quadrate p_i² und q_i² benötigt, die ja dann auch die doppelte Bitlänge haben. Numerische Rechenoperationen, insbesondere mehrere Multiplikationen mit derart langen Zahlen für jeden zu generierenden y-Wert kosten natürlich viel Zeit.

Bisher habe ich als teilweise Kompensation des geschilderten neuen Problems nur die Vergrößerung der Smoothness-Bound S um die Faktoren 2, 4, 8, 16, ... gefunden, was zwar zu einer deutlich höheren Wahrscheinlichkeit von glatten Zahlen bezüglich der Faktorbasis aber natürlich auch zu einer entsprechenden Vergrößerung der Faktorbasis führt. Aber das Letztere ist nicht so schlimm, wie es sich anhört, wenn man die beiden Phasen des Verfahrens, die Datensammelphase und die Datenverarbeitungsphase nicht separat nacheinander abarbeitet, sondern miteinander verzahnt, so dass jede gefundene glatte Kongruenz auch sofort verarbeitet wird. Dann kommt man teilweise schon zu nichttrivialen Teilern der zu faktorisierenden Zahl N wenn die quadratischen Binärmarix M, deren Dimension in diesem Fall ja der Größe der Faktorbasis exakt entspricht, erst zu 20% oder 25% gefüllt ist. Das heißt, man spart manchmal ca. 80% bis 90% der Zeit ein, die benötigt werden würde, wenn man die rechteckige Binärmatrix M zuerst komplett füllt, bevor man sie verarbeitet und nach nichtrivialen Teilern der zu faktorisierenden Zahl N sucht.

Gibt es für die Kettenbruchmethode evtl. noch andere brauchbare Optimierungsmöglichkeiten? Die Nutzung von "großen" Primzahlen P außerhalb der Faktorbasis und die GCD-Methode zum effektiveren Herausfiltern der glatten y-Werte (mit maximal einem primen CoFaktor P <= S²), die Vergrößerung der Faktorbasis, sowie die Verzahnung von Datensammelphase und Datenverarbeitungsphase sind schon implementiert. Trotzdem sind zusammengesetzte Zahlen im 128-Bitbereich manchmal schon eine "recht harte Nuss" für die Kettenbruchmethode ...

--Aragorn321 (Diskussion) 12:56, 10. Jul. 2013 (CEST)

So richtig kenne ich das Verfahren auch nicht, aber ich denke der "Haupttrick" ist, dass man alles modulo N rechnen kann, das heißt größere Zahlen als N sollten während des ganzen Algorithmus gar nicht auftauchen. Für weitere Tricks und wie man die Faktorbasis geschickt wählt usw. müsste man wohl mal die Literatur dazu durchforsten. -- HilberTraum (Diskussion) 19:51, 10. Jul. 2013 (CEST)

Leider habe ich auch nach dem Durchlesen von im Internet umherschwirrender Literatur über die Kettenbruchmethode bisher keinen Hinweis darauf gefunden, dass wirklich alle Zahlen modulo N gerechnet werden können. Im Gegenteil, das Verfahren basiert offensichtlich auf der "unendlichen" Entwicklung von immer besseren Approximationen zur Wurzel(N) in Form von besten Näherungsbrüchen (p/q). Da aber (auch laut Wikipedia) beste Näherungsbrüche nur dann noch besser werden können, wenn man den Nenner q (und damit natürlich auch den Zähler p) größer macht, wachsen p und q zwangsweise in jeder Iteration. Würde man "normale" Software benutzen, wäre das auch nicht ganz so schlimm, weil es ja nun schon seit über 40 Jahren Integermultiplikationsalgorithmen mit einer fast linearen Laufzeitkomplexität gibt. In Java 7.0 wird aber (für den Datentyp BigInteger) immer noch ein Integermultiplikationsalgorithmus mit einer quadratischen Laufzeitkomplexität verwendet, der schon nachweislich bei den alten Ägyptern bekannt war. Frei nach dem Motto - Schlimmer geht's nimmer! Das hätte ich wirklich nicht erwartet, obwohl ich es eigentlich hätte besser wissen müssen. Das ist jedenfalls der (vermeidbare) Grund für die von mir festgestellte Laufzeitexplosion in der Kettenbruchmethode. Offensichtlich kommt man wesentlich besser, wenn man die gesamte von Java angebotene Klasse BigInteger ignoriert und durch eine selbst implementierte Klasse (mit schnelleren Algorithmen) ersetzt. Aber solange man mit der vermutlich langsamsten Software der Welt noch die Herstellung und den Verkauf von immer schnelleren und noch größeren Rechnerarchitekturen voranpeitschen kann, ist ja die Welt noch völlig in Ordnung ... --Aragorn321 (Diskussion) 20:02, 16. Jul. 2013 (CEST)

Das Rechnen modulo N sollte meiner Ansicht nach schon klappen. Die Näherungsbrüche selbst braucht man ja gar nicht und am Schluss wird sowieso modulo N genommen, weil ja der ggT mit N bestimmt wird. Probier's doch einfach mal aus, dann siehst du's ja. Ein Faktorisierungsverfahren für N, das wesentlich größere Zahlen als N selbst verwendet, würde ja irgendwie nicht so viel Sinn machen. -- HilberTraum (Diskussion) 07:54, 17. Jul. 2013 (CEST)

Schau mal hier, in dem Paper wird eine Implementierung genauer beschrieben. Hilft dir das weiter? -- HilberTraum (Diskussion) 08:25, 17. Jul. 2013 (CEST)

Vielen Dank für den Link! Sah sich beim Durchlesen alles sehr interessant an. Leider hatte er mir aber beim Implementieren - wegen eigener Inkompetenz - nicht viel geholfen. Zwei mal habe ich komplett von vorn angefangen, diese Kettenbruchvariante zu implementieren und stieß jedesmal auf das gleiche neue Problem. Zwar sind die generierten x und y Werte, wie vorhergesagt, alle tatsächlich schön klein, dafür wurden aber schon nach kurzer Zeit scheinbar immer die gleichen x und y Werte und somit auch die gleichen Kongruenzen produziert. Ab einem gewissen Punkt wurden also nur noch nichttriviale Teiler, aber keine einzige neue Kongruenz mehr gefunden. Nicht einmal eine einzige Fastprimzahl mit 2x32 Bit Länge konnte ich so faktorisieren. Also suchte ich erneut im Internet und wurde fündig bei dem Link: Kryptologie: Algebraische Methoden und Algorithmen. Die dortige Herangehensweise ist zwar sehr ähnlich, wie die von dem empfohlenen Link, der mir nicht weitergeholfen hatte, aber ich habe es - warum auch immer - problemlos auf Anhieb implementiert bekommen.

Jetzt habe ich ein neues Problem, diesmal aber ein durchweg Positives, welches ich mir bisher noch nicht richtig erklären kann. Die von mir implementierte Variante der Kettenbruchmethode mit einer angeblichen Laufzeitkomplexität von L[1/2, 1*sqrt(2)] ist rein messtechnisch (also praktisch) gesehen, asysmptotisch deutlich besser als das Quadratische Sieb mit einer theoretisch besseren Laufzeitkomplexiztät von L[1/2, 1], welches wiederum asymptotisch besser ist als der einfache Dixon-Algorithmus mit einer Laufzeitkomplexität von L[1/2, 2*sqrt(2)]. Letzteres stimmt ja auch mit der Theorie überein, aber Ersteres definitiv nicht! Aber was kann ich dafür, wenn bei der Kettenbruchmetode die y-Werte, welche auf Glattheit bzgl. der Faktorbasis zu testen sind, vom Betrag her gesehen sich ausschließlich im Bereich [0 ... 2*sqrt(n)] bewegen, während die auf Glattheit zu testenden y-Werte beim Quadratischen Sieb vom Betrag her gesehen fast ausschließlich im Bereich von [sqrt(n) ... n] liegen. So ist die Wahrscheinlichkeit bei 2x32 Bit langen Fastprimzahlen glatte y-Werte zu finden, bei der Kettenbruchmetzhode ca. 50 mal größer. Selbst bei einer um Faktor 4 reduzierten Faktorbasis werden bei der Kettenbruchmethode im Vergleich zum Quadratischen Sieb noch ca. 30 mal soviele Kongruenzen gefunden. Allerdings ist der Rechenaufwand für jeden der generierten y-Werte bei der Kettenbruchmethode sowohl bei dessen Erzeugung als auch bei der Überprüfung auf Glattheit deutlich höher als beim Quadratischen Sieb, was das von mir beobachtete Laufzeitverhalten um so bemerkenswerter macht. Je länger die zu faktorisierenden Fastprimzahlen sind, desto stärker tritt dieser Unterschied auf und desto größer ist auch die Laufzeitdifferenz. Liegt diese bei 2x32 Bit langen Fastprimzahlen nur bei ca. Faktor 6, steigt diese bei 2x64 Bit langen Fastprimzahlen auf ca. Faktor 50 an. Dabei verbraucht meine Implementierung der Kettenbruchmethode weniger als 20% des Speichers, den das Quadratischen Sieb benötigt. So macht das Programmieren ja richtig Spaß!

Zur besseren Veranschaulichung gibt die folgende Tabelle eine Übersicht der bisher von mir ermittelten durchnittlichen Laufzeiten. Es wurden dabei jedesmals die gleichen (K = 16) zufällig generierten Fastprimzahlen faktorisiert, pro Algorithmus die gesamte benötigte Laufzeit in Sekunden gemessen und dann die durchschnittliche Laufzeit in Sekunden berechnet. Es wurden alle Implementationen in Java SE 7.0 gemacht und auf einem 2-GHZ-64Bit Multikernprozessor ausgeführt. Multithreading wurde aber beim Rechnen explizit nicht verwendet, obwohl der asymmetrisch laufende Garbage-Collector laut Lastverteilung meist von einen anderen Prozessorkern ausgeführt wird. Sowohl bei dem Dixon-Algorithmus als auch beim Quadratischen Sieb habe ich mit einer vergrößerten Faktorbasis (SmoothnessBoundFactor = 2.0) bei der Kettenbruchmethode dagegen mit einer verkleinerten Faktorbasis (SmoothnessBoundFactor = 0.35) gearbeitet, um für jeden der drei verschiedenen Faktorisierungsalgorithmen möglichst optimale Laufzeiten zu bekommen.

Länge der Fastprimzahl in Bit	Laufzeit Dixon-Algorithmus in Sekunden	Laufzeit Quadratisches Sieb in Sekunden	Laufzeit Kettenbruchmethode in Sekunden
2x32	3,013e-01	1,267e-01	2,077e-02
2x36	7,968e-01	3,169e-01	4,306e-02
2x40	3,749e+00	1,325e+00	1,112e-01
2x44	8,390e+00	2,803e+00	1,736e-01
2x48	3,073e+01	9,819e+00	4,553e-01
2x52	7,147e+01	2,222e+01	8,947e-01
2x56	2,628e+02	7,673e+01	2,545e+00
2x60	9,849e+02	2,743e+02	7,564e+00
2x64	...	ca. 800	1,592e+01

--Aragorn321 (Diskussion) 13:53, 6. Aug. 2013 (CEST)

Hm, kann ich leider nicht viel dazu sagen, weil ich mich da auch nicht genauer auskenne. Bist du denn sicher, dass dein Quadratischer-Sieb-Algorithmus korrekt implementiert ist? -- HilberTraum (Diskussion) 21:24, 8. Aug. 2013 (CEST)

Diskussionswunsch: "Kettenbruchmethode" vs. "Kettenbruchverfahren"

Kettenbruchmethode ist eine mmN --Traugott (Diskussion) 18:10, 14. Jun. 2020 (CEST) un-passende Übersetzung des englischen continued fraction method.