¿Por qué la factorización de un número es difícil en comparación con el de averiguar si es primo (que se puede hacer en el polinomio de tiempo) ?
Yo creo que podría ser de dificultad similar en términos de complejidad computacional.
Respuesta
¿Demasiados anuncios?
¿Por qué hemos de esperar que las pruebas de primalidad a ser más fácil que la factorización?
Recordemos Fermat Poco y Teorema de tratar a base de una prueba de primalidad . Esta prueba no siempre funciona, pero se sugiere la diferencia entre las pruebas de primalidad y factorización.
Deje $p$ ser una de las primeras. Supongamos que $a$ $p$ han máximo común divisor $(a,p)=1$. Entonces $$ a^{p-1} \equiv 1 \mod p. $$
Este cálculo se puede realizar de forma rápida el uso repetido el cuadrado y el hecho de que podemos trabajar $\mod p$, en lugar de tener que calcular el (muy grande) número de $a^{p-1}$.
Por ejemplo, $59$ es primo, y $2^{58} \equiv 1 \mod 59$. Si no ya lo hicimos saber que $59$ es primo, obtener la respuesta 1 aquí sugiero fuertemente (pero no demostrar) de que es un primo.
Otro ejemplo, $63$ no es primo, y $2^{62} \equiv 4 \mod 63$. Si no ya lo hicimos saber que $63$ es compuesto, este cálculo sería suficiente para demostrar que el $63$ es compuesto. Sin embargo, no nos dice lo que la factorización es.
Este es un ejemplo de cómo se puede comprobar la primalidad pero sin encontrar la factorización. Podríamos intentar el cálculo de $a^{n-1} \mod n$ para diferentes valores de $a$. Si queremos obtener una respuesta que no es $1$, se sabría de inmediato que $n$ es compuesto. Si queremos obtener la respuesta $1$ cada vez, entonces podríamos crecer cada vez más seguros de que $n$ es primo.
Lo que acabo de describir no es un buen primalidad de la prueba; los números de Carmichael (por ejemplo 561) tonto. Pero demuestra la idea de que uno puede averiguar algo acerca de primalidad mientras no averiguar cuáles son los factores. Una idea aquí es que el $\mathbb Z/n\mathbb Z$ (los enteros considera modulo n) tiene una estructura diferente dependiendo de si $n$ es primo o compuesto. Hay cosas (como el de arriba primalidad de Fermat prueba) que nosotros podemos hacer para distinguir entre estas diferentes estructuras. De esta manera, podemos aprender que un número es compuesto sin encontrar su factorización.
