Faktorisierung von großen Zahlen

Question

Im Unterricht sind wir auf dieses Programmierproblem gestoßen, und wir haben derzeit keine Ahnung, wie wir es lösen können.

Die positive ganze Zahl n gegeben ist. Es ist bekannt, dass n = p * q , donde p y q Primzahlen sind, p<=q y |q-k*p|<10^5 für eine gegebene positive ganze Zahl k . Sie müssen finden p y q .

Eingabe:

35 1
121 1
1000730021 9

Sortie :

5 * 7
11 * 11
10007 * 100003

Es sind keine Hausaufgaben, wir versuchen nur, einige interessante Probleme zu lösen. Wenn ihr Ideen habt, postet sie bitte hier, damit wir etwas ausprobieren können, danke.

Answer 1

Für Zahlen in der Größenordnung, von der Sie hier sprechen, ist die schnellste Factoring-Methode (wahrscheinlich), das Sieb des Eratosthenes zu verwenden, um Primzahlen bis ungefähr zur Quadratwurzel der Zahl zu erzeugen, und dann eine Probedivision durch diese Zahlen durchzuführen, um herauszufinden, welche Zahl(en) Teiler sind.

Für größere Zahlen wurden zahlreiche Factoring-Methoden erfunden. Googeln Sie mal nach "Fermat's factoring method", "Pollard Rho", "Brent's method", "Lenstra elliptical curve", "multiple polynomial quadratic sieve" und "general number field sieve". Ich habe diese in (grob) aufsteigender Reihenfolge der Komplexität und der Fähigkeit, größere Zahlen zu faktorisieren, aufgelistet. Es ist fraglich, ob ich das allgemeine Zahlenfeldsieb erwähnen sollte oder nicht - es ist zwar die effizienteste Methode, die derzeit für die Faktorisierung extrem großer Zahlen bekannt ist, aber sie ist nur auf wirklich großen Rechnern nützlich - unterhalb von etwa 110 Ziffern ist das MPQS schneller, aber um die großen Zahlen zu faktorisieren, bei denen das GNFS schneller ist, braucht man viel mehr Speicher, als ein typischer Desktop oder Server unterstützen kann (man denke an ein Terabyte RAM als minimalen Ausgangspunkt, aber wahrscheinlich mehr als das).

Answer 2

Ich habe die ECM Methode, um große Ganzzahlen zu faktorisieren. Es ist einer der effizientesten bekannten Algorithmen. Wenn Sie lernen wollen, wie der Algorithmus funktioniert, müssen Sie eine Menge lesen, aber wenn Sie ihn für Ihre Forschung nutzen wollen, haben ihn einige Leute implementiert. Sie können zum Beispiel diese Open-Source-Pakete erhalten: GMP-ECM für C/C++ oder Pyecm für Python.

$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]

Answer 3

n = p * q 
|q-k*p|<10^5

con n y k wird als Eingabe gegeben. Daher

q-k*p=a 

con

-10^5<=a<=10^5

Multiplizieren q-k*p=a por q und die Ersetzung p*q durch n ergibt

q^2-a*q-k*n=0

Lösen Sie diese quadratische Gleichung für jede a avec

-10^5<=a<=10^5` 

und prüfen, ob q dividiert n . Das Lösen einer quadratischen Gleichung kann in Polynomialzeit erfolgen, und dies gilt für das Lösen 2*10^5+1 Gleichung. Es gibt bessere Algorithmen für kleine Werte von n y k und auch für große Werte von n y k natürlich.

Wie ypercube erwähnte, muss man nur die Gleichungen überprüfen, bei denen

a^2+4*k*n

ist ein Quadrat.

Answer 4

N = p * q und |q-k*p|<10^5 mit n und k als Eingabe. Daher ist q-k*p=a, mit -10^5<=a<=10^5 Die Multiplikation von q-k*p=a mit q und die Substitution von p*q durch n ergibt q^2-a*q-k*n=0. Lösen Sie diese quadratische Gleichung für jedes a mit -10^5<=a<=10^5 und prüfen Sie, ob q durch n teilbar ist. Das Lösen einer quadratischen Gleichung kann in Polynomialzeit erfolgen, und dies gilt auch für die Lösung der 2*10^5+1 Gleichung. Für kleine Werte von n und k gibt es bessere Algorithmen

p liegt im Intervall

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]

Daher müssen Sie nur 10^5/k Werte für p prüfen. q liegt im Intervall

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]

der immer etwa 10^5 Inger enthält

Answer 5

Sie können die GUI-basierte Version von YAFU verwenden von http://qurancode.com um ein größeres Beispiel auszuprobieren. Der Hauptvorteil von YAFU ist seine adaptive Natur, bei der es den Algorithmus während des Factorings automatisch umschaltet. Wirklich das Beste und einfacher mit der GUI-Edition für Windows 7/8/10.

Klicken Sie einfach auf das gelbe PI-Symbol, das von einem roten Herz umgeben ist :)