Unidades en Zm

Denotamos por Um al conjunto de elementos invertibles de Zm.

Um es llamado por algunos autores como el conjunto reducido de residuos módulo m.

Cuando m es primo, todos los enteros {1,...,m-1} son invertibles en Zm, por lo tanto el cardinal |Um | = m-1

En Zm se cumple que:

La función φ de EulerBio

Se define la función φ de Euler con la función φ: N ⇒ N que a cada n le hace corresponder el número de enteros x (1<x<n), que son primos relativos con n, esto es, cuyo mcd(x,n)=1.

Siempre se cumple que φ(p)= |Up|

Así tenemos que φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2; φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6,...

Y cuando p es primo, φ(p) = p-1. Ejemplo: φ(17)=16.

Teoremas de Euler y de Fermat

El teorema de Euler

Si [a] ∈ Um entonces [a]φ(m) = [1] en Zm.

Por tanto, si un b ∈ Z verifica que mcd(m,b)=1 entonces bφ(m) ≡ 1 (mod m)

El Pequeño teorema de FermatBio

Si p es primo y p no divide a a entonces:

ap-1 ≡ 1 (mod p)

Números pseudoprimos

Si se cumpliese la implicación contraria en el teorema de Fermat (que si se cumpliere que ap-1 ≡ 1 (mod p) con a no múltiplo de p, entonces podría asegurarse que p es primo), tendríamos una forma inmediata de comprobar si un número dado es primo. Desgraciadamente, hay ciertos números compuestos que satisfacen el teorema de Fermat. A esta clase de números compuestos se la denomina números pseudoprimos.

Un ejemplo de número pseudoprimo es el 341=11.31, ya que se cumple que 2340 ≡ 1(mod 341). Para verificar el resultado de esa potencia, puede usarse el applet de exponenciación modular en esta nueva ventana

Test de primalidad y generación de números primos

Tests de primalidad

Para números muy grandes, como los usados en sistemas criptográficos como el RSA, que llegan a tener tamaños de entre 512 y 2048 bits, no es viable en un tiempo razonable el tratar de factorizar un número para saber si es o no primo. Pero existen métodos probabilísticos que nos pueden decir con un alto grado de certeza si un número es primo o compuesto. A estos métodos se les llama tests de primalidad.

El mismo teorema de Fermat nos proporciona un método probabilístico para ver si un número es primo o no. Si un número p satisface el pequeño teorema de Fermat es probable que sea primo, aunque como ya se ha visto no podemos estar seguros de ello, ya que hay números compuestos (los pseudoprimos) que igualmente pueden pasar ese test.

A lo largo del tiempo se han inventado tests de primalidad más eficientes que el teorema de Fermat. Todos ellos tienen en común que dan un resultado probable sobre la primalidad de p con una probabilidad de error determinada, y mediante iteraciones sucesivas del método podemos obtener mayores grados de certeza sobre el resultado. Cuanto mayor grado de certeza queramos tener, más iteraciones del método habrá que hacer y más tiempo computacional tardará en terminar el test.

Así, si usamos un test de primalidad, como el método de Lehmann o algún otro, que nos indica si un número p es primo con una probabilidad de error menor o igual que 0.5 en el peor caso, si repetimos el método para p (con distintos parámetros, claro) n veces seguidas, al final la probabilidad de error será de 1 contra 2n.

Generación de números primos

A efectos prácticos, un algoritmo que se suele emplear en las aplicaciones (por ejemplo, como Matlab o Maple) para generar aleatoriamente un número primo p con n bits es el siguiente:

  1. Generar un número aleatorio p de n bits.
  2. Poner a uno el bit más significativo (así garantizamos que el número es de n bits) y el menos significativo (debe ser impar para poder ser primo)
  3. Intentar dividir p por una tabla de primos precalculados (usualmente aquellos que sean menores que 2000). Esto elimina gran cantidad de números no primos de una forma muy rápida. Baste decir a título informativo que más del 99.8 % de los números impares no primos es divisible por algún número primo menor que 2000.
  4. Ejecutar tests de primalidad sobre p para ver si es primo hasta el grado de certeza deseado
  5. Si el test falla, incrementar p en dos unidades y volver al paso 3.
Anterior Arriba Siguiente