Paralelización de Factorización Pollard-Rho

Question

Recientemente me topé con a paper en una paralelización de Pollard's Rho algorithm, y dada mi aplicación específica, además del hecho de que no he alcanzado el nivel requerido de matemáticas, me pregunto si esta particular paralelización método ayuda a mi caso específico.

Estoy tratando de encontrar dos factores-semiprimas-de un número muy grande. Mi suposición, basada en lo poco que puedo entender del documento, es que esta paralelización funciona bien en un número con muchos factores más pequeños, más que en dos factores muy grandes.

¿Es esto cierto? ¿Debería usar esta paralelización o usar algo más? ¿Debería incluso usar Rho de Pollard, o hay una mejor paralelización de un algoritmo de factorización diferente?

Answer 1

La idea básica al factorizar enteros grandes es utilizar una variedad de métodos, cada uno con sus ventajas y sus desventajas. El plan habitual es comenzar con la división de prueba por primos a 1000 o 10000, seguido de unos pocos millones de pasos de Pollard rho; eso debería darte factores de hasta doce dígitos. En ese punto, algunas pruebas están en orden: es el número una potencia principal o una potencia perfecta (hay pruebas simples para esas propiedades). Si aún no ha tenido en cuenta el número, sabe que será difícil, por lo que necesitará herramientas de servicio pesado. Un siguiente paso útil es el método p-1 de Pollard, seguido de su primo cercano, el método de la curva elíptica. Después de un tiempo, si eso no funciona, los únicos métodos que quedan son el tamiz cuadrático o el tamiz de campo numérico, que son intrínsecamente paralelos.

El método de rho paralelo que solicitó no se usa ampliamente en la actualidad. Como sugirió, Pollard rho es más adecuado para encontrar pequeños factores en lugar de grandes. Para un semi-prime, es mejor pasar ciclos paralelos en uno de los tamices que en Pollard rho.

Recomiendo el foro de factoring en mersenneforum.org para obtener más información.

Answer 2

artículo de Wikipedia establece dos ejemplos concretos:

Number    Original code  Brent's modification 
18446744073709551617 26 ms    5 ms 
10023859281455311421 109 ms    31 ms 

En primer lugar, ejecute estos dos con su programa y echar un vistazo a sus tiempos. Si son similares a esto (los números "duros" calculan de 4 a 6 veces más), pregúntese si puede vivir con eso. O mejor aún, use otros algoritmos como la simple factorización de "fuerza bruta" clásica y observe los tiempos que brindan. Supongo que pueden tener un factor difícil más cerca de 1, pero peores tiempos absolutos, por lo que es una simple compensación.

Nota al margen: Por supuesto, la paralelización es el camino a seguir aquí, supongo que lo sabes, pero creo que es importante destacarlo. Además, sería útil para el caso que otro enfoque sea entre las temporizaciones de Pollard-rho (por ejemplo, Pollard-Rho 5-31 ms, enfoque diferente 15-17 ms) - en este caso, considere ejecutar los 2 algoritmos en hilos separados hacer una "carrera de factorización".

En caso de que todavía no tenga una implementación real del algoritmo, aquí están Python implementations.