En la \u00faltima clase vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en $\\mathbb{Z}_n$. Este teorema ten\u00eda un antecedente, que se conoce como el Teorema peque\u00f1o de Fermat:<\/p>\n
\nSi $a,p\\in\\mathbb{Z}$ con $p$ primo y $p$ no divide a $a$, entonces $$a^{p-1}\\equiv 1(p)$$<\/p>\n<\/blockquote>\n
Consecuentemente si dado un n\u00famero $n$ que no divida a $a$ se cumple $$a^{n-1}\\not\\equiv 1(n)$$
\nimplicar\u00eda que $n$ no es primo, pues de lo contrario incumplir\u00eda el Teorema peque\u00f1o de Fermat.<\/p>\nPues bien, este resultado lo podemos utilizar para chequear si un n\u00famero es primo. Este test se denomina test de primalidad de Fermat.<\/p>\n
Disponemos de un resultado que nos garantiza si un n\u00famero es primo, el Teorema de Wilson:<\/p>\n
\nEl n\u00famero $n\\in\\mathbb{Z},\\, n>1$ es primo si, y s\u00f3lo, si $$(n-1)!\\equiv -1(n)$$<\/p>\n<\/blockquote>\n
El problema es el c\u00f3mputo del factorial que es trem\u00e9ndamente costoso para n\u00famero muy grandes. Por ese motivo utilizamos los test de primalidad.<\/p>\n
Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un n\u00famero de entrada $n$, no consigue verificar la hip\u00f3tesis de un teorema cuya conclusi\u00f3n es que $n$ es compuesto.<\/p>\n
El test de Fermat nos propone buscar si un n\u00famero es compuesto probando las igualdades $$2^{n-1}\\equiv 1(n),$$ $$3^{n-1}\\equiv 1(n),$$ $$5^{n-1}\\equiv 1(n),…$$ $$a^{n-1}\\equiv 1(n),$$ hasta encontrar un valor de $1<a<n$ para el que no se cumpla.<\/p>\n
Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos n\u00fameros de Carmichael, o pseudoprimos.<\/p>\n
Hay m\u00e1s test de este tipo, son conocidos como test probabil\u00edsticos de primalidad, pues no nos garantizan que es primo; m\u00e1s bien ofrecen una probabilidad de que sea primo.<\/p>\n
El test de Fermat puede mejorarse utilizando el criterio de Euler:<\/p>\n
\nSi $p\\in\\mathbb{Z}$ es primo y $p$ no divide a $a$, entonces $$a^\\frac{p-1}{2}\\equiv 1(p)\\, \\mbox{ \u00f3, } a^\\frac{p-1}{2}\\equiv -1(p)$$<\/p>\n<\/blockquote>\n
El test probabil\u00edstico de primalidad m\u00e1s utilizado es el de Rabin-Miller, basado en el resultado:<\/p>\n
\nSea $p\\in\\mathbb{Z},\\, p>1$ primo impar y $k,m\\in\\mathbb{Z}$, tales que $p-1=2^km$, com $m$ impar. Entonces, para todo entero positivo $a$, menor que $p$, se cumple al menos una de los siguientes resultados:<\/p>\n
\n
- Alg\u00fan n\u00famero de la serie $a^{2^km},a^{2^{k-1}m},…,a^{m}$ es congruente con -1 m\u00f3dulo $p$.<\/li>\n
- $a^m\\equiv 1(p)$<\/li>\n<\/ul>\n<\/blockquote>\n