¿Qué sucede si alguien descubre un algoritmo de tiempo polinómico para problemas de factorización de enteros?

Answer 1

El algoritmo RSA funciona porque no existe un algoritmo de tiempo polinómico para la factorización de enteros. Ahora, imagina que si alguien encuentra el algoritmo de tiempo polinómico, pueden ocurrir las siguientes cosas:

1. El HTTPS no funcionará. El hombre en el ataque del medio volverá a ser famoso. Entonces, la mayor parte de la vida en línea se perderá
2. No podríamos hacer transacciones sentados en casa.
3. No podemos disfrutar de las compras en línea en absoluto. A menos que exista algún protocolo nuevo.
4. Por otro lado, nos será posible disfrutar de la vida con mucha menos intervención de Internet.
5. Viviremos la era de Facebook detrás. Habrá más conversación en la vida real
6. Finalmente, los investigadores encontrarán una nueva tarea para diseñar una mejor técnica de encriptación

La vida cambiará drásticamente de cada individuo.

Answer 2

Recientemente hemos desarrollado un simulador cuántico de factoring publicado en PRL el año pasado. Bueno, de hecho, el resultado significa que dos electrones enredados en una trampa Penning tienen el espectro de los números primos si programa las frecuencias de su simulador con el número que desea factorizar. El resultado nuevamente muestra la misma complejidad que la de Shor, es decir, que solo se necesita un polinomio (logN) ^ 3 mediciones de energía para obtener un tamiz probabilístico cuántico. Subimos el resultado preliminar al arXiv. [1704.03174] Bell declara en una trampa de Penning como el simulador cuántico del problema de factorización de enteros. Actualmente, los números de hasta 10 ^ 20 pueden factorizarse con solo dos electrones enredados en una trampa de tamaño típico.

Answer 3

Déjame darte una opinión diferente.

Durante mucho tiempo se pensó que el problema de la originalidad estaba en P, pero no teníamos un algoritmo de tiempo polinomial determinista hasta que se descubrió AKS en 2002. ¿Qué impactos prácticos ha tenido? Ninguna. Claro que es tiempo polinómico, pero es realmente lento debido a un gran exponente y grandes constantes. Es de importancia lógica, y todavía ofrece algo de esperanza de que podamos encontrar mejoras, pero por ahora seguimos usando los algoritmos de tiempo polinomial no determinista que estábamos usando antes.

A diferencia de la primalidad, creo que nos inclinamos hacia la factorización de enteros que no es un problema de tiempo polinómico. Pero digamos que nos sorprendemos y encontramos un algoritmo. Del ejemplo anterior, es muy posible que no tenga ningún impacto que no sea ​​para las organizaciones de noticias y la interminable explicación que todos tendríamos que hacer. Al igual que algunos de los métodos de primalidad, nuestros mejores algoritmos de factorización actuales son el tiempo sub-exponencial. Por lo tanto, es posible que nuestro algoritmo de tiempo polinómico no se vuelva más rápido hasta que los tamaños de las claves sean miles de millones de órdenes de magnitud más grandes de lo que usamos actualmente, por lo que no tiene ningún uso práctico. Sin embargo, probablemente nos pondríamos bastante nerviosos, ya que la puerta está mucho más abierta para que alguien (por ejemplo, la NSA) oculte una mejor solución.

Por ejemplo, el algoritmo 1 no es tiempo polinomial. Tiene complejidad [matemática] O (\ log ^ {\ log \ log \ log n} (n)) [/ math]. El algoritmo 2 es el tiempo polinomial. Tiene complejidad [matemática] O (\ log ^ {8} (n)) [/ matemática]. El algoritmo 1, a pesar de no ser un tiempo polinómico, será más rápido que el algoritmo 2 para todos los tamaños de números que nos interesarían. Es decir, el punto de cruce está mucho más allá del punto de viabilidad computacional.

Answer 4

Entonces los criptosistemas como RSA que se basan en el problema de factorización de enteros serían inseguros. Los criptosistemas basados ​​en DLP (problema de registro discreto) no se verían afectados, es decir, DSA, ECDSA.