5.3: Teorema pequeño y pruebas de primalidad de Fermat
- Page ID
- 111493
El teorema de Euler tiene muchas otras consecuencias importantes. Implica lo que se conoce como pequeño teorema de Fermat, aunque no fue probado por el propio Fermat, ya que, como escribe en la carta en la que afirmaba el resultado, temía “pasar demasiado tiempo”. No es un caso aislado, ¡aparecería!
Corolario 5.8 (Pequeño teorema de Fermat)
Si\(p\) es primo y\(\gcd(a, p) = 1\), entonces\(a^{p-1} = _{p} 1\).
Esto se desprende del teorema de Euler al darse cuenta de que para un primo\(p\),\(\varphi (p) = p-1\). Existe una formulación equivalente que permite\(p\) ser un divisor de\(a\). A saber, si\(p\) es primo, entonces\(a^{p} = _{p} a\). Observe que si\(p | a\), entonces ambos lados son congruentes con\(0\).
Los primos son de gran valor teórico y práctico (piense en el cifrado, por ejemplo). Por lo tanto, los algoritmos para pruebas de primalidad son muy útiles. La prueba más sencilla para averiguar si algún número grande\(\sqrt{n}\) es primo, consiste por supuesto en aplicar alguna versión del tamiz de Eratóstenes a los enteros positivos menores o iguales a\(n\). Por el teorema del número primo (Teorema 2.21), esto dará en el orden de\(\frac{2\sqrt{n}}{ln n}\) los primos. Entonces divide\(n\) por todos estos números. Esto asumirá el orden de\(\frac{2\sqrt{n}}{ln n}\) las divisiones.
Otra posibilidad es usar lo contrario del pequeño teorema de Fermat (Corolario 5.8). Si\(n\) y\(p\) son primos distintos, eso lo sabemos\(p^{n-1} = _{n} 1\). La prueba de primalidad de Fermat para\(n\) consiste en probar por ejemplo si\(2^{n-1} = _{n} 1\). Sin embargo, ¡lo contrario del pequeño teorema de Fermat no es cierto! Entonces aunque\(2^{n-1} = _{n} 1\), podría ser que no\(n\) es primo; discutiremos esta posibilidad al final de esta sección. Resulta que las pruebas de primalidad a través del pequeño teorema de Fermat se pueden hacer mucho más rápido que el método ingenuo, siempre que se utilicen algoritmos de exponenciación modular rápidos. Ilustramos brevemente esta técnica computando\(11^{340}\) módulo\(341\).
Se inicia expandiendo\(340\) en base\(2\) como se hizo en el ejercicio 3.18, donde se demostró que ésta adquiere el orden de divisiones\(\mbox{log}_{2} 340\) (largas).
\[340 = 170 \cdot 2+\textbf{0} \nonumber\]
\[170 = 85 \cdot 2+\textbf{0} \nonumber\]
\[85 = 42 \cdot 2+\textbf{1} \nonumber\]
\[42 = 21 \cdot 2+\textbf{0} \nonumber\]
\[21 = 10 \cdot 2+\textbf{1} \nonumber\]
\[10 = 5 \cdot 2+\textbf{0} \nonumber\]
\[5 = 2 \cdot 2+\textbf{1} \nonumber\]
\[2 = 1 \cdot 2+\textbf{0} \nonumber\]
\[1 = 0 \cdot 2+\textbf{1} \nonumber\]
Y así
\[\begin{array} {cc} {340 = 101010100}&{\mbox{in base } 2} \nonumber \end{array}\]
A continuación, computa una tabla de potencias\(11^{2^{i}}\) módulo\(341\), como se hace a continuación. Al hacer esto de abajo hacia arriba, esto se puede hacer usando muy pocos cálculos. Por ejemplo, una vez que se\(11^{8} = _{341} 143\) ha establecido, el siguiente arriba se encuentra por\(143^2\) módulo de computación\(341\), que da\(330\), y así sucesivamente. Entonces esto toma sobre\(\mbox{log}_{2} 340\) multiplicaciones.
\[\begin{array}{ll} {1}&{11^256 = _{341} 330}\\ {0}&{11^128 = _{341} 143}\\ {1}&{11^{64} =_{341} 319}\\ {0}&{11^{32} = _{341} 121}\\ {1}&{11^{16} = _{341} 330}\\ {0}&{11^8 = _{341} 143}\\ {1}&{11^4 = _{341} 319}\\ {0}&{11^2 = _{341} 121}\\ {0}&{11^1 = _{341} 11} \end{array}\]
La primera columna de la tabla así obtenida ahora nos dice qué coeficientes en la segunda necesitamos para calcular el resultado.
\[11^{340} = _{341} 330 \cdot 319 \cdot 330 \cdot 319 = _{341} 132 \nonumber\]
Nuevamente, esto no toma más que\(\mbox{log}_{2} 340\) multiplicaciones. Así, en conjunto, para un número\(x\) y un cálculo en base\(b\), esto toma el orden de\(2 \mbox{log}_{b} x\) multiplicaciones más\(\mbox{log}_{b} x\) divisiones. Para grandes números, esto es mucho más eficiente que el\(\sqrt{x}\) del método ingenuo.
El inconveniente es que podemos obtener falsos positivos.
Definición 5.9
El número\(n \in \mathbb{N}\) se llama pseudoprimo a la base a if\(\gcd (a, n) = 1\) y\(a^{n-1} = _{n} 1\) pero no obstante\(n\) es compuesto. (Cuando la base es\(2\), la cláusula a la base a menudo\(2\) se deja caer.)
Algunos números pasan todas las pruebas a cada base y siguen siendo compuestos. Estos se llaman números de Carmichael. El número más pequeño de Carmichael es 561. Se ha demostrado [7] que hay infinitamente muchos de ellos.
Definición 5.10
El número\(n \in \mathbb{N}\) se llama número Carmichael si es compuesto y es un pseudoprimo para cada base.
El pseudoprimo más pequeño es\(341\), porque\(2^{340} = _{341} 1\) mientras\(341 = 11 \cdot 31\). En este caso, todavía se puede demostrar que no\(341\) es un primo usando una base diferente\(3^{340} = _{341} 56\). Por el pequeño teorema de Fermat,\(341\) no puede ser primo.
La razón por la que el método esbozado aquí sigue siendo útil es que los pseudoprimos son mucho más raros que los primos. El número a continuación\(2.5 \cdot 10^{10}\) contiene en el orden de\(10^{9}\) los primos. Al mismo tiempo, este conjunto contiene sólo\(21853\) pseudoprimos al primo\(2\). Solo hay\(1770\) enteros por debajo\(2.5 \cdot 10^{10}\) que son pseudoprimos a la base\(2, 3, 5\), y\(7\). Por lo tanto, si un número pasa estas cuatro pruebas, es abrumadoramente probable que sea un primo.