Existen varios algoritmos rápidos para factorizar números grandes, pero ¿cuál es el mejor algoritmo para factorizar un montón de "pequeños" números? Necesito factorizar un montón de números Impares $< \mathbf{2^{56}}$ . Quiero hacerlo sólo con 64 bits aritmética.
Yo uso una combinación de eso:
- Una tabla de todos los primos $< 2^{16}$ .
- Una "técnica de compensación" para iterar sobre posibles números primos mayores que $2^{16}$ .
- Le site Rho de Pollard heurística para (probablemente) encontrar un divisor. He implementado la versión presentada en "Introducción a los algoritmos" (Cormen, Leiserson, Rivest y Stein), con la adición de un número máximo de iteraciones algo así como $n^{1/2}$ o $n^{1/4}$ .
De hecho, quiero calcular el suma de divisores Impares $\sigma_{\text{odd}}$ de estos números. Para comprobar que $\forall n \in \mathbb{N}, n > 1, \exists k : \sigma_{\text{odd}}^k(n) < n$ . ¿Quizá haya una forma mejor de hacerlo que utilizar la factorización completa en números primos?
¿Y qué pasa con todas estas consideraciones en un en paralelo ¿contexto?
Respuesta : Por último, utilizo una gran tabla única con todos los números primos $<2^{32}$ :
- prime32.7z (165 MiB): https://mega.nz/#!jQtWGY5Y!jHj0PXwJ52Rd69cSuFzo_X_3lk-N5GJHC5JiiR0K7wE
- prime32.bin.gz (272 MiB): https://mega.nz/#!jU9FDRBK!wLfU4YncXYR5fZbUTqRGNZX7eL_j6BlG2j4mSr3YHBM
