¿por qué la factorización de enteros es un tiempo no polinomial?

Question

Soy solo un principiante de la informática. Aprendí algo sobre el tiempo de carrera, pero no puedo estar seguro de lo que entiendo es correcto. Entonces por favor ayudame

Por lo tanto, la factorización de enteros actualmente no es un problema de tiempo polinomial, pero sí lo es la prueba de primalidad. Suponga que el número que debe verificarse es n. Si ejecutamos un programa solo para decidir si cada número de 1 a sqrt (n) puede dividir n, y si la respuesta es sí, entonces almacena el número. Creo que este programa es un tiempo polinomial, ¿no?

Una posible forma en la que estoy equivocado sería un programa de factorización que debería encontrar todos los números primos, en lugar del primer primo descubierto. Entonces tal vez esta es la razón por la cual.

Sin embargo, en la criptografía de clave pública, encontrar un factor primo de un gran número es esencial para atacar la criptografía. Como generalmente un gran número (clave pública) es solo el producto de dos primos, encontrar un primo significa encontrar el otro. Esto debería ser un tiempo polinomial. Entonces, ¿por qué es difícil o imposible atacar?

Answer 1

Descripciones ocasionales de la complejidad como "factorización polinómica algoritmo "generalmente se refieren a la complejidad con respecto a la tamaño de la entrada, no a la interpretación de la entrada. Entonces, cuando la gente dice "sin algoritmo de factorización polinomial conocido", quiere decir que no existe un algoritmo conocido para factorizar N -bit números naturales que se ejecutan en polinomios de tiempo con respecto a N. No es un polinomio con respecto al número en sí, que puede ser hasta 2^N.

Answer 2

Si ejecutamos un programa solo para decidir si cada número de 1 a sqrt (n) puede dividir n, y si la respuesta es sí, entonces almacena el número.

Incluso haciendo caso omiso de que la prueba de la divisibilidad se necesitará más tiempo para los números más grandes, este enfoque tiene casi el doble de tiempo si usted acaba de añadir un solo dígito (binario) a n. (En realidad, tomará el doble de tiempo si agrega dos dígitos)

Creo que es la definición de tiempo de ejecución exponencial: hacer n un bit más largo, el algoritmo toma el doble de tiempo.

Pero tenga en cuenta que esta observación se aplica solo al algoritmo que ha propuesto. Todavía no se sabe si la factorización de enteros es polinómica o no. Los criptógrafos seguramente esperan que no lo es, pero también hay algoritmos alternativos que no dependen de que la factorización prima sea difícil (como la criptografía de curva elíptica), por las dudas ...

Answer 3

La dificultad de la factorización es uno de esos hermosos problemas matemáticos que es simple de entender y lo lleva inmediatamente al borde del conocimiento humano. Para resumir (el conocimiento de hoy) sobre el tema: no sabemos por qué es difícil, no con ningún grado de prueba, y los mejores métodos que hemos ejecutado en más tiempo polinomial (pero también significativamente menos que el tiempo exponencial). El resultado de que primality testing es par en P es bastante reciente; ver la página de Wikipedia vinculada.

La mejor explicación heurística que conozco para la dificultad es que los números primos se distribuyen aleatoriamente. Uno de los resultados más fáciles de entender es Dirichlet's theorem. Este teorema dice que cada progresión aritmética contiene infinitos primos, en otras palabras, puedes pensar en primos como densos con respecto a las progresiones, lo que significa que no puedes evitar toparte con ellos.Esta es la más simple de una colección bastante grande de tales resultados; en todos ellos, los primos aparecen de formas análogas a los números aleatorios.

La dificultad de factorizar es, por lo tanto, análoga a la imposibilidad de invertir un pad de una sola vez. En una plataforma única, hay un poco que no sabemos XOR con otro que no conocemos. Obtenemos información cero sobre un bit individual que conoce el resultado del XOR. Reemplace "bit" con "prime" y la multiplicación con XOR, y tendrá el problema de factoraje. Es como si hubieras multiplicado dos números aleatorios juntos, y obtienes muy poca información del producto (en lugar de información cero).