Depende.
Lo difícil de romper el crpyto actual es la factorización de números primos. Se sabe que este problema está en NP, pero nadie ha podido encontrar un algoritmo de tiempo polinómico (lo que demuestra que está en P). Tenga en cuenta que nadie ha podido demostrar que es NP-hard (y se cree que no lo es).
Digamos que alguien encontró un algoritmo de tiempo polinómico para un problema como SAT (todos los problemas en NP pueden reducirse a SAT), mostrando así P = NP. La forma en que eso afecta a la criptología depende del algoritmo ahora. Como es polinomial, su complejidad es [matemática] O (n ^ c) [/ matemática] (donde O es la notación O grande yn es la longitud de la entrada). Si c es pequeño (2,5,7 y así sucesivamente), tenemos un problema en criptología, ya que significa que los primos se pueden factorizar rápidamente. Si c es grande (nueve a la potencia de nueve a la potencia de nueve … cien veces) entonces es un resultado inútil para aplicaciones prácticas. Sí, es polinomial, pero el exponente es muy grande, aunque sea una constante.
- ¿Qué nivel de matemáticas necesito tener si quiero convertirme en un buen programador gráfico?
- ¿Cuál es la salida de un filtro Gabor?
- ¿Cuál es la interpretación de XOR de los enteros? ¿Hay alguna forma simple de calcular XOR en lugar de 'XOR-ing' todos los bits individuales?
- ¿Cuál es una explicación para esta ecuación de números de punto fijo con signo?
- Cómo imprimir dos variables enteras en la misma línea en Python
Digamos que alguien descubrió que no puede haber un algoritmo que resuelva todos los problemas en NP en tiempo polinómico, mostrando así P! = NP. Digamos que ha demostrado que lo más rápido que haremos para resolverlos es [matemática] O (2 ^ {n / 100}) [/ matemática]. Eso no es bueno si quieres romper la criptografía. Sí, es mucho mejor de lo que tenemos hoy en día, pero aumentar n cien veces nos lleva a donde estábamos. Digamos que muestra que el límite inferior para la complejidad de la velocidad de cualquier algoritmo que resuelva los problemas NP más difíciles es [matemática] O (2 ^ {\ log \ log \ log n}) [/ matemática]. Ahora esto es exponencial, pero espere un minuto … en realidad es mucho mejor que el algoritmo que realiza los pasos [math] \ leq d * n [/ math] (para algunos d razonablemente pequeños), ¡incluso para n grande!
Entonces depende de la prueba. Si hay una prueba. También es muy posible que P? = NP no se pueda probar con los axiomas que los científicos y matemáticos tienen actualmente.
