Cómo encontrar los factores primos de los números rápidamente

Answer 1

Similar a ¿Cuál es el algoritmo de factorización prima más rápido hasta la fecha?

No hay suficiente información en la pregunta para saber realmente lo que está preguntando, ya que puedo pensar en muchas formas de adivinar lo que quiere decir.

Si está pensando en hacer esto a mano, use métodos fáciles para los humanos, como la regla de Divisibilidad, Wikipedia. Básicamente formas de acelerar la división de prueba para humanos normales. Si realmente te interesan las matemáticas e insistes en no usar computadoras, entonces comienzas a buscar formas especiales, diferencias de cuadrados, etc. Básicamente lo que la gente hizo en el siglo XVII o principios del siglo XX para factorizar números, y todavía a veces lo hace hoy.

Si solo desea los factores para algún propósito práctico, entonces usa un programa que alguien ha escrito para esto, por ejemplo, Pari / GP, Mathematica, yafu, alpertron, Perl / ntheory, Python / primefac, etc. Hay muchos. Yafu es lo último en factoraje amateur.

Si desea hacerlo usted mismo en una computadora, primero debe determinar cuáles son sus requisitos. ¿Está factorizando números trivialmente pequeños, como menos de 1M? ¿Menos de 64 bits? ¿Menos o más de 100 dígitos? Entradas aleatorias o semiprimes? ¿Quieres que “rápidamente” signifique bastante rápido o * realmente * rápido? Si es esto último, prepárese para un montón de trabajo, ya que no existe un método único para todos y se verá empantanado en todos los detalles por los cuales las personas pasaron * años * trabajando en los programas encima.

También necesita saber qué es práctico. Factorizar números de 64 bits de cualquier tipo no es muy difícil para las computadoras. Mi Macbook puede factorizar completamente más de 30,000 enteros aleatorios de 64 bits en un segundo. Darle semiprimes de 64 bits (19-20 dígitos), los ejemplos más difíciles, lo lleva a 500 por segundo. Factorizar números de 40 dígitos lleva más tiempo, pero aún así es bastante fácil para la mayoría de los programas. 80 dígitos se están volviendo interesantes, 110 dígitos son desafiantes pero prácticos. 150 dígitos es un gran esfuerzo. Es probable que 200 dígitos requieran que varias máquinas funcionen durante mucho tiempo, y mucho más que eso actualmente no es práctico.

Answer 2

La factorización es uno de los problemas “difíciles” por excelencia de la informática. No hay forma de hacerlo rápidamente. Si lo descubrieras, probablemente te convertirías en uno de los científicos informáticos más famosos de la historia y, como otro usuario mencionó, invalidaría la mayoría de los protocolos criptográficos disponibles en la actualidad.

Answer 3

Si puede hacerlo, puede romper la mayoría de los sistemas de cifrado que protegen las transacciones financieras y la inteligencia militar.

Answer 4

Mirando el número, el método más fácil y posiblemente más rápido es un árbol de factores. Básicamente está dividiendo el número. P.ej. Digamos que 72 es tu número. Puedes dividir 72 en 8 x 9. Luego puedes dividirlo ya que los factores primos de 8 son 2 x 2 x 2. Los factores de 9 son 3 x 3. Por lo tanto, los factores primos de 72 son 3 x 3 x 2 x 2 x 2

Answer 5

La buena manera es por factorización prima y ninguna otra es más simple que eso