¿Cuál podría ser el algoritmo eficiente para obtener el factor primo más grande de un número realmente grande, es decir, en el orden de 10 ^ 18?

Answer 1

Michal Forišek está en lo correcto. Para factorizar, este es un número pequeño. Cualquier cosa por debajo de 50 dígitos es fácil con algoritmos modernos y computadoras, y menos de 100 dígitos no es muy difícil. Las cosas se ponen interesantes por encima de los 120 dígitos.

Para un número en el rango de 10 ^ 18, rho de Pollard y SQUFOF son los dos algoritmos más efectivos. Para obtener la mejor eficiencia para las entradas arbitrarias, es probable que realice algunas divisiones de prueba al comienzo, y es posible que también desee una prueba de primalidad rápida. Dado que cualquiera de los algoritmos puede devolver resultados compuestos (por ejemplo, factorizar p * q * r * s puede devolver p * q), es posible que desee una pila (en este tamaño pequeño puede hacer suficiente división de prueba para limitar a una sola variable temporal).

En mi computadora, las entradas aleatorias de 60 bits (aproximadamente 10 ^ 18 de tamaño) se pueden factorizar por completo en aproximadamente 60 microsegundos . Ascender a semiprimes aleatorios de 18 dígitos es de aproximadamente 400 microsegundos. Sus algoritmos e implementaciones pueden variar. Los “pocos milisegundos” de Michal son un buen número conservador.

Answer 2

Voy a pedirle al OP que sea paciente aquí, así que doy algunos antecedentes para esta pregunta. Y luego lo responderé.

En general, se sabe que factorizar números grandes es un problema difícil en las matemáticas. Hay matemáticos que trabajan para encontrar formas más rápidas de factorizar todos los días. Y también es un problema muy importante. Por ejemplo, una de las técnicas de cifrado más importantes, utilizada muchas veces al día, se llama algoritmo RSA.

Y una de las razones por las que es útil es que es prácticamente irrompible. A menos que podamos encontrar una manera rápida de factorizar números muy grandes, es decir. Si es así, RSA está listo y tendríamos que cambiar a otras técnicas de cifrado.

El valor clave más importante en el algoritmo RSA es un número que es el producto de dos primos muy grandes, P1 y P2. Así que defina N = P1 * P1 y tenga en cuenta que N es esencial para cifrar y descifrar.

Los números primos se generan aleatoriamente y son muy, muy grandes. Por ejemplo, ¡cada uno podría tener 300 dígitos! Es decir, estarían en algún lugar alrededor de [math] {10} ^ {300} [/ math] cada uno, por lo que N = P1 * P2 tendría aproximadamente 600 dígitos decimales.

Con nuestro conocimiento matemático actual y las velocidades actuales de la computadora, supongamos que le di este valor para N y le dije que era el producto de dos números primos de 300 dígitos. Factor N para mí.

No importa cuánto quisieras factorizar N para mí, es más probable que el Sol se queme antes de que puedas factorizarlo. Sí, es tan difícil de factorizar.

(Cómo encontrar primos tan grandes es una historia hermosa y fascinante en sí misma).

—–

Ahora hay buenas noticias para el OP. Y eso se debe a que el OP ‘solo’ quiere factorizar un número del tamaño [math] {10} ^ {18} [/ math]. Y los números de ese tamaño se pueden factorizar con bastante rapidez utilizando una técnica estándar.

Digamos que se nos da un número N, que es alrededor de [matemáticas] {10} ^ {18} [/ matemáticas]. Una cosa muy importante que debe saber es que si estamos dividiendo números en N para encontrar un factor, el factor más grande no debe ser más que [math] \ sqrt {N} [/ math]. ¿Por qué? Digamos que N es 100. Comenzamos a dividir entre 3, luego 5, luego 7, luego 9, luego 11. Pero espere, si dividimos 11 en 100 obtendremos 9 (redondeado) y ya verificamos 9.

Si N es par, podemos escribir 2 como factor primo, y luego dividir los números impares hasta la raíz cuadrada de N y encontraremos todos los factores de N.

El pseudocódigo se vería así:

displayFactors (int N)
{
si N es par, imprime 2

para (int i = 3; i <= sqrt (N); i + = 2) // incrementaré en 2
{
if (N% i == 0) // i se divide en N sin resto
imprimir (i);
}

Y ahi tienes. Todos los factores de N. ¿Cuánto tiempo lleva esto? [matemáticas] \ sqrt {N} = \ sqrt {{10} ^ {18}} = {10} ^ {9} [/ matemáticas]. Esto es solo mil millones, por lo que necesitaríamos medio billón de bucles. Ninguna de las operaciones dentro del ciclo toma mucho tiempo (siempre que el compilador calcule sqrt (N) solo una vez).

Answer 3

En términos de números que ya podemos factorizar, [matemáticas] 10 ^ {18} [/ matemáticas] todavía se considera pequeño. Para números de este tamaño, el algoritmo rho de Pollard es una buena opción: es lo suficientemente simple de implementar desde cero y lo suficientemente rápido como para factorizar cualquier número de nuestro rango en unos pocos milisegundos.