¿Por qué es importante en la práctica demostrar la hipótesis de Riemann?

Question

Estoy de acuerdo en que estudiar matemáticas puras tiene sentido por la propia curiosidad intelectual.

Sin embargo, después de descubrir el algoritmo AKS, me surge una pregunta: "¿Sigue siendo importante en la práctica la hipótesis de Riemann después de descubrir el algoritmo AKS?".

Leí dos libros de texto no formales "La obsesión de los primos" y "La música de los primos".

Esos libros se publicaron antes del descubrimiento del algoritmo AKS.

Resumiendo la importancia de demostrar la hipótesis de Riemann en esos libros es "Si la hipótesis de Riemann es cierta, el algoritmo de Miller-Rabin se convirtió en determinista de tiempo poli O(bit $^4$ ). Y es muy útil para fortificar RSA mediante el aumento de bits.

Pero tengo dos dudas:

El algoritmo AKS es también un algoritmo poli primo determinante con O(bit $^{12}$ ). Es más lento que Miller-Rabin pero es poli-tiempo sin ninguna suposición y probablemente la complejidad de tiempo puede ser reducida. Miller-Rabin sigue siendo fuerte sin hipótesis de Riemann porque puede responder "es un compuesto" con probabilidad 3/4 en cada iteración si es un número compuesto. Estoy de acuerdo en que tiene una vulnerabilidad crucial: Miller-Rabin puede ser falso negativo.

RSA es prácticamente robusto (seguridad no demostrada pero inquebrantable) y puede utilizar la firma digital. Sin embargo, hay criptosistemas combinatorios (y todavía se están sugiriendo muchas cosas) que no utilizan la teoría de números, como el número primo. (Pero algunas criptografías, como Merkle-Hellman, no funcionan).

Entonces, ¿sigue siendo importante en la práctica demostrar la hipótesis de Riemann?

Answer 1

En la práctica es tan importante como antes, ya que el AKS es poco práctico para los grandes números que requiere la seguridad.

El algoritmo AKS es un "algoritmo galáctico", y por tanto no se utiliza en la práctica... no es práctico para números grandes. Es un resultado teórico enorme, pero no "prácticamente importante" en términos de cifrado. Por lo tanto, si la prueba de la HR era prácticamente importante antes, entonces sigue siendo prácticamente importante hoy en día. Los algoritmos de prueba de primos que se utilizan ahora en la práctica son los mismos que antes, y siguen dependiendo de que la HR sea cierta.

Dicho esto, las pruebas matemáticas sólo tienen importancia práctica para otros problemas matemáticos, no para cuestiones de confianza, que es la seguridad. El cifrado es una cuestión de confianza, que no depende de la posibilidad de que se rompa (prueba), sino de la practicidad de que se rompa (probabilidad).

Sin embargo, cómo definir la importancia práctica que tenía antes es una cuestión de pensamiento filosófico. Pero desde el punto de vista fáctico... su importancia no ha cambiado.