MAD: Test de primalidad

En la última clase vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en $\mathbb{Z}_n$. Este teorema tenía un antecedente, que se conoce como el Teorema pequeño de Fermat:

Si $a,p\in\mathbb{Z}$ con $p$ primo y $p$ no divide a $a$, entonces $$a^{p-1}\equiv 1(p)$$

Consecuentemente si dado un número $n$ que no divida a $a$ se cumple $$a^{n-1}\not\equiv 1(n)$$
implicaría que $n$ no es primo, pues de lo contrario incumpliría el Teorema pequeño de Fermat.

Pues bien, este resultado lo podemos utilizar para chequear si un número es primo. Este test se denomina test de primalidad de Fermat.

Disponemos de un resultado que nos garantiza si un número es primo, el Teorema de Wilson:

El número $n\in\mathbb{Z},\, n>1$ es primo si, y sólo, si $$(n-1)!\equiv -1(n)$$

El problema es el cómputo del factorial que es treméndamente costoso para número muy grandes. Por ese motivo utilizamos los test de primalidad.

Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada $n$, no consigue verificar la hipótesis de un teorema cuya conclusión es que $n$ es compuesto.

El test de Fermat nos propone buscar si un número 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.

Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos números de Carmichael, o pseudoprimos.

Hay más test de este tipo, son conocidos como test probabilísticos de primalidad, pues no nos garantizan que es primo; más bien ofrecen una probabilidad de que sea primo.

El test de Fermat puede mejorarse utilizando el criterio de Euler:

Si $p\in\mathbb{Z}$ es primo y $p$ no divide a $a$, entonces $$a^\frac{p-1}{2}\equiv 1(p)\, \mbox{ ó, } a^\frac{p-1}{2}\equiv -1(p)$$

El test probabilístico de primalidad más utilizado es el de Rabin-Miller, basado en el resultado:

Sea $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:

  • Algún número de la serie $a^{2^km},a^{2^{k-1}m},…,a^{m}$ es congruente con -1 módulo $p$.
  • $a^m\equiv 1(p)$
Ejercicio: Verificar que 561 es un número de Carmichael
This entry was written by admin , posted on jueves abril 26 2018at 08:04 am , filed under Matemática Discreta . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Deja un comentario

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>