¿Cuál es la forma más rápida de encontrar divisores de enteros grandes?

Como alguien ya ha señalado, la factorización de enteros – página de Wikipedia cubre esta pregunta (si x es un divisor de un entero, entonces x es el producto de los factores del entero). Aun así, busqué la complejidad del tiempo para algunos de los algoritmos generales y los tracé.

Encontré estos resultados interesantes ya que difieren de los problemas con los números primos (un problema ligeramente diferente). Aquí está el código que generó las tramas.

#! / usr / bin / env python2
matemáticas de importación
importar matplotlib.pyplot como plt
importar numpy como np
operador de importación
if __name__ == “__main__”:
fig, ax = plt.subplots (2,1)
MIN = 0.0
MAX = 10.0 ** 250.0
t = math.pow (10,200) ** np.linspace (0.0, 2, 2000)
x = np.linspace (0.0, 20, 200)
O1 = 1
quadratic_sieve = np.e ** ((1 + O1) * np.sqrt (np.log (t) * np.log (np.log (t))))
continue_fraction_factorization = np.e ** (np.sqrt (2 * np.log (t) * np.log (np.log (t))))
vástagos = t ** 0.25
general_number_sieve = np.e ** (((64/9) ** (1.0 / 3.0) + O1) * (np.log (t) ** (1.0 / 3.0)) * (np.log (np.log ( t)) ** (2.0 / 3.0)))

para i en [0, 1]:
ax [i] .plot (t, quadratic_sieve, ‘c’, label = “Quadractic Sieve”)
ax [i] .plot (t, continue_fraction_factorization, ‘m’, label = “Factorización de fracción continua”)
ax [i] .plot (t, vástagos, ‘b’, etiqueta = “vástago”)
ax [i] .plot (t, general_number_sieve, ‘r’, label = “Tamiz de número general”)

tiradores, etiquetas = hacha [i] .get_legend_handles_labels ()
ax [i] .legend (maneja [:: – 1], etiquetas [:: – 1])
ax [i] .set_xscale (‘log’, basex = 10)
ax [i] .set_yscale (‘log’, basey = 10)
si i == 0:
ax [i] .set_xlim ([MIN, MAX])
ax [i] .set_ylim ([MIN, 10.0 ** 65])
más:
ax [i] .set_xlim ([MIN, 10.0 ** 16])
ax [i] .set_ylim ([MIN, 10.0 ** 16])

plt.show ()

En resumen, no existe un algoritmo “más rápido”. Algunos algoritmos son más eficientes en un contexto dado que otros.

Todo divisible por 1
Números pares divisibles por 2
Suma los números individuales. 42 sería cuatro más dos iguales a 6, si esta suma es divisible por 3, también lo es el número original. Divisible por 3
4 es solo un factor de 2
Divisible por 5 si el número termina en 5 o 0
Divisible por 6 si primero, divisible por 3, entonces, también debe ser divisible por 2
Divisible por 7, tome el último número del número y duplíquelo, reste el número que duplicó al número ahora truncado y reste el número duplicado. Si este nuevo número es divisible por 7, entonces también lo es el original. por ejemplo 777. 7 se duplica a 14, 77-14 = 63. Como 63 es divisible por 7, entonces también lo es el número original 777

Sí, hay varias formas mejores. Si desea código, puede mirar Sage, son de código abierto. Se basan en conceptos como seives cuadráticos y curvas elípticas.

Factorización entera

Depende de lo que quiera decir con “grande”. Para los números que tienen alrededor de 200 dígitos decimales o menos, existen técnicas prácticas para hacer esto (ver: Factorización de enteros – Wikipedia), pero para números más grandes, afortunadamente, no se conocen prácticas maneras de encontrar factores enteros de esos números. La mayoría de la seguridad digital se basa en que no se tienen en cuenta los enteros grandes. Este artículo incluye enlaces a algún software que es más eficiente que O (sqrt (n)): Tamiz de campo de número general – Wikipedia.

Es solo una idea, pero …

Encuentra todos los factores primos. No estoy seguro de cómo, pero no debería ser demasiado difícil.

Ahora, simplemente imprima el producto de todas las combinaciones posibles.

P.ej. 36 tiene los factores primos 2, 2, 3 y 3

Entonces los factores son:

• 2
• 2 × 2
• 2 × 2 × 3
• 2 × 2 × 3 × 3
• 2 × 3 × 3
• 2 × 3
• 3 × 3
• 3

Y por supuesto:

• 1

Tamiz de campo de número general – Wikipedia

Hay implementaciones en Python y algunas otras cosas.

Tiene la misma complejidad de tiempo de ejecución que probar si el número es primo, es O (sqrt (n))