¿Existe un algoritmo de factorización de tiempo lineal?

Answer 1

Ni siquiera cerca. Hay algoritmos simples que son O (sqrt (N)). Y hay algoritmos de factorización más rápidos. Curiosamente, todavía no sabemos cuál es el algoritmo de factorización más rápido.

Y esta es una parte importante de la teoría de números, porque si podemos factorizar números grandes rápidamente, algunas de nuestras técnicas de cifrado, como el algoritmo RSA, se romperán.

Por ejemplo, supongamos que generamos dos primos de 1000 dígitos, P1 y P2. Necesitaría saber algo de Matemática discreta para poder encontrar estos números primos, pero se puede hacer rápidamente.

Ahora calcule C = P1 * P2 y dele C a cualquier organización en el mundo.

C tendrá aproximadamente 2000 dígitos, lo que supera los 6000 bits.

Sin el conocimiento actual de factorización, el Sol se quemaría antes de que alguien pudiera factorizar C.

Si encuentra una forma de factorizar C rápidamente, avíseme. Haremos un montón de dinero vendiendo el algoritmo a la Agencia de Seguridad Nacional. Pero no le digas a nadie más, de lo contrario 1) Sin dinero, y 2) Estarías comprometiendo la seguridad de los Estados Unidos.

Answer 2

Si se refiere a ciencias de la computación, para tamaños de entrada lo suficientemente grandes, el tiempo de ejecución aumenta linealmente con el tamaño de la entrada. Por ejemplo, un procedimiento que suma todos los elementos de una lista requiere un tiempo proporcional a la longitud de la lista. Esta descripción es ligeramente inexacta, ya que el tiempo de ejecución puede desviarse significativamente de una proporcionalidad precisa, especialmente para valores pequeños de n . Esto va a la forma paralela de trabajar algunas máquinas. El concepto de tiempo lineal se utiliza en algoritmos de coincidencia de cadenas. Y creo que algunos componentes de hardware nunca pueden llegar esta vez.