Ab welchem N ist ein Quadratisches Sieb sinnvoll?
-
Hallo,
ich hab mich in letzter Zeit ein bisschen mit dem Quadratischen Sieb auseinandergesetzt und ich glaube, dass ich es mittlerweile auch so einigermaßen verstanden hab. Ursprünglich hatte ich vor, Primfaktoren noch schneller berechnen zu können. Ich hab aber festgestellt, dass das Sieb doch recht aufwendig ist und folglich für die Zerlegung kleiner Zahlen wohl nicht geeignet ist (N < 1.000.000). Vor allem auch deshalb weil ich alle Primzahlen bis 1Mio gut im Speicher halten kann und dann einfach über Brute-Force eine Zahl durch alle kleineren Primzahlen teilen kann.
Ist es korrekt, dass das Quadratische Sieb hier wohl keine Verbesserungen in der Laufzeit bringen wird? Und wenn ja, gibt es Möglichkeiten wie ich die einfache Brute-Force Methode (N durch alle kleineren Primzahlen teilen) in diesem keinen Zahlenbereich noch weiter verbessern könnte?
-
Primzahlen bis 1 Million? Da würde doch sogar ein Lookup-Table gehen.
-
Ein bisschen wikipedia und google fördern dazu genug Treffer, um dich für die nächsten Jahre zu beschäftigen, z.b. http://de.wikipedia.org/wiki/Zahlkörpersieb
http://www.cdc.informatik.tu-darmstadt.de/~samoa/NFS.pdf
-
Antoras schrieb:
ich hab mich in letzter Zeit ein bisschen mit dem Quadratischen Sieb auseinandergesetzt und ich glaube, dass ich es mittlerweile auch so einigermaßen verstanden hab. Ursprünglich hatte ich vor, Primfaktoren noch schneller berechnen zu können. Ich hab aber festgestellt, dass das Sieb doch recht aufwendig ist und folglich für die Zerlegung kleiner Zahlen wohl nicht geeignet ist (N < 1.000.000).
bei N<1000000 hast Du als Kandidaten nur die Zahlen von 2 bis 1000. Nur 1000 Divisionen. Da wirft man noch kein großes Sieb an.
Antoras schrieb:
Vor allem auch deshalb weil ich alle Primzahlen bis 1Mio gut im Speicher halten kann und dann einfach über Brute-Force eine Zahl durch alle kleineren Primzahlen teilen kann.
Also nur noch 168 Divisionen. Oder mit einem 30-er wheel aber ohne alle Primzahlen immernoch nur 266 Divisionen.
Antoras schrieb:
Ist es korrekt, dass das Quadratische Sieb hier wohl keine Verbesserungen in der Laufzeit bringen wird?
Sehe ich auch so.
Antoras schrieb:
Und wenn ja, gibt es Möglichkeiten wie ich die einfache Brute-Force Methode (N durch alle kleineren Primzahlen teilen) in diesem keinen Zahlenbereich noch weiter verbessern könnte?
Die möglichen Teiler bis 31 (selber messen) hardcoded testen (nicht im Array ablegen). Zahlen >=1369 auf Primalität mit einem SPRP-Test prüfen, zwei Basen genügen wohl schon (selber suchen). Die übrigen Zahlen von Pollard's Rho knacken lassen in der Variante von Brent.
-
SeppJ schrieb:
Primzahlen bis 1 Million? Da würde doch sogar ein Lookup-Table gehen.
Das stimmt, aber bis die geladen ist vergeht auch seine Zeit. Außerdem bin ich auch der Suche nach einem Algo, der aus dem Stand heraus Primzahlen suchen kann.
Mups schrieb:
[...]Zahlkörpersieb
Das ist ja noch komplexer als das Quadratische Sieb und soll wohl erst ab Zahlen mit mehr als 100 Stellen effizienter sein.
volkard schrieb:
bei N<1000000 hast Du als Kandidaten nur die Zahlen von 2 bis 1000. Nur 1000 Divisionen.
Wie kommt man da drauf, dass in diesem Zahlenbereich keine größeren Primzahlen eine Rolle spielen? Kann man das berechnen?
volkard schrieb:
Die möglichen Teiler bis 31 (selber messen) hardcoded testen (nicht im Array ablegen).
Was meinst du damit? Wenn sie in dem Array mit Primzahlen liegen sind sie doch hardcodiert. Die ändern sich ja schließlich nicht.
volkard schrieb:
Zahlen >=1369 auf Primalität mit einem SPRP-Test prüfen, zwei Basen genügen wohl schon (selber suchen). Die übrigen Zahlen von Pollard's Rho knacken lassen in der Variante von Brent.
Super! Das guck ich mir mal an.
-
Antoras schrieb:
volkard schrieb:
bei N<1000000 hast Du als Kandidaten nur die Zahlen von 2 bis 1000. Nur 1000 Divisionen.
Wie kommt man da drauf, dass in diesem Zahlenbereich keine größeren Primzahlen eine Rolle spielen? Kann man das berechnen?
Ja. Sei N eine große zu untersuchende Zahl. Und sei t ein Teiler. Dann ist auch N/t ein Teiler.
Wir wissen, sqrt(N)sqrt(N) = N.
Und t * N/t = N.
Wenn t größer als sqrt(N) ist, dann muß N/t kleiner als sqrt(N) sein.
Deswegen reicht es, alle Teiler von 2 bis sqrt(N) zu testen, zu jedem gefunden Teiler gibt es den Gegenteiler N/t, der größer als sqrt(N) ist. Sozusagen die eine Hälfte der Teiler ist kleiner sqrt(N) und die andere Hälfte ist größer sqrt(N).
Beispiel:
100=250
100=425
100=520
100=1010
100=205
100=254
100=502
Es reicht, bei N<=1000 alle Teiler von 2 bis 10 zu testen, jeder Teiler über 10 hätte einen passenden Gegenteiler, der unter 10 liegt.Und so reicht es auch, bei N<=1000000 alle Teiler von 2 bis 1000 zu testen.
Darüberhinaus reicht es sogar, nur die Teiler zu testen, die Primzahlen sind. Und unter 1000 gibt's nur 168 Primzahlen.
Antoras schrieb:
volkard schrieb:
Die möglichen Teiler bis 31 (selber messen) hardcoded testen (nicht im Array ablegen).
Was meinst du damit? Wenn sie in dem Array mit Primzahlen liegen sind sie doch hardcodiert. Die ändern sich ja schließlich nicht.
Doch, der Compiler kann Divisionen (und Modulo-Rechnungen) durch Konstanten umwandeln zu Multiplikationen, das bringt viel Speed.
-
volkard schrieb:
Antoras schrieb:
volkard schrieb:
bei N<1000000 hast Du als Kandidaten nur die Zahlen von 2 bis 1000. Nur 1000 Divisionen.
Wie kommt man da drauf, dass in diesem Zahlenbereich keine größeren Primzahlen eine Rolle spielen? Kann man das berechnen?
Ja. [...]
Danke für die Erklärung. Hab es verstanden.
volkard schrieb:
Antoras schrieb:
volkard schrieb:
Die möglichen Teiler bis 31 (selber messen) hardcoded testen (nicht im Array ablegen).
Was meinst du damit? Wenn sie in dem Array mit Primzahlen liegen sind sie doch hardcodiert. Die ändern sich ja schließlich nicht.
Doch, der Compiler kann Divisionen (und Modulo-Rechnungen) durch Konstanten umwandeln zu Multiplikationen, das bringt viel Speed.
Tatsächlich, der Unterschied kann sogar recht groß sein wie ich festgestellt hab.
Ich hab mich mal näher mit Pollard's Rho in Brents Variante auseinandergesetzt. Hab den Algo zwar zum Laufen gebracht - ihn allerdings noch nicht vollständig verstanden.
Vor allem funktioniert der Algo in Brents Variante nicht immer - manchmal endet er in einer Endlosschleife oder berechnet die Zahl, die eigentlich faktorisiert werden sollte. Der Fehler hängt wohl mit den Psoudozufallszahlen zusammen und tritt auch nur bei Brents Variante auf. Was für Eigenschaften müssen denn alle für die Zufallszahlen gelten, damit der Algo das korrekte Ergebnis liefert?
-
Antoras schrieb:
Vor allem funktioniert der Algo in Brents Variante nicht immer - manchmal endet er in einer Endlosschleife oder berechnet die Zahl, die eigentlich faktorisiert werden sollte. Der Fehler hängt wohl mit den Psoudozufallszahlen zusammen und tritt auch nur bei Brents Variante auf. Was für Eigenschaften müssen denn alle für die Zufallszahlen gelten, damit der Algo das korrekte Ergebnis liefert?
Kann man nicht vorhersagen. Wenn die Start-Zahl unglücklich war, findet er eben mal nichts. Dann die nächste Start-Zahl nehmen. Irgendwann findet er schon was.
-
Ok, ich zähle die Zufallszahl jetzt nach jedem erfolglosen Durchgang nun um eins hoch, was schon Verbesserungen gebracht hat. Das reicht aber noch nicht - der Algo läuft noch immer nicht bei jeder Zahl korrekt durch.
Bisher wähle ich nur Zahlen zwischen 0 und N, die aber offenbar noch nicht ausreichen - manchmal läuft der Algo bei der gleichen Zahl durch, manchmal aber auch nicht. Was könnte noch dran Schuld sein, dass der Algo nicht korrekt terminiert?
-
Nö, jetzt müßte es klappen.
Hast Du Rechenfehler wegen Überläufen?
Wenn nicht, fällt mir auch nichts mehr ein.
-
Ich bin den Code jetzt noch ein paar mal durchgegangen, konnte aber keinen Fehler finden. Ich werde ihn mal posten, vllt. hat ja jemand Lust ihn durchzugucken. Ich bin dabei nach dem Psoudocode vorgegangen, den man hier finden kann.
Folgender Java-Code funktioniert manchmal, manchmal aber auch nicht:
import java.util.ArrayList; import java.util.List; import java.util.Random; import static java.lang.Math.*; public class PollardBrent { public static void main(final String... args) { System.out.println(primeFactors(3624)); } private static List<Integer> primeFactors(final int n) { final List<Integer> l = new ArrayList<Integer>(); search(n, l); return l; } private static void search(final int n, final List<Integer> l) { int i = n; while (i > 1) { if (isPrime(i)) { l.add(i); break; } int d = brent(i); while (d == i) { d = brent(i); } search(d, l); i /= d; } } private static boolean isPrime(final int n) { if (n == 2) { return true; } if (n < 2 || n % 2 == 0) { return false; } final int root = (int) sqrt(n); int j = 3; while (j <= root) { if (n % j == 0) { return false; } j += 2; } return true; } private static int brent(final int n) { if (n % 2 == 0) { return 2; } final int bitLen = (int) ceil(log(n) / log(2)); final int c = new Random().nextInt(bitLen) + 1; int x = c, y = c; int g = 1, r = 1, q = 1, ys = 1; while (g <= 1) { x = y; for (int i = 1; i < r; ++i) { y = f(y, n, c); } for (int k = 0; k < r && g <= 1; k += c) { ys = y; for (int i = 1; i < min(c, r - k); ++i) { y = f(y, n, c); q = q * abs(x - y) % n; } g = gcd(q, n); } r *= 2; } if (g == n) { do { ys = f(ys, n, c); g = gcd(x - ys, n); // c = c < n ? c + 1 : 0; } while (g <= 1); } return g; } private static int f(final int x, final int n, final int c) { return (x * x + c) % n; } private static int gcd(final int a, final int b) { return gcdHelp(abs(a), abs(b)); } private static int gcdHelp(final int a, final int b) { return b == 0 ? a : gcdHelp(b, a % b); } }Größtes Problem ist wohl, dass ich noch immer nicht verstanden hab wie der Algo genau funktioniert. Hab aber dieses Dokument gefunden, das den Code wohl erklärt, vllt. hilft mir das den Fehler zu finden.
Die Standardvariante von Pollard hab ich mittlerweile getestet und dabei festgestellt, dass sie knapp 50% schneller ist als mein bisheriger Algo. Das ist schon mal eine gute Nachricht, auch wenns mit dem Algo von Brent noch nicht so ganz hinhaut.
