aritmetica modular

Tema 4: Aritm´tica Modular
e
Magdalena Fern´ndez Lebr´n
a
o
lebron@us.es
Dpto. Matem´tica Aplicada I
a

Curso 2013-2014

Introducci´n a la Matem´tica Discreta
o
a
Grado en I.I.-T´cnolog´ Inform´ticas
e
ıas
a
Magdalena Fern´ndez Lebr´n lebron@us.es
a
o

Tema 4: Aritm´tica Modular
e

N´meros congruentes
u
Ejemplo
Si contamos 100 d´ a partir de hoy, ¿en qu´ d´ de lasemana
ıas
e ıa
caer´? Como 100 = 14 × 7 + 2, dentro de 100 d´ ser´ el
a
ıas
a
mismo d´ de la semana que dentro de dos d´ Aqu´ hemos
ıa
ıas.
ı
tomado n = 7 y hemos reemplazado 100 por el resto de su
divisi´n entre 7, es decir, por 2.
o
Definici´n
o
´
[Numeros congruentes]
Sea n un entero positivo y sean a y b dos enteros cualesquiera.
Se dice que a es congruente con b m´dulo n y lodenotamos por
o
a ≡ b (mod n) si a y b dan el mismo resto cuando se dividen
entre n.
a=q n+r
b=q n+r

0≤r 1, como d divide a n sabemos que n es
compuesto.
Si mcd (a, n) = 1 y
an−1 ≡ 1 (mod n) =⇒ n es compuesto.
Obs´rvese que al ser a ⊥ n podemos hacer uso del teorema
e
de Fermat en vez de su corolario.
Si mcd (a, n) = 1 y an−1 ≡ 1 (mod n) nos quedaremos
con la duda de si se trata deun primo o de un pseudoprimo
para la base a.

Magdalena Fern´ndez Lebr´n lebron@us.es
a
o

Tema 4: Aritm´tica Modular
e

1

Escoger, aleatoriamente una base a ∈ {2, . . . , n − 1}

2

Calcular el mcd (a, n)
Si mcd (a, n) > 1, devolver compuesto
si no, si an−1 ≡ 1 (mod n), devolver compuesto
si no, devolver posible primo

Obs´rvese que al tomar a ∈ {2, . . . , n − 1} existenn − φ(n) − 1
e
posibilidades de que mcd (a, n) > 1 en cuyo caso sabemos que el
n´mero n es compuesto y s´lo φ(n) − 1 casos en los que
u
o
mcd (a, n) = 1 y ser´ necesario aplicar realmente el test de
ıa
pseudoprimalidad, por lo que existen muchas posibilidades de
que aun siendo n un n´mero de Carmichael, el test detecte que
u
se trata de un n´mero compuesto.
u
Magdalena Fern´ndezLebr´n lebron@us.es
a
o

Tema 4: Aritm´tica Modular
e

Otros test de primalidad
Para cualquier entero positivo elegido al azar, la funci´n
o
isprime de Maple determina si n es primo con una
probabilidad de error inferior a 10−15 .
Para la obtenci´n de n´meros primos muy grandes se
o
u
utilizan los n´meros de Mersenne (Mp = 2p − 1 con p
u
primo). El siguiente algoritmo nos proporcionaun test
determinista de primalidad eficiente para los n´meros de
u
Mersenne.
Teorema
Sea p un primo impar y consideremos la sucesi´n
o
2
2
S1 = 4 S2 ≡ S1 − 2 (mod Mp ) · · · Sp−1 ≡ Sp−2 − 2 (mod Mp ).

Se verifica entonces que el n´mero de Mersenne Mp es primo
u
si, y s´lo si, Sp−1 ≡ 0 (mod Mp ).
o
Magdalena Fern´ndez Lebr´n lebron@us.es
a
o

Tema 4: Aritm´tica Modular
e

Testde Lucas-Lehmer
Este test, que resulta en apariencia demasiado largo de
realizar, es ideal para ordenadores, ya que las congruencias
se realizan m´dulo 2p − 1 que en binario son muy f´ciles de
o
a
obtener. Adem´s se ha refinado computacionalmente con el
a
uso de Transformadas R´pidas de Fourier para multiplicar
a
a gran velocidad.
El soporte inform´tico para dichos c´lculos fuecoordinado
a
a
por el programa GIMPS (Great Internet Mersenne Prime
Search), que desde su fundaci´n en 1996 ha obtenido todos
o
los a˜os el “Oscar al mayor n´mero primo” y es mediante
n
u
el test de Lucas-Lehmer como se prob´ que M43112609 es
o
primo (el mayor n´mero primo conocido con 12,978,189
u
d´
ıgitos).

Magdalena Fern´ndez Lebr´n lebron@us.es
a
o

Tema 4: Aritm´tica Modular
eCongruencias lineales

Para dar sentido al cociente [b]/[a] de dos clases de
congruencias [a], [b] ∈ Zn , tenemos que considerar la
soluci´n de la congruencia lineal ax ≡ b (mod n).
o
Si x es una soluci´n, y x ≡ x, entonces ax ≡ ax ≡ b y, por
o
tanto, x tambi´n es una soluci´n; por lo que las soluciones
e
o
(en caso de existir) las constituyen clases de congruencia.
Como ax ≡ b...