No soy matemático de profesión, así que pido disculpas si esta es una pregunta poco clara. Me doy cuenta de que actualmente no existe tal algoritmo, pero estoy tratando de entender cómo sería un algoritmo de factorización de primos en tiempo polinómico. Mi opinión actual es que un algoritmo de este tipo tardaría menos del doble de tiempo en factorizar un número dos veces más grande, y en cambio se escalaría linealmente en relación con la longitud de bits de la entrada. Así, por ejemplo, un algoritmo que realizara una única operación simple en cada número menor que $n(x)$ no cumplirá este criterio, incluso si $x$ es una fracción muy pequeña, como tampoco lo sería una que sólo necesitara realizar la raíz cúbica de $n$ operaciones. ¿Estoy en el camino correcto?
Respuestas
¿Demasiados anuncios?
Lo que has descrito es un algoritmo de tiempo lineal. Eso ya es bastante rápido (dependiendo del problema). En un algoritmo de tiempo polinómico, el tiempo necesario para los cálculos crece polinómicamente en el tamaño de la entrada. Por ejemplo, con un tiempo de ejecución $\mathcal{O}(x^2)$ , obtendríamos como máximo cuatro veces el tiempo de ejecución al duplicar el tamaño de la entrada, nueve veces el tiempo al triplicar el tamaño, etc.
Tienes razón, un algoritmo de tiempo lineal, es decir $\mathcal{O}(x)$ para la factorización es bastante improbable. Pero tal vez hay un algoritmo que toma, digamos, $\mathcal{O}(x^{100})$ . Este algoritmo no sería realmente aplicable en la práctica en los ordenadores actuales, pero sería un algoritmo de tiempo polinómico y, por tanto, de gran interés teórico.
Hay varias capas de tiempo de ejecución posibles.
Un algoritmo de tiempo exponencial sería aquel que tarda $x$ veces más tiempo para factorizar un número que es el doble de grande, para alguna constante $x>1$ . Usted menciona $x=2$ pero en realidad deberíamos esperar algo mucho más pequeño que esto - incluso la división de prueba sólo multiplica por $x=\sqrt 2$ porque el número máximo de ensayos que necesita para factorizar $n$ se trata de $\sqrt n$ (si se factoriza, uno de los factores debe ser menor que la raíz cuadrada). Y sí, tu ejemplo de raíz cúbica también sería exponencial, con $x=\sqrt[3] 2$ . Los algoritmos de tiempo exponencial se vuelven muy lentos muy rápidamente.
Un algoritmo de tiempo polinómico se ejecuta en un tiempo que es una función polinómica del número de bits (o equivalentemente dígitos), no necesariamente lineal. Tiempo par $b^{100}$ es polinómico - y será mucho más rápido que $x^b$ para números suficientemente grandes.
En realidad, los algoritmos de factorización más rápidos que se conocen están entre los dos: el tiempo de ejecución real se describe mediante una función inusual que será mucho más lenta que la polinómica pero mucho más rápida que la exponencial. Un ejemplo de esta función es $2^{\sqrt{b}}$ (la función real es bastante más complicada que esto).
La razón por la que esto es importante es que la seguridad informática depende del hecho de que es relativamente fácil encontrar dos números primos grandes y multiplicarlos juntos, pero (hasta donde sabemos) es difícil que alguien invierta este proceso. Pero esto tiene que ser así incluso si el enemigo que intenta revertir el proceso tiene un ordenador mucho más rápido que el tuyo, o incluso muchos ordenadores mucho más rápidos y mucho más tiempo para gastar, porque queremos ser capaces de hacer transacciones seguras en pequeños dispositivos que sean seguros contra ataques bien organizados. Para que los códigos que son fáciles de hacer en un ordenador pequeño sean difíciles de romper, incluso con enormes cantidades de recursos, necesitamos que los algoritmos para romperlos se vuelvan difíciles mucho más rápido: superpolinómicos frente a polinómicos.
Los principales sistemas criptográficos encontraron su resistencia en la dificultad para factorizar números grandes con la suficiente rapidez.
El tiempo de ejecución de los algoritmos no polinómicos está creciendo demasiado rápido para permitir un cálculo de este tipo en un tiempo razonable con las longitudes de clave actuales. (Incluso con longitudes de clave moderadas, el tiempo de factorización puede superar la esperanza de vida del universo).
El crecimiento no es tan explosivo con comportamientos polinómicos. De todos modos, los grados altos también son problemáticos.
$$\begin{matrix}n&n^2&n^{10}&2^n\\ 1&1&1&2\\ 2&4&1024&4\\ 3&9&59049&8\\10&100&10000000000&1024\\ 100&10000&100000000000000000000&1267650600228229401496703205376\end{matrix}$$
Algunos investigadores afirman que este límite puede romperse mediante el uso de los llamados "ordenadores cuánticos". Estos no funcionan mejorando la complejidad del algoritmo, sino proporcionando una potencia de cálculo "exponencial".
