Fattorizzazione di grandi numeri

Question

In classe abbiamo riscontrato questo problema di programmazione e al momento non abbiamo idea di come risolverlo.

Viene fornito il numero intero positivo n. È noto che n = p * q, dove p e q sono numeri primi, p<=q e |q-k*p|<10^5 per alcuni dati interi positivi k. È necessario trovare p e q.

ingresso:

35 1 
121 1 
1000730021 9 

uscita:

5 * 7 
11 * 11 
10007 * 100003 

Non è compiti a casa, stiamo solo cercando di risolvere alcuni problemi interessanti. Se hai qualche idea, per favore postala qui, così possiamo provare qualcosa, grazie.

Answer 1

Per i numeri di cui parli qui, il metodo di factoring più veloce è (probabilmente) per utilizzare il setaccio di Eratostene per generare numeri primi fino a circa la radice quadrata del numero, quindi utilizzare la divisione di prova da quelli da trovare quale (s) sono divisori.

Numerosi metodi di factoring sono stati inventati per numeri più grandi. Potresti volere Google per "metodo di factoring di Fermat", "Pollard Rho", "metodo di Brent", "curva ellittica di Lenstra", "setaccio quadratico polinomiale multiplo" e "setaccio di campo di numero generale". Ho elencato quelli in ordine di complessità (all'incirca) crescente e in grado di calcolare numeri più grandi. È aperto il dubbio se dovrei menzionare il setaccio generale del numero o no - mentre è il metodo più efficace attualmente noto per il factoring di numeri estremamente grandi, è utile solo su macchine molto grandi - al di sotto di circa 110 cifre, MPQS è più veloce, ma per calcolare i grandi numeri in cui GNFS è più veloce, è necessaria molta più memoria di quella che un desktop o un server tipico può supportare (si pensi a un terabyte di RAM come punto di partenza minimo, ma probabilmente più di questo).

Answer 2

Ho utilizzato il metodo ECM per il fattore numero intero grande. È uno degli algoritmi più efficienti conosciuti. Se vuoi imparare come funziona l'algoritmo, hai un sacco di letture da fare, ma se vuoi utilizzarlo per fare la tua ricerca, alcune persone lo hanno implementato. Ad esempio è possibile ottenere questi pacchetti open source: GMP-ECM per C/C++ o Pyecm per 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 e k è dato come input.Pertanto

q-k*p=a 

con

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

Moltiplicando q-k*p=a da q e sostituendo p*q da n dà

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

risolvere questa equazione quadratica per ogni a con

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

e verificare se q divide n. La risoluzione di un'equazione quadratica può essere eseguita in tempo polinomiale, e questo è vero per risolvere l'equazione 2*10^5+1. Esistono algoritmi migliori per i piccoli valori di n e k e anche per i grandi valori di n e k, naturalmente.

Come ypercube menzionato, si deve solo controllare le equazioni dove

a^2+4*k*n 

è un quadrato.

Answer 4

n = p * q e | q-k * p | < 10^5 con n e k dati come input. Pertanto qk * p = a, con -10^5 < = a < = 10^5 Moltiplicazione qk * p = a da q ans sostituendo p * q con n dà q^2-a * qk * n = 0 . Risolvi questa equazione di secondo per ogni a con -10^5 < = a < = 10^5 e verifica se q divide n. La risoluzione di un'equazione quadratica può essere eseguita in tempo polinomiale, e questo è vero per risolvere l'equazione 2 * 10^5 + 1. Ci sono migliori algoritmi per piccoli valori di n e k

p è in Intervallo

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

pertanto è necessario verificare solo 10 valori^5/K per p. q è nella Intervallo

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

che contiene sempre circa 10^5 inegers