¿Cuál es el algoritmo más eficiente para factorizar un número en sus factores primos?

Answer 1

Esta pregunta es muy similar a:

¿Cuál es el algoritmo de factorización prima más rápido?

¿Cuál es el algoritmo de factorización prima más rápido hasta la fecha?

---

La respuesta es, depende. Suponga que recibe una entrada arbitraria que no tiene alguna forma especial. El algoritmo más eficiente es una receta que utiliza algoritmos de factorización individuales. Estas son todas las posibilidades:

Para entradas muy pequeñas, use la división de prueba por números primos (o una rueda para acercarse sin tener que tener o generar números primos). Esto funciona mejor para ~ 1M, dependiendo de las implementaciones. Alguna división de prueba es siempre una buena idea para eliminar pequeños factores.

Pollard Rho funciona bastante bien. A medida que la entrada se hace más grande (por ejemplo,> 2 ^ 32 pero menos de 2 ^ 64), SQUFOF generalmente funciona más rápido.

Una vez más grande que 2 ^ 64, Pollard Rho todavía puede valer un poco de tiempo para encontrar pequeños factores, pero P-1 y ECM son mejores cuando se busca más profundamente.

El tamiz cuadrático generalmente es mejor comenzar en algún lugar en el rango de 30-40 dígitos y continuar hasta 95-105 dígitos.

Después de eso, NFS (GNFS) es el algoritmo más eficiente.

=================================================

Tenga en cuenta que, aparte de las entradas pequeñas, el método más eficiente no es solo elegir una de ellas y ejecutarla, sino pasar por una secuencia. También necesitamos una prueba de primalidad eficiente, que es otro tema. Por ejemplo, dado un número arbitrario de 150 dígitos, lo mejor que puede hacer es no comenzar a ejecutar NFS. Deberíamos eliminar los divisores pequeños, primero por división de prueba (quizás con un GCD rápido, o un árbol restante, o simplemente una prueba de divisibilidad), luego usando los algoritmos que son eficientes para encontrar divisores pequeños: Pollard Rho, P-1 y ECM . Estos encontrarán eficientemente pequeños divisores (en el caso de ECM, ¡”pequeño” puede tener más de 20 dígitos!). ¿Por qué molestarse con Rho y P-1 si ECM es más eficiente a largo plazo? Porque un corto recorrido de Rho o P-1 es típicamente más rápido que ECM si los divisores son pequeños. Algunas personas no se preocupan por esta optimización e irán directamente a ECM (señalando que la forma en que ejecuta ECM en términos de tamaño y número de curvas termina siendo una discusión similar), y las implementaciones son importantes.

Una vez que ha ejecutado “suficiente” P-1 / ECM, y el número que todavía tiene que procesar es compuesto, entonces elige QS o NFS.

Para el caso de menos de 128 bits, puedo dar el ejemplo del factor GNU de Grandlund y Möller. Realiza la división de prueba por pequeños números primos seguidos de Pollard Rho o SQUFOF. Perl / ntheory es más complicado, ya que utiliza más algoritmos y más optimización para entradas pequeñas.

Para entradas más grandes, yafu es un programa de factoring de última generación. Comienza con la división de prueba, hace un poco de Pollard Rho, luego comienza a mezclar P-1 y ECM en una secuencia de tamaños y curvas que funcionan bien en promedio, luego elige QS o NFS en función del tamaño de entrada restante y el punto de cruce medido para la máquina. Esto básicamente sigue lo que describí.

Answer 2

No tengo una respuesta, pero estoy trabajando en un algoritmo prometedor para factorizar un producto de dos primos muy grandes (utilizados como claves en software de cifrado como RSA) y mi opinión sobre esto es que debe pensar en algo muy innovador maneras de crear algoritmos de alto rendimiento. En mi caso, me alejé de un enfoque de módulo / teoría de grupo / teoría de números elementales, para tratar principalmente con números reales (no enteros) y el teorema del punto fijo en un contexto inusual: aplicado a funciones caóticas, no continuas. Puede leer sobre mi algoritmo (todavía en progreso, pensé que he factorizado números como 395,909,818,831 de manera muy eficiente, en Factoring Massive Numbers: Machine Learning Approach – Why and How).

Answer 3

Para números muy grandes, no hay algoritmos eficientes.

Por ejemplo, supongamos que generé dos primos grandes de 1000 dígitos, P1 y P2. (En realidad, esto no es tan difícil de hacer con un fondo matemático discreto).

Ahora los multiplico para obtener C = P1 * P2, que tiene alrededor de 2000 dígitos, más de 6000 bits.

Y te doy C y te pido que lo factorices.

El sol se quemará antes que tú. Entonces se dice que factorizar es difícil.

Por cierto, si pudieras hacer esto, habrías roto el algoritmo RSA, y el mundo del cifrado se sumirá en el caos. Si juegas bien tus cartas, ganarás mucho dinero vendiendo tu técnica a la NSA, siempre y cuando no se lo digas a nadie más.

Los matemáticos trabajan todo el tiempo tratando de encontrar formas más rápidas de factorizar, porque no conocemos formas rápidas de factorizar números tan grandes.

Para un número, N, menos de un billón más o menos, primero asegúrese de que no sea par o que termine en 5.

Luego cree un bucle que lo divida entre 3, 5, 7, 9, 11, … sqrt (N)

Esto se repetirá en el peor medio millón de veces. Entonces descubrirás muy rápidamente si es primo.

Answer 4

Si los factores son grandes, el tamiz de campo numérico. Solo para profesionales. Busque concursos de factoring RSA.

Para encontrar factores “pequeños”, el método de curva elíptica será más rápido.

Y, por supuesto, use la división de prueba para eliminar pequeños factores (por ejemplo, <1,000).