La forma más rápida de factorizar enteros < 2^60

Question

Llevo unos 12 meses buscando curvas de Mordell de rango >=8 y he identificado aproximadamente 280.000 curvas en nuestro rango archivable, entre muchos millones que no lo están.

Para esta búsqueda he estado utilizando hasta 60 cpus de 3Ghz+ a la vez. Ahora estoy llegando a un punto en el que el rendimiento disminuye y los requisitos de memoria aumentan considerablemente. Por lo tanto, tengo que ser un poco más inteligente en algunas de las matemáticas.

Mi pregunta es, entonces, cuál se cree (o se sabe) que es el algoritmo de factorización más rápido para enteros positivos < 2^60.

No estoy muy dispuesto a consumir más décadas de GHz de potencia de procesamiento a menos que pueda obtener un rendimiento razonable de la inversión, para lo cual un algoritmo de factorización rápido sin duda ayudaría.

Cualquier idea será más que bienvenida.

EDITAR:

Leyendo las respuestas me doy cuenta de que probablemente debería añadir que quiero mantener la factorización dentro de la aritmética de 64 bits. El algoritmo Pollard Rho era interesante, pero probablemente superaría el límite de 64 bits durante su ejecución.

Otra parte del rompecabezas es que, a partir de las factorizaciones, estoy almacenando las diferencias de pares de divisores para cada número factorizado. Esto puede, potencialmente, dejarme con una matriz de alrededor de 50.000.000 valores que luego, posteriormente, necesita ser ordenada.

He estado utilizando Pari/GP para este proyecto y, hasta ahora, ha ido genial. Mi problema actual es principalmente con el uso de memoria, ya que cada tarea de Pari/GP ocupa más de 8GByte de memoria. Esto está impidiendo que mi máquina de 32 núcleos sea tan eficiente como podría haber sido de otra manera. De ahí mi intención de pasar a la aritmética de 64 bits y al código 'C', con la esperanza de ganar eficiencia tanto en tiempo como en espacio, dando así nueva vida a un proyecto que de otro modo se estancaría.

Actualización:

Gracias a todos los que han respondido con tan buenas sugerencias sobre cómo proceder.

Al final he decidido utilizar la biblioteca flint, como sugirió William Hart, en lugar de intentar reinventar la rueda. La capacidad de flint para trabajar directamente con enteros de 64 bits me da una gran ventaja en cuanto a uso de memoria y velocidad en comparación con mi configuración actual. En particular, ahora puedo ejecutar los 32 núcleos en mi máquina principal y todavía tener memoria de sobra, potencialmente dando una mejora de 8 veces en el rendimiento de procesamiento.

Kevin.

Answer 1

Merece la pena echar un vistazo al SQUFOF (Square FOrm Factorisation) de Shanks.

Henri Cohen comenta:

Este método es muy sencillo de aplicar y tiene la gran ventaja de trabajar exclusivamente con números que son como máximo $2\sqrt{N}$ [...] Por lo tanto, es eminentemente rápido y práctico cuando se quieren factorizar números menores que $10^{19}$ incluso en una calculadora de bolsillo.

Y $2^{60}$ está justo debajo de $10^{19}$ y, de hecho, el $10^{19}$ como el número tal que $2\sqrt{N}$ todavía cabe en un "int". Como referencia, la complejidad es $O(N^{1/4+\varepsilon})$ ; pero este no es el punto principal.

Normalmente, esto tendría que ir precedido de una división de prueba para factores pequeños y (posiblemente) alguna prueba de primalidad.

En general, recomiendo los capítulos pertinentes del libro "A course in computational algebraic number theory" de Henri Cohen (del que está tomada la cita); normalmente, además de teoría y algoritmos, también discute aspectos prácticos de la implementación (al no ser el libro reciente, algunos de ellos podrían tener que modificarse, pero aún así el aspecto práctico y la discusión de rangos están presentes).

Además, es fácil encontrar otras referencias de SQUFOF en Internet.

---

Algunas referencias y citas más, y algunos comentarios.

Gower y Wagstaff (Factorización de la forma cuadrada, Math of Computation, 2008) en un artículo sobre SQUFOF :

En un ordenador de 32 bits, SQUFOF es el algoritmo de factorización campeón indiscutible para números comprendidos entre $10^{10}$ y $10^{18}$ y es probable que siga siéndolo.

Más recientemente William Hart propuso una variante de Fermat que denominó Algoritmo de factorización en una línea que describe como competitivo con SQUFOF en la práctica (aunque sólo es $O(n^{1/3})$ ). En el documento respectivo, para ser precisos un preprint del mismo no tengo el documento real, escribe (J. Aust. Math. Soc. 2012)

La mayoría de los paquetes de álgebra computacional modernos implementan numerosos algoritmos para la factorización. Para números que caben en una sola palabra de máquina es popular el SQUFOF de Shanks, ya que tiene tiempo de ejecución $O(n^{1/4})$ con una constante implícita muy pequeña.

Por lo tanto, para el rango que se pide en la pregunta estoy bastante seguro de que SQUFOF sería una buena elección. Sin embargo, hay que tener en cuenta que, como también se comenta en el libro de Cohen, a medida que los números aumentan (más allá del umbral mencionado) SQUFOF deja de ser atractivo, mientras que, por ejemplo, Pollard rho sigue siendo interesante. A grandes rasgos, esto parece deberse a que SQUFOF no se beneficia de los factores "pequeños", a diferencia de, por ejemplo, Pollard (véase la respuesta de Laurent Berger). Sin embargo, para números en ese rango y después de división de prueba (Cohen sugirió entonces la división de prueba por primos hasta 500000) de todos modos no hay factores tan "pequeños".

Como ya se ha señalado, una gran ventaja de SQUFOF es que los números implicados son sólo de tamaño $2\sqrt{N}$ a diferencia de otros métodos que suelen requerir $N$ o incluso $N^2$ . Esto afecta sólo a la constante en el tiempo de ejecución, pero esto también es importante, y además en la práctica permite arreglárselas con tipos de datos simples durante más tiempo.

Answer 2

Hace mucho tiempo programé mi HP48 (¡4 MHz! ¡Vaya!) en lenguaje ensamblador para factorizar números. Hacía la división de prueba por todos los enteros congruentes a $\pm 1 \bmod{6}$ hasta algún límite B y luego usar el método rho de Pollard. Supongo que en tu caso tienes que averiguar cuál debe ser B dependiendo de tu implementación. En ese momento, estaba usando "Prime Numbers and Computer Methods for Factorization" de Hans Riesel como referencia. Desde $2^{60}$ es relativamente pequeño, no estoy seguro de que métodos más potentes fueran realmente de ayuda. Se cree que el método rho de Pollard está en algo así como $O(p^{1/2})$ donde $p$ es el factor primo más pequeño de tu entero, que es bastante pequeño en tu caso.

Answer 3

Inria ha publicado un trabajo de factorización de enteros de 50-200 bits.
Los cuatro métodos elegidos son: SQUFOF, ECM, SIQS y CFRAC.

En el documento se ofrece un breve pseudocódigo de cada método, para que pueda juzgar si se adaptan a sus restricciones de cálculo.

De sus experimentos se desprende que SQUFOF es efectivamente el más rápido hasta $2^{60}$ donde está empatado con SIQS. Tenga en cuenta que estos experimentos se realizan con números enteros que se sabe que tienen pocos factores primos (Algo así como 2-4).

En tu caso, parece que estás factorizando números enteros aleatorios hasta $2^{60}$ .
Por lo tanto, excepto en el caso de ECM, es más eficiente factorizar a prueba los números primos pequeños hasta un cierto límite.
(Véanse más abajo los comentarios sobre el caso ECM)

Un punto adicional: ECM (específicamente GMP-ECM también de Inria) puede ser una buena idea, ya que el software está muy optimizado. (Con un equipo de investigación codificándolo desde hace unos años)
Por otra parte, la aritmética se realiza en módulo $N$ .
Esto podría significar que habrá desbordamiento durante los pasos de multiplicación.

Si eliges ECM, puedo explicarte un poco más.
Un problema común es el hecho de que ECM es probabilístico.
Esto puede resolverse si sabes qué curvas elegir para cubrir todos los factores primos.
Inria también ha publicado sus trabajos en este ámbito, que demuestran que 124 curvas cuidadosamente elegidas encuentra todos los factores primos hasta $2^{32}$ .
Las cifras son bastante adecuadas para su caso.
Sin embargo, estadísticamente hablando, los factores se encuentran con una probabilidad de alrededor de 0,15 por curva, por lo que 20 curvas suelen ser suficientes.
Como se mencionó anteriormente, utilizando estos parámetros puede omitir la parte de factorización de prueba.
Durante la búsqueda de grandes primos, también encontrará los más pequeños en el proceso.

Si desea aumentar aún más la eficacia, lo mejor es realizar primero un filtrado basado en $P-1$ y $P+1$ método de factorización, seguido del ECM real.
Esto es un poco más difícil, ya que es necesario calibrar los parámetros correctamente.

EDIT : No se dio cuenta de que todos los números son de la forma $x^3-y^3$ con $ 0 < y < x < 50000 $ .
Hay alrededor de $50000^2/2=2^{36.86}$ posibilidades.
De todos ellos, una parte serán primos.
Una parte será suave con factores $< B$ para algunos $B$ que puede dividirse fácilmente en juicios.
Los demás casos son compuestos con primos $> B$ .

Suponga que tiene $n$ entradas restantes.
Clasifíquelos en el siguiente formato, por $N_i$ :
$N_i L_i$ donde $N_i$ es el valor de la entrada, cada uno un compuesto de factores $> B$ y $L_i$ es el desplazamiento para encontrar la factorización.
En offset $L_i$ , almacene los factores primos distintos (puede optar por no almacenar la multiplicidad haciendo la división de prueba).

Cada vez se obtiene un número:
1) Realice la prueba de primalidad 2) Realice la división de prueba 3) Realizar otra prueba de primalidad
4) Si quedan residuos, haz una búsqueda binaria en la factorización

Creo que esto debería poder manejar tu factorización de 4 millones.
Está claro que hay más formas de ajustar el método, pero la idea aquí es que puedes hacer un cálculo de una sola vez y almacenar los cálculos difíciles como una tabla de consulta.

Answer 4

Este cálculo es mejor hacerlo por lotes.

Empezaremos por calcular un conjunto $S$ de enteros relativamente primos tal que cada entero que se quiera factorizar sea un producto de potencias de este conjunto. Esto se puede hacer de manera eficiente por un algoritmo debido a Bernstein, un enlace es: http://www.dcc.unicamp.br/~rdahab/cursos/mo637-mc933/Welcome_files/numTheory/WebPages/DBernstein_perfectpowers.html Este paso es útil porque garantiza que cada factor primo se factorizará un número mínimo de veces. En el caso extremo, factorizará todos los números.

El segundo paso consiste en factorizar los elementos en $S$ . Potencialmente puede haber primos de hasta $2^{59}$ en $S$ pero sólo tenemos que preocuparnos de los primos hasta $2^{30}$ . Los métodos de Factorización por Curva Elíptica son probablemente el método de elección.

Answer 5

En caso de relevancia: Doy por hecho que está cribando sus 280.000 curvas y desechando las que no le convienen. La pregunta es, ¿necesitas una factorización completa de tus números para descartar una curva? Por ejemplo, si quiero descartar cualquier número que no sea la suma de dos cuadrados, puedo deshacerme muy rápidamente de un alto porcentaje mediante la división de prueba por primos hasta 1000. Es decir, si hay un primo $q < 1000$ con $q \equiv 3 \mod 4$ y mi número de sujeto de examen $n \equiv 0 \pmod q$ pero $n \neq 0 \pmod {q^2},$ entonces sé que $n$ no es la suma de dos cuadrados. Y, para tales números, no he necesitado realizar una factorización completa. De hecho, cualquier aparición de una potencia impar de tales $q$ decidirá la cuestión.

Bueno, así ha sido en general como he conseguido hacer las cosas, división de prueba hasta un límite pequeño para la selección inicial, hasta un límite mayor para los que quedan, finalmente apelar a la curva elíptica para los testarudos.

Veamos, $2^{60} \approx 10^{18}.$ No está tan mal. Primer cribado por primos hasta $1024 = 2^{10}.$ Segundo cribado por primos hasta $1,048,576 = 2^{20}.$ Si algún número no está completamente factorizado por ahora, es el producto de dos primos solamente.