Factorización de números primos: ¿la forma más fácil?

Question

Para la factorización de primos, ¿hay otra forma de hacerlo, distinta de dividir el número por una serie de primos (empezando por el más pequeño)?

¿No podríamos también elegir la misma serie de primos y multiplicarlos de alguna manera hasta obtener el número objetivo?

Está claro que cualquier enfoque implicará muchos cálculos, pero algunas formas podrían ser más difíciles que otras, ¿no?

¿Existe un nombre para una multiplicación exploratoria para intentar alcanzar un número?

Estoy especialmente interesado en hacer esto con números grandes. Está claro que encontrar los factores primos de 24 o 32 es una tarea fácil en ambos sentidos (dividiendo o multiplicando). Pero con cosas como 598703019332, ¿sería factible en absoluto?

Answer 1

"¿Existe un nombre para una multiplicación exploratoria para intentar alcanzar un número?"

Sí, se llama factorización de enteros, y ha recibido mucha atención desde la antigüedad, pero aún más en las últimas décadas, ya que ha cobrado importancia práctica. Sólo tienes que buscar en Google, encontrarás más información sobre ella de la que probablemente quieras.

Answer 2

Una implementación eficiente de esta "multiplicación exploratoria" podría llevarse a cabo mediante árboles de restos, véase [1]. Esto podría ser realmente útil para algunos tipos de números de hasta unos 20 dígitos, aunque para la mayoría de los números de ese tamaño las técnicas ordinarias (división de prueba, SQUFOF y rho) serán superiores.

[1]: Daniel J. Bernstein, La multiplicación rápida y sus aplicaciones , Teoría algorítmica de los números (2008), editado por Buhler y Stevenhagen, pp. 325-384.