¿Por qué es más rápido en primer lugar comprobar si un número es un pseudoprime de dividir un número por todos los números enteros de hasta, pero no incluyendo, ese número?

Question

El Oxford Conciso Diccionario de Matemáticas define un pseudoprime como cualquier número $n$ que satisface la condición de $a^n = a \pmod n$ "para todos los enteros $a$". Para encontrar un pseudoprime, tenemos que ir sobre la iteración de cada número entero menor que $n$, al menos hasta que llegamos al punto donde podemos estar seguros de que ninguno de los números que siguen son factores de $n$. Entonces, si queremos estar seguros de que el número que tenemos es un primo, todavía tenemos que dividir ese número por cada uno de los mencionados números enteros.

¿No sería más fácil poner a prueba cada uno de los n el "grado de la escuela"?

Edit: me refiero a que, si hacemos todo esto en un equipo, no puede haber mucha diferencia entre las dos pruebas.

Answer 1

Digamos que había un número $n$ de tamaño aproximadamente $10^{100}$. Para la prueba de primalidad por la división de juicios, tendríamos que dividir por todos los números primos hasta alrededor de $10^{50}$ (si el número es en realidad prime). De acuerdo con el Teorema de los números Primos hay alrededor de $\frac{10^{50}}{\ln\left(10^{50}\right)}\approx 8.7\times10^{47}$ prepara para tratar de dividir por.

Por otro lado, un pseudoprime prueba con la base de $b$ requiere calcular el mínimo no negativo de los residuos de $b^{n-1}\pmod{n}$. El uso de un sucesivas cuadratura del algoritmo, esto sólo toma alrededor de $335$ squarings (para nuestro número en el rango de $10^{100}$), multiplicaciones, modular y la reducción de pasos (cada uno de estos pasos se lleva a unos cuantos ... acerca de $5$--multiplicaciones y divisiones). Así que eso es $1700$ multiplicaciones y divisiones, en comparación con $10^{47}$ multiplicaciones y divisiones para la comprobación de un primer ensayo de la división.

Para un equipo que, de la verificación de un alojamiento en el rango de $10^{100}$, lleva para siempre (bueno, no literalmente, pero más que la edad del universo); mientras que el pseudoprime prueba se puede hacer en cuestión de segundos (tal vez menos de un segundo).

Answer 2

Permítanme señalar la falsedad de la última declaración en la cuestión, afirmando que "si queremos estar seguros de que el número que tenemos es un primo, todavía tenemos que dividir ese número por cada uno de los mencionados números enteros."

Prueba de la división es no es la única forma de verificar si un número es primo, y no es la forma más eficiente para grandes enteros. Prueba de la división para el prime $n$ requiere entero divisiones hasta el $\lfloor \sqrt n \rfloor$. A partir de una complejidad perspectiva este es un número exponencial de las operaciones en términos del tamaño de la entrada (el tamaño de bits de $n$ o $\log_2 n$).

Es conocido que existen polinomio de tiempo de algoritmos deterministas para comprobar la primalidad. Ver los números Primos es en P: Un Breakthough para el "hombre común".

Para todos los efectos prácticos, el problema de la primalidad de pruebas que pueden ser abordados por una ligera variación de la pseudoprime de prueba mencionados en la Pregunta, a saber, la fuerte pseudoprime de prueba para un número suficiente de relativamente primer bases.

Esto es fácil de implementar. Si $n$ falla un fuerte pseudoprime prueba para cualquier base, es sin duda compuesto (y tal base se llama un "testigo" para el compositeness de $n$).

Si probabilística de la prueba (de precisión arbitraria) es satisfactorio, debido a que un número compuesto $n$ falla la fuerte pseudoprime de prueba de por lo menos tres cuartas partes de las bases coprime a$n$$1$$n$, la probabilidad de que un compuesto $n$ pass $k$ de estas pruebas para las bases elegido al azar es (conservadoramente) menos de $2^{-2k}$. Por lo tanto podemos controlar la manera en pequeñas queremos aprovechar la oportunidad que "probablemente el primer" está realmente compuesto.

Esto también puede ser considerado como un determinista de verificación, cuya suficiencia depende de una Extendida Hipótesis de Riemann (ERH), lo que implica la base más pequeña para que un compuesto $n$ falla la fuerte pseudoprime prueba es en la mayoría de las $2 (\ln n)^2$. De ello se sigue que si ERH es cierto, entonces primalidad se puede comprobar de forma determinista por no más de que muchos de los fuertes pseudoprime pruebas, lo que significa que la totalidad de la prueba tiene la complejidad de la $O((\ln n)^3)$. Para más detalles, ver los Miller-Rabin prueba de primalidad.

---

Añadido: La descripción de la prueba de la división implícita en el título de la Pregunta también es demasiado pesimista. Si $n$ es un compuesto natural de número, pero un primer factor será en la mayoría de las $\sqrt n$, así que vamos a tratar de dividir (en el peor de los casos) por números enteros hasta ese límite (no "por todos los números enteros de" menos de $n$).

De hecho, no necesitamos tratar de dividir por cada entero a a $\sqrt n$ porque si $k$ no divide $n$, ni más múltiplos de $k$. En particular, una vez que se sabe que $2$ no divide $n$, no tenemos necesidad de comprobar la divisibilidad por más números enteros. Llevado al extremo, esto significa que sólo se necesita trate de dividir a $n$ por un conjunto de "juicio divisores" $k$ que contiene todos los números primos que no exceda $\sqrt n$.