Factorizar enteros grandes sin un clúster

Question

¿Cuál es el mejor programa para el factor de gran arbitraria de forma enteros en una sola computadora, o en un par de inconexos de los equipos? "Mejor" es obviamente subjetiva, pero ¿qué recomienda usted?

Estoy trabajando en un proyecto para el factor general de la forma de los números, que yo sepa son compuestas, con una escala de 100 - 1000 dígitos. Tengo un par de equipos que pueden utilizar para procesar en paralelo, pero están en ninguna parte cerca de un clúster y, desde luego, no tiene la potencia / memoria necesaria para algo como GNFS.

He mirado un poco, pero lo que he encontrado puede ser clasificada como:

1. Demostrar primalidad general de la forma de los números (la mía = conocido composites)
2. Factor especiales-números de formulario (el mío = general-números de formulario)
3. Factor general-formulario de números en un enorme racimo (no grupo)

Me falta el último, "Factor general-formulario de números en una o dos de la sneakernet sistemas".

Final advertencias: prefiero algo gratis, pero yo estaría dispuesto a primavera de Arce / Mathematica / lo que sea si es mi mejor opción. También prefiero algo que ya está construido (paquete binario), pero puedo compilar desde el código fuente si que es una mejor opción.

Answer 1

Usted está preguntando acerca de una gama muy amplia de números!

Para todos los números, usted debe hacer ECM primera. Recomiendo GMP-ECM (Windows, fuente).

Para los números de alrededor de 100 dígitos, su mejor apuesta (después de hacer una cantidad adecuada de la prueba de la factorización y ECM) es el uso de un SIQS. msieve sería una buena opción.

Para los números de entre 100 y 200 dígitos, usted debe hacer una gran cantidad de ECM, al menos una CPU del día vale la pena (y posiblemente 100+ CPU-días). Una vez que esos completa, si no hay factores que se encontraron, usted debe pasar a GNFS. GGNFS (Windows, fuente) es buena y no requiere de un clúster, a pesar de que para el extremo superior de la gama, usted necesitará por lo menos un año si se está ejecutando en una sola (multinúcleo, uno espera) de la máquina. Aquí están algunas directrices sobre el uso de NFS.

Usted no tiene ninguna esperanza de factorización de números de 200 a 300 dígitos sin muchas máquinas. Por lo tanto, para los grandes generales-formar números, usted debe centrarse completamente en ECM con la esperanza de encontrar un pequeño factor (hasta alrededor de 60 dígitos, con paciencia, o alrededor de 70 dígitos, con la paciencia y la buena fortuna). Si usted encuentra un factor, el cofactor puede ser susceptible a GNFS (o podría ser prime).

Nadie tiene una oportunidad razonable de duro de factor de números de 300 a 1000 dígitos, a menos que posiblemente la NSA. Usted debe utilizar ECM en esos números en la esperanza de encontrar un factor, pero es poco probable para terminar la factorización incluso si usted no hace.

Ahora, si usted tiene acceso a un compatibles con CUDA GPU (o varios), puede acelerar el ECM con EECM . No sé de cualquiera de las herramientas que hacer NFS en GPUs.

En resumen: ECM un montón, luego rematar con SIQS o NFS si el número es lo suficientemente pequeño (por debajo de 180-200 dígitos en función de sus recursos y la paciencia). Si quieres tirar el dinero en el problema, comprar más hardware, posiblemente Gpu-no comprar software comercial, que no tiene la explosión para su buck.