Muchos algoritmos son conocidos por factorizar números pequeños y grandes, tanto de formas especiales como generales. Enlace obligatorio de factorización de enteros de Wikipedia, que le brinda una visión general muy básica y listas de algunos algoritmos, pero también omite montones de cosas útiles para saber. Es un área llena de digresiones e información profunda sobre muchos pequeños subcampos.
Por supuesto, necesitamos saber qué significa “muy grande” para usted. El método de tamizado de Ryan, aunque es una idea inteligente para su propósito, es dudoso aquí, ya que realmente solo funciona si se considera que 10 ^ 9 más o menos es “muy grande”. Admito que algunas personas lo hacen, pero al factorizar términos es “muy pequeño”. “Y sobre todo de uso en la programación de problemas de tipo desafío.
Para números de 32 bits (aproximadamente 4 mil millones), todo es bastante rápido, por lo que estamos optimizando nanosegundos bajo el supuesto de que lo llamaremos con bastante frecuencia. Hay enfoques de tabla, pero generalmente una pequeña división de prueba y algo como Fermat, Hart’s OLF, p-1 o Pollard Rho funciona bien. Las implementaciones generalmente toman menos de medio microsegundo para factorizar cualquier entrada de 32 bits.
- ¿Qué es el algoritmo k-Means y cómo funciona?
- ¿Cuáles son los ejemplos del mundo real que puedo usar para ilustrar la recursividad de mi clase de introducción CS?
- ¿Cómo funciona esta recursión?
- Cómo aprender estructuras de datos y algoritmos
- ¿Encuentra el número de fila y el número de columna donde 20096 ocurre en una matriz triangular?
Para números de 64 bits (aproximadamente 19 dígitos y menos, más unos 20 dígitos pequeños), el ganador moderno está optimizado Pollard Rho / Brent. SQUFOF se acerca y solía ser la respuesta correcta en el extremo superior, pero los experimentos de varios autores el año pasado mostraron que esto ha cambiado. Los tiempos prácticos son de aproximadamente 50 microsegundos para el peor de los casos (semiprimes de 64 bits), menos para entradas más pequeñas o más fáciles.
Para números de 30 a 40 dígitos y menores, Pollard Rho, Pollard P-1, ECM, y los llamados métodos de “pequeño QS” son los mejores. Los primeros son mucho más fáciles de escribir y existen una variedad de versiones rápidas, pero las mejores implementaciones pequeñas de QS son más rápidas. Los tiempos prácticos son de 4 a 500 milisegundos para semiprimes, pero hay muchas variaciones según la entrada y la implementación.
Hasta 100 dígitos, QS (Quadratic Sieve) es el ganador. Existen múltiples variantes de algoritmos y diferentes implementaciones de cada uno. Probablemente menos de una hora si utiliza una buena herramienta (por ejemplo, YAFU).
Más allá de eso, la respuesta es GNFS (Tamiz de campo de número general). Esto va a funcionar prácticamente (aunque lentamente) hasta aproximadamente 170 dígitos, después de lo cual básicamente no tienes suerte a menos que no sea mucho más alto y tengas muchos recursos. Para usar una declaración no perfecta, si no ha considerado las compensaciones de Inifiniband vs. 40/100 GbE para su clúster (o no sabe lo que acabo de decir), entonces no tiene los recursos. 🙂
Vea el excelente informe del estado del arte a principios de 2018, así como instrucciones simples para hacerlo usted mismo aquí:
Cómo comenzar a factorizar, por Victor de Hollander
