Si alguien pudiera factorizar rápidamente los números primos, ¿cuáles serían las consecuencias?

Supongo que, como Michael Kamrath, te refieres a factorizar números compuestos en primos rápidamente.

Si “rápidamente” significa un cambio lineal, como un millón de veces más rápido que los mejores algoritmos ahora, no tendría un significado matemático profundo, aunque el método en sí podría ser una herramienta útil para otros problemas o conducir a otras ideas profundas. Haría que descifrar cosas y robar cosas protegidas por cifrado como Bitcoin sea más fácil, pero no necesariamente lo suficientemente fácil como para hacer una gran diferencia. Y las personas podrían ajustarse rápidamente usando claves más grandes o cambiando a otras formas de descifrado.

Si “rápidamente” significa un cambio en la tasa de que el problema se vuelve más difícil con teclas más grandes, y si la nueva tasa se limita por encima de un polinomio de grado finito, tendría profundas implicaciones matemáticas, porque significaría que todos los problemas computacionales podrían ser resuelto de tal manera, y probablemente estimularía una explosión de progreso matemático. Pero si hizo una diferencia práctica dependería de los parámetros. Es posible, pero no necesariamente cierto, que pueda hacer que descifrar las claves actuales sea lo suficientemente rápido como para importar, y es posible, pero no seguro, que también pueda derrotar claves más largas. Es posible, pero no seguro, que pueda vencer todas las formas de criptografía de clave pública, y tendríamos que volver a las claves compartidas a través de líneas de transmisión seguras.

Pero no tiene que resolver el problema general para tener los efectos prácticos. Es posible que pueda factorizar los tipos de números compuestos utilizados en algoritmos criptográficos, tal vez utilizando información de texto cifrado, sin saber cómo factorizar números compuestos en general.

Si quisieras “factorizar cualquier número dado en números primos”, nuestros sistemas bancarios tendrían que ser renovados. ¿Alguien sabe si la criptografía de curva elíptica es una alternativa?

En resumen, es mejor que confiemos el uno en el otro. Robar sería demasiado fácil. Supongo que las personas tendrían que dejar sus duffs y comenzar a comprar en persona nuevamente.

Me tientas, señor. Alguien, ¿es ilegal hacer una copia de la clave pública utilizada por mi banco?

Puedo factorizar números primos instantáneamente y el mundo no ha cambiado un poco. Solo dame cualquier primo, p, y te daré su factorización prima: también p.