¿Es la siguiente una afirmación correcta para la prueba de primalidad de Fermat?
Para todos $b$ si
- $n$ es primo y
- $(b,n)=1$
entonces $b^{n-1} \equiv 1 \bmod{n}$ .
El contrapositivo es si $b^{n-1} \not \equiv 1 \bmod{n}$ entonces la condición (1) y/o (2) es falsa (son equivalentes -ambas atestiguan $n$ no ser primo).
No, no lo es, es una declaración correcta de la prueba que comprueba si $n$ es un número primo o un número de Carmichael. Eso es algo sutilmente diferente.
Desde un punto de vista teórico, no importa si $b < n$ o no. Por ejemplo, $$b^{n - 1} \equiv (n + b)^{n - 1} \pmod n.$$ Lo mismo ocurre con $2n + b$ , $3n + b$ etc.
Desde un punto de vista práctico, tienes que poder decirle a tu algoritmo que se detenga en algún lugar. $n - 1$ puede no ser el punto óptimo para detenerse, pero es mucho mejor que el número más grande que pueda manejar, por ejemplo, para probar $561$ es mejor detenerse en $560$ que en $2^{31} - 1$ .
Entonces su algoritmo va a probar cada $b$ de $2$ a $n - 1$ . Sin embargo, tiene la condición de $(b, n) = 1$ en el momento de escribir este artículo. Así que si $n$ es compuesto, entonces la prueba tal y como la escribiste originalmente requiere que nos saltemos $b$ tal que $\gcd(b, n) > 1$ aunque $b < n$ .
Tampoco ha dicho que se salte $b$ se sabe que son compuestos, al menos no en el enunciado original de su pregunta.
Por lo tanto, lo que tienes es una prueba que devuelve true si $n$ es primo o un número de Carmichael (véase OEIS de Sloane ).
Pero como los números de Carmichael son relativamente raros, si un número grande (como un primo cercano al mayor primo de Mersenne conocido) es un pseudoprimo de Fermat para un montón de pequeños $b$ , es puede ser un número primo después de todo.
Si no se requiere que la prueba sea definitiva, entonces, bueno, um, tal vez.
Sin embargo, para que sea práctico, yo cambiaría "todo $b$ " a "todos $1 < b < n$ ". Evidentemente, $n^{n - 1} \equiv 0 \bmod n$ . Dado que esta prueba implica la exponenciación, querría evitar tener que hacer más multiplicaciones de las necesarias.
Intentemos $n = 341$ . Está claro que 341 es un número impar. Tanto Wolfram Mathematica como Wolfram Alpha nos dicen fácilmente que $2^{340} \equiv 1 \bmod 341$ . Igualmente vemos que con una raíz digital de base 10 de 8, 341 no es divisible por 3 sino $3^{340} \equiv 56 \bmod 341$ . En efecto, $341 = 11 \times 31$ . Parece que la prueba funciona.
Pero no nos conformemos con una carrera exitosa. ¿Qué tal si $n = 561$ ? No voy a sacar esa cifra de un sombrero. Se ha sacado de uno de los comentarios.
Bien, entonces 561 es también impar, y vemos que $2^{560} \equiv 1 \bmod 561$ . Con una suma de dígitos de 12, vemos que 561 es divisible por 3, así que nos saltamos el 3 y pasamos al 4. Vemos que $4^{560} \equiv 1 \bmod 561$ lo que significa que el...
¡Oye, espera un momento! Si 561 es divisible por 3, ¿puede ser primo? No, es compuesto. De hecho $3^{560} \equiv 375 \bmod 561$ . Pero usted encontrará que si $b$ no es divisible por 3, 11 o 17, entonces $b^{560} \equiv 1 \bmod 561$ .
Por eso el 341 se llama pseudoprimo de base 2 y algunos otros, y el 561 se llama pseudoprimo de bases 2, 4, 5, 7, 8, 10, 13, 14, etc.
Esto significa que la prueba de primalidad de Fermat no es fiable por sí misma, da muchos pequeños falsos positivos. Sin embargo, si para un número impar grande puedes descartar muchos primos pequeños (como 3, 11, 17) como factores primos con la división de prueba, y es un pseudoprimo para muchas bases pequeñas, eso podría ser una indicación de primalidad lo suficientemente buena para tus propósitos.
Por cierto, PrimeQ en Wolfram Mathematica tampoco es definitivo. Pero nadie ha encontrado todavía un falso positivo, y quizás nadie lo haga nunca.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
