Barrapunto

Lo que dices es muy interesante. ¿Podrías dar algún ejemplo o al menos alguna pista sobre algoritmos con una complejidad de orden superior a los actuales? Supongo que no estamos hablando de criptografía de curva elíptica, sino de una serie de algoritmos que no sólo son NP completos sino que además su ruptura por fuerza bruta requiera muchísimos más cálculos que ahora (si no se encuentran atajos matemáticos claro). ¿Se podría lograr eso multiplicando por ejemplo más de dos números primos grandes? No se si los tiros van por ahí o tendríamos que buscar nuevos problemas matemáticos de naturaleza diferente (eso no creo que se encuentre con unos simples "cafetitos por la tarde" :-). Gracias por tu respuesta!

Multiplicar más de dos números primos no aumenta de forma exponencial la dificultad de factorizar dicho número, así que no, no soluciona nada una gran multiplicación muchos primos.... bueno espera, a menos que sean 2^n parejas de primos, entonces sí que tenemos nuestro querido problema de complejidad O(K^n^n) de una dirección. Claro que para usar este método necesitas un computador cuántico (única manera de realizar 2^n operaciones) pero, hey! se supone que ya lo tenemos, no?

Hombre, por unos "cafetitos" me refería al hecho de que un experto en teoría de números debería poder "complicar" un problema, en teoría lo difícil es _simplificar_ un problema.

Otra cosa es cuando el experto tenga un problema O(K^n^n) conseguir que sea de una dirección (osea, que ir de a->b tenga coste O(K) pero de b->a tenga coste O(K^n^n)... Eso es otro cantar.

En cualquier caso, ahora no se me ocurre ningún O(K^n^n) de una dirección que se pueda utilizar en un ordenador normal (no cuántico), pero es que no soy un experto en teoría de números y además me he quedado sin café jejeje ;-) Espero no haber puesto demasiada fe en los expertos en teoría de números :-P