Upload
alinser-alcantara-cabrejos
View
21
Download
1
Embed Size (px)
Citation preview
Tema 4: Aritmetica Modular
Magdalena Fernandez [email protected]
Dpto. Matematica Aplicada I
Curso 2013-2014
Introduccion a la Matematica DiscretaGrado en I.I.-Tecnologıas Informaticas
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Numeros congruentes
Ejemplo
Si contamos 100 dıas a partir de hoy, ¿en que dıa de la semanacaera? Como 100 = 14× 7 + 2, dentro de 100 dıas sera elmismo dıa de la semana que dentro de dos dıas. Aquı hemostomado n = 7 y hemos reemplazado 100 por el resto de sudivision entre 7, es decir, por 2.
Definicion
[Numeros congruentes]Sea n un entero positivo y sean a y b dos enteros cualesquiera.Se dice que a es congruente con b modulo n y lo denotamos pora ≡ b (mod n) si a y b dan el mismo resto cuando se dividenentre n.
a = q n+ r 0 ≤ r < nb = q′n+ r′ 0 ≤ r′ < n
}a ≡ b (mod n) ⇐⇒ r = r′
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Caracterizacion de los numeros congruentes
Ejemplos
1 16 ≡ 11 (mod 5) ya que al dividir ambos (16 y 11) por 5obtenemos de resto 1:
16 = 3× 5 + 1 y 11 = 2× 5 + 1
2 8 ≡ 5 (mod 3) ya que 8 = 2× 3 + 2 y 5 = 1× 3 + 2.
Lema
Para cualquier entero dado n ≥ 1
a ≡ b (mod n) ⇐⇒ n|(a− b)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Relacion de equivalencia
Lema
Para cualquier entero fijo n ≥ 1 se verifican las propiedades:
1 Reflexiva: a ≡ a (mod n) para cualquier entero a
2 Simetrica: a ≡ b (mod n) =⇒ b ≡ a (mod n)
3 Transitiva:a ≡ b (mod n)
b ≡ c (mod n)
}=⇒ a ≡ c (mod n).
Estas tres propiedades definen una relacion de equivalencia, porlo que para cada entero n, la congruencia modulo n es unarelacion de equivalencia en Z.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Clases de equivalencia
Cada elemento a ∈ Z define la clase de equivalencia
[a] = {x ∈ Z : x ≡ a (mod n)} = {.., a−2n, a−n, a, a+n, a+2n, ..}
quedando Z dividido en las n clases de equivalenciacorrespondientes a los n posibles restos de dividir un enteroentre n
[0], [1], [2], . . . , [n−1] ya que a ≡ b (mod n) ⇐⇒ [a] = [b]
Ejemplo
Para n = 2 el conjunto Z queda dividido en las clases [0] y [1]que se corresponden con los numeros pares y los imparesrespectivamente.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Enteros modulo n
Definicion
Para cada n ≥ 1, el conjunto de las n clases de congruenciamodulo n lo denotamos por Zn y se conoce como el conjunto delos enteros modulo n.
Zn = {0, 1, 2, . . . , n− 1}
donde los elementos a ∈ Zn representan a sus respectivas clasesde equivalencia modulo n.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La aritmetica de Zn
Definicion
Si a y b son elementos de Zn (ie, representan a las clases deequivalencia [a] y [b] modulo n respectivamente), definimos
[a] + [b] = [a+ b][a]− [b] = [a− b]
[a][b] = [ab]
Ejemplo
Sea Z2 = {0, 1} donde 0 = [0]2 representa a cualquier entero pary 1 = [1]2 a cualquier numero impar. Decir en Z2 que
1 + 1 = [1] + [1] = [1 + 1] = [2] = [0] = 0
equivale a decir que la suma de dos numeros impares es par,pero independientemente de los numeros impares que se hayansumado.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La aritmetica en Zn
Lema
Para cualquier entero n ≥ 1, si a′ ≡ a (mod n) y b′ ≡ b (mod n),entonces a′ + b′ ≡ a+ b, a′ − b′ ≡ a− b y a′b′ ≡ ab.
Ejemplo
Calculemos resto de la division de 28× 33 entre 35.
28 ≡ −7 (mod 35)33 ≡ −2 (mod 35)
}=⇒ 28× 33 ≡ (−7)× (−2) ≡ 14 (mod 35)
Es decir, el resto de la division es 14.
Observese que en Z35 hemos tomado como representantes de lasclases 28 y 33 a los enteros -7 y -2 ya que el producto esindependiente de los representantes que se tomen.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La aritmetica en ZnSi intentamos definir la exponencial de clases en Zn como
[a][b] = [ab],
limitandonos a los valores no negativos de b con el fin de que ab
sea entero.
Si fijamos n = 3 se tiene, por ejemplo, que
[2][1] = [21] = [2]
desafortunadamente, [1] = [4] en Z3 y nuestra definicion nosdice que
[2][4] = [24] = [16] = [1] 6= [2]
por lo que se obtienen diferentes clases de congruencia para[a][b] para diferentes representantes b y b′ de la misma clase [b].Limitamos, por tanto, la aritmetica en Zn a las operaciones biendefinidas, tales como la suma, la resta, el producto, la potencia.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La aritmetica en Zn
Para cualquier entero k ≥ 2, podemos definir sumas finitas,productos y potencias de clases en Zn por
[a1] + [a2] + · · ·+ [ak] = [a1 + a2 + · · ·+ ak][a1][a2] · · · [ak] = [a1a2 · · · ak]
[a]k = [ak]
¿Y la division? ¡Cuidado! Si a · c ≡ b · c (mod n), nosiempre es cierto que a ≡ b (mod n) (no se verifica lapropiedad cancelativa del producto)Ejemplo: 15 · 2 ≡ 20 · 2 (mod 10), pero 15 6≡ 20 (mod 10).
Mas aun, puede ocurrir que
a · b ≡ 0 (mod n) con a 6= 0 (mod n) y b 6= 0 (mod n)
(existen elementos divisores de cero)Ejemplo: 6 · 4 ≡ 0 (mod 12), pero 4 6≡ 0 (mod 12) ni6 6≡ 0 (mod 12).Mas adelante veremos cuando podemos dividir
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Propiedades de la suma y el producto
Internas:
∀x, y ∈ Zn =⇒ x+ y, xy ∈ Zn.
Asociativas:
∀x, y, z ∈ Zn ⇒ x+ (y + z) = (x+ y) + z, x(yz) = (xy)z.
Conmutativas:
∀x, y ∈ Zn =⇒ x+ y = y + x, xy = yx.
Distributiva:
∀x, y, z ∈ Zn =⇒ x(y + z) = xy + xz.
Elementos neutro y unidad: ∃0, 1 ∈ Zn tales que∀x ∈ Zn ⇒ x+ 0 = 0 + x = x y x · 1 = 1 · x = x
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Propiedades de la suma y el producto
Elementos opuestos:∀x ∈ Zn existe un unico elemento, que denotaremos por−x ∈ Zn tal que x+ (−x) = (−x) + x = 0.
Divisores de cero:Un elemento no nulo de Zn tal que su producto por otroelemento tambien no nulo produce un resultado nulo se diceque es un divisor de cero.Ası, por ejemplo, en Z4 2 es divisor de cero ya que 2 · 2 = 0.La existencia de divisores de cero hace que, en Zn, NO SEVERIFIQUE LA PROPIEDAD CANCELATIVADEL PRODUCTO.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Tablas de la suma y el producto en Z4
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
× 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
Observamos que 2 · 1 = 2 · 3 y esto no implica la igualdad de 1 y3, es decir, en Z4 no se verifica la propiedad cancelativa delproducto.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Tablas de la suma y el producto en Z5
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
× 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Observemos que aunque el producto no tiene elemento inverso,existen elementos que sı lo tienen, por ejemplo el 4 (4× 4 = 1,es decir 4 es autoinverso) o el 2 y el 3 que son inversos uno delotro (ya que 2× 3 = 1 y 3× 2 = 1). Cabe entonces hacerse lasiguiente pregunta
¿cuando va a tener inverso un elemento de Zn?
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Unidades de Zn
Definicion
Un elemento r de Zn decimos que es una unidad si es inversible,es decir, si existe otro elemento s ∈ Zn tal que sr = rs = 1.
Teorema
El inverso de un elemento unidad es unico.
Teorema
Un elemento r ∈ Zn es inversible si, y solo si, r y n son primosentre si, es decir, si mcd (n, r) = 1.
r unidad de Zn ⇐⇒ r ⊥ n
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Observaciones
El algoritmo extendido de Euclides nos proporciona el inversode los elementos unitarios de Zn.
Ejemplo
Las unidades de Z8 son 1, 3, 5 y 7, en efecto:
1 · 1 = 1 3 · 3 = 1 5 · 5 = 1 7 · 7 = 1
por lo que cada una de estas unidades es su propio inverso.En Z9 las unidades son 1, 2, 4, 5, 7 y 8
1 · 1 = 1 2 · 5 = 1 4 · 7 = 1 8 · 8 = 1
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La estructura de [Zn,+, ·]
Si n es compuesto n = ab con 1 < a, b < n por lo que en Znlas clases definidas por dichos elementos verificaran queab = 0 es decir, Zn posee divisores de cero y la estructurade [Zn,+, ·] es de un anillo con divisores de cero.
Si p es primo, cualquier elemento no nulo deZp = {0, 1, . . . , p− 1} es primo con p y posee inverso, por loque todos los elementos no nulos de Zp tienen inverso,resultando que [Zp,+, ·] tiene estructura de cuerpo.
Teorema
Los unicos elementos autoinversos de Zp con p primo son 1 yp− 1.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Pequeno teorema de Fermat
Teorema
Si p es primo y a ⊥ p (es decir, mcd (a, p) = 1),
ap−1 ≡ 1 (mod p).
Corolario
Si p es primo, para cualquier entero a se verifica que
ap ≡ a (mod p)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo
Encontrar el resto de la division de 268 entre 19:Aplicando el Pequeno teorema de Fermat a p = 19 (primo)y a = 2 (ya que mcd (2, 19) = 1), tenemos que218 ≡ 1 (mod 19).Dado que 68 = 18× 3 + 14, se tiene
268 = (218)3 × 214 ≡ 13 × 214 = 214 (mod 19).
Como 24 = 16 ≡ −3 (mod 19), podemos escribir14 = 4× 3 + 2 y deducir que
214 = (24)3 × 22 ≡ (−3)3 × 22 ≡ −27× 4 ≡
≡ −8× 4 ≡ −32 ≡ 6 (mod 19)
por lo que el resto de la division es 6.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo
Vamos a probar que a25 − a es divisible entre 30 cualquieraque sea el entero a:Factorizando 30, es suficiente probar que a25 − a esdivisible por los primos 2, 3 y 5.
Aplicando el Corolario del pequeno teorema de Fermat dosveces tenemos:
a25 = (a5)5 ≡ a5 ≡ a (mod 5)
por lo que 5 divide a a25 − a cualquiera que sea el entero a.Analogamente, a3 ≡ a (mod 3), por lo que
a25 = (a3)8a ≡ a8a = a9 = (a3)3 ≡ a3 ≡ a (mod 3)
es decir, 3 divide a a25 − a cualquiera que sea el entero a.Ademas, a2 ≡ a (mod 2) de donde se deduce que
a25 = (a2)12a ≡ a12a = (a2)6a ≡ a6a = (a2)3a
≡ a3a = a4 = (a2)2 ≡ a2 ≡ a (mod 2).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Funcion De Euler
Ahora pretendemos encontrar un resultado similar alpequeno teorema de Fermat, pero para numeroscompuestos n, es decir, an−1 ≡ 1 (mod n) (que en generalno es cierta).
Si d = mcd (a, n) > 1, cualquier potencia de a es divisiblepor d, por lo que no puede ser congruente con 1 modulo n
Esto nos sugiere que debemos restringirnos a los enteros aque sean primos con n.
Pero aun entonces la congruencia puede fallar: n = 4(compuesto), a = 3 (primo con n) yan−1 = 33 = 27 6≡ 1 (mod 4).
Necesitamos un exponente diferente e(n) tal queae(n) ≡ 1 (mod n) para todo entero a primo con n.
La funcion mas sencilla que cumple esta propiedad es lafuncion de Euler.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Funcion de Euler
Definicion
Se denomina funcion de Euler a la funcion φ : N→ N queasocia a cada n ∈ N el numero de unidades de Zn, es decir:φ(n) = |Un|
La siguiente tabla nos da el valor de la funcion de Euler para losprimeros enteros
n 1 2 3 4 5 6 7 8 9 10 11 12
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4
Si n es primo, φ(n) = n− 1
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Propiedades de la funcion de Euler
1 φ(pe) = pe − pe−1 = pe−1(p− 1) = pe(
1− 1p
).
2 m ⊥ n =⇒ φ(mn) = φ(m)φ(n).
3 n = pe11 · pe22 · · · p
ekk =⇒
φ(n) =
k∏i=1
(peii −pei−1i ) =
k∏i=1
pei−1i (pi−1) = n
k∏i=1
(1− 1
pi
).
4 d = mcd (n,m) =⇒ φ(mn)φ(d) = φ(m)φ(n)d.
Ejemplo
φ(60) = φ(22 · 3 · 5) = 60
(1− 1
2
)(1− 1
3
)(1− 1
5
)= 16.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Teorema de Euler
En 1760, Euler probo la siguiente generalizacion del PequenoTeorema de Fermat y que se conoce como teorema de Euler.
Teorema
Si a ⊥ n se verifica que aφ(n) ≡ 1 (mod n).
El Pequeno Teorema de Fermat es un caso especial de esteresultado: si n es primo φ(n) = n− 1, luego an−1 ≡ 1 (mod n).
Ejemplo
Encontrar el resto de la division de 2365 entre 60.Dado que 23 es primo con 60, el teorema de Euler nos dice que
23φ(60) = 2316 ≡ 1 (mod 60)
2365 = 2316·4+1 = (2316)4 · 23 ≡ 14 · 23 = 23 (mod 60)
por lo que el resto buscado es 23.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Tests de primalidad
Teorema
[Teorema de Wilson]Un entero positivo n es primo si, y solo si,(n− 1)! + 1 ≡ 0 (mod n).
Ejemplo: El 13 es primo ya que
(13−1)!+1 = 12!+1 = 479001601 = 36846277·13 ≡ 0 (mod 13)
El test de Wilson no es aplicable ya que el calculo de(n− 1)! requiere, para valores grandes de n un numero deoperaciones que en un ordenador puede superar la edad delUniverso. Ası para un numero de 100 dıgitos n ≈ 10100 sedeberıan realizar 10100 productos y un ordenador querealizase un billon de operaciones por segundo requerirıaaproximadamente 3 · 1078 siglos en realizarlos.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Tests de primalidad
El teorema de Wilson resuelve el problema del test deprimalidad. Sin embargo, la dificultad de computarfactoriales hace que el test sea muy ineficaz, incluso paraenteros pequenos.
Nos encontramos, por tanto, que no existe ningunmetodo determinista que pueda realizarse de maneraefectiva.
Todos los metodos que se aplican en la practica sonmetodos probabilısticos, es decir, metodos que no nospueden asegurar que un entero n sea primo aunquesı pueden garantizarnos una probabilidad alta de que lo sea.
Todos los test que veremos a continuacion si detectan quen es compuesto, nos garantizan que lo es, y solo cuando nopueden detectar si es compuesto nos diran que posiblementepueda ser primo, aunque con una probabilidad alta. Esaprobabilidad depende del test que estemos aplicando.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Test de pseudoprimalidad de Fermat
Proposicion
Sea n un entero positivo. Si existe un entero a para el quean 6≡ a (mod n), podemos asegurar que n es compuesto.
Los chinos utilizaban este test para a = 2 y conjeturaronhace 25 siglos que el recıproco del corolario del pequenoteorema de Fermat tambien era cierto, se decir, que si2n ≡ 2 (mod n), entonces n era primo.
Esto resulto ser falso, pero hasta 1819 no se encontro uncontraejemplo: 2341 ≡ 2 (mod 341) y 341 = 11 · 31 escompuesto.
A dichos enteros los denominamos pseudoprimos : parecenque son primos, pero de hecho son compuestos.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Pseudoprimos
Definicion
Un entero n se dice que es pseudoprimo para la base a si,siendo compuesto, verifica que an ≡ a (mod n).
El numero 341 es un pseudoprimo para la base 2, ya que2341 ≡ 2 (mod 341) y 341 = 11 · 31 (compuesto).
Si el numero de pseudoprimos para una determinada base afuese finito bastarıa aplicar el test de pseudoprimalidadde Fermat en dicha base a un determinado entero n paradecidir:
Si an 6≡ a (mod n), el numero n es compuesto.Si an ≡ a (mod n), entonces n o es primo o es pseudoprimopara dicha base. Mirando si figura en la lista de lospseudoprimos para dicha base podrıamos decidir si se tratade un primo o de un numero compuesto.
Desgraciadamente, esto no es posible ya que:
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Pseudoprimos
Teorema
Existen infinitos pseudoprimos para cualquier base a.
Ejemplo:
2341 ≡ 2 (mod 341). No sabemos si 341 es primo opseudoprimo para la base 2. Es decir, no sabemos si esprimo o compuesto.3341 ≡ 168 6= 3 (mod 341). Podemos asegurar que escompuesto.
Si n supera el test para las bases a y b:an ≡ a (mod n)bn ≡ b (mod n)
}=⇒ (ab)n ≡ ab (mod n) es decir,
tambien supera el test para la base ab, no aportando nadanuevo la aplicacion de este test, por lo que parece sensatorestringir los valores de las bases a los sucesivos numerosprimos.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Test de pseudoprimalidad de Fermat
Al aplicar el test de pseudoprimalidad de Fermat esnecesario calcular an por lo que multiplicando a por asucesivamente serıan necesarias n− 1 operaciones, lasmismas que requiere el calculo de (n− 1)! Por lo quenuestro ordenador tardarıa 3 · 1078 siglos en realizar loscalculos cuando n es un numero de 100 dıgitos.
Pero en aritmetica modular podemos reducir el numero demultiplicaciones para el calculo de grandes potencias:
Si queremos calcular 1226 (mod 23), descomponemos elexponente como potencias de 2 (pasarlo a base 2),26 = (11010)2. Entonces 1226 = 1216 · 128 · 122 que solonecesita de 6 multiplicaciones.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Algoritmo de calculo de grandes potencias
Supongamos que queremos calcular an. Por ejemplo a19.
Expresamos n en notacion binaria. 19→ 10011.
Intercalamos una C entre cada dos cifras. 1C0C0C1C1.
Eliminamos los ceros. 1CCC1C1.
Sustituimos los unos por la letra M . MCCCMCM .
Comenzando ahora por 1 y siguiendo la secuencia obtenida enla que M representa multiplicar por n y C elevar al cuadradovamos obteniendo:
1M−→ a
C−→ a2 C−→ a4 C−→ a8 M−→ a9 C−→ a18 M−→ a19
Luego, para cualquier entero positivo n, el numero demultiplicaciones que requiere el calculo de an es, como maximo,el doble del numero de dıgitos de la expresion binaria de n, esdecir, como maximo 2 · (1 + blog2 nc).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Para un numero de 100 dıgitos n ≈ 10100 habrıa que hacer,en el peor de los casos
2 · (1 + blog2 10100c) = 666
operaciones y nuestro ordenador que realiza un billon deoperaciones por segundo tardarıa menos de unamilmillonesima de segundo en realizarlas, frente a los3 · 1078 siglos que tardarıa multiplicando a por asucesivamente.
Luego el test de pseudoprimalidad de Fermat es facilmenteaplicable.
Si para una determinada base el test no puede asegurarnossi nuestro numero es primo o compuesto, podemos cambiarde base (utilizando siempre numeros primos como base).
Al aumentar el numero de bases para las quean ≡ a (mod n) mayor probabilidad tendremos de quenuestro numero n sea primo.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Numeros de Carmichael
¿Serıa una buena estrategia seguir probando bases hastaencontrar alguna en la que, si el numero es compuesto, sedetecte como compuesto? La respuesta evidentemente es que no.
Definicion
Se denominan numeros de Carmichael a aquellos numeros quesiendo compuestos superan los test de pseudoprimalidad deFermat cualquiera que sea la base que se tome.
n de Carmichael ⇐⇒{
n compuestoan ≡ a (mod n) ∀ a ∈ Z+
Los numeros de Carmichael se dan con mucha menor frecuenciaque los primos aunque no son difıciles de construir.En 1912, Carmichael conjeturo que existen infinitos, y fueprobado en 1992 por Alford, Granville y Pomerance.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Numeros de Carmichael
Teorema
[Caracterizacion de los numeros de Carmichael]Un numero compuesto n es de Carmichael si, y solo si, es librede cuadrados (un producto de primos distintos) y p− 1 divide an− 1 para cada primo p que divide a n.
Ejemplo
561 = 3 · 11 · 17 es compuesto y libre de cuadrados y ademas3− 1 = 2 | (561− 1) = 560
11− 1 = 10 | (561− 1) = 56017− 1 = 16 | (561− 1) = 560
por lo que se trata de un numero de Carmichael.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Test de pseudoprimalidad de Fermat
Elegimos al azar una base a del rango {2, 3, . . . , n− 1},resultando:
Si mcd (a, n) = d > 1, como d divide a n sabemos que n escompuesto.
Si mcd (a, n) = 1 yan−1 6≡ 1 (mod n) =⇒ n es compuesto.Observese que al ser a ⊥ n podemos hacer uso del teoremade Fermat en vez de su corolario.
Si mcd (a, n) = 1 y an−1 ≡ 1 (mod n) nos quedaremoscon la duda de si se trata de un primo o de un pseudoprimopara la base a.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
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 6≡ 1 (mod n), devolver compuesto
si no, devolver posible primo
Observese que al tomar a ∈ {2, . . . , n− 1} existen n− φ(n)− 1posibilidades de que mcd (a, n) > 1 en cuyo caso sabemos que elnumero n es compuesto y solo φ(n)− 1 casos en los quemcd (a, n) = 1 y serıa necesario aplicar realmente el test depseudoprimalidad, por lo que existen muchas posibilidades deque aun siendo n un numero de Carmichael, el test detecte quese trata de un numero compuesto.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Otros test de primalidad
Para cualquier entero positivo elegido al azar, la funcionisprime de Maple determina si n es primo con unaprobabilidad de error inferior a 10−15.
Para la obtencion de numeros primos muy grandes seutilizan los numeros de Mersenne (Mp = 2p − 1 con pprimo). El siguiente algoritmo nos proporciona un testdeterminista de primalidad eficiente para los numeros deMersenne.
Teorema
Sea p un primo impar y consideremos la sucesion
S1 = 4 S2 ≡ S21−2 (mod Mp) · · · Sp−1 ≡ S2
p−2−2 (mod Mp).
Se verifica entonces que el numero de Mersenne Mp es primosi, y solo si, Sp−1 ≡ 0 (mod Mp).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Test de Lucas-Lehmer
Este test, que resulta en apariencia demasiado largo derealizar, es ideal para ordenadores, ya que las congruenciasse realizan modulo 2p − 1 que en binario son muy faciles deobtener. Ademas se ha refinado computacionalmente con eluso de Transformadas Rapidas de Fourier para multiplicara gran velocidad.
El soporte informatico para dichos calculos fue coordinadopor el programa GIMPS (Great Internet Mersenne PrimeSearch), que desde su fundacion en 1996 ha obtenido todoslos anos el “Oscar al mayor numero primo” y es medianteel test de Lucas-Lehmer como se probo que M43112609 esprimo (el mayor numero primo conocido con 12,978,189dıgitos).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Congruencias lineales
Para dar sentido al cociente [b]/[a] de dos clases decongruencias [a], [b] ∈ Zn, tenemos que considerar lasolucion de la congruencia lineal ax ≡ b (mod n).
Si x es una solucion, y x′ ≡ x, entonces ax′ ≡ ax ≡ b y, portanto, x′ tambien es una solucion; por lo que las soluciones(en caso de existir) las constituyen clases de congruencia.
Como ax ≡ b (mod n) si, y solo si, ax− b es multiplo de n,se tiene que x es una solucion de la congruencia lineal si, ysolo si, existe un entero y tal que x e y satisfacen laecuacion diofantica ax+ ny = b.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Congruencias lineales
Teorema
Si d = mcd (a, n), entonces la congruencia lineal
ax ≡ b (mod n)
tiene solucion si, y solo si, d divide a b. Si d divide a b y x0 esuna solucion, la solucion general viene dada por
x = x0 +nt
d
donde t ∈ Z : en particular, las soluciones forman, exactamente,d clases de congruencias modulo n, con representantes:
x = x0, x0 +n
d, x0 +
2n
d, · · · x0 +
(d− 1)n
d
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplos congruencias lineales
Ejemplo
Consideremos la congruencia
10x ≡ 3 (mod 12).
Aquı a = 10, b = 3 y n = 12, por lo que d = mcd (10, 12) = 2;como no divide a 3, no existen soluciones. (Esto puede versedirectamente: los elementos de la clase de congruencia [3] enZ12 son todos impares, mientras que cualquier elemento de[10][x] es par.)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplos congruencias lineales
Ejemplo
Consideremos ahora la congruencia
10x ≡ 6 (mod 12).
Al igual que antes, d = 2 y ahora sı divide a b = 6, por lo queexisten dos clases de soluciones. Podemos tomar x0 = 3 comosolucion particular para expresar la solucion general de la forma
x = x0 +nt
d= 3 +
12t
2= 3 + 6t
donde t ∈ Z. Estas soluciones constituyen dos clases decongruencia [3] y [9] modulo 12, cuyos representantes x0 = 3 yx0 + (n/d) = 9; constituyen la unica clase de congruencia [3]modulo 6.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Congruencias lineales
Corolario
Si mcd (a, n) = 1 las soluciones x de la congruencia linealax ≡ b (mod n) constituyen una unica clase de congruenciamodulo n.
Luego si a y n son primos entre sı, para cada b existe unaunica clase [x] tal que [a][x] = [b] en Zn; podemosconsiderar que la clase [x] es la clase cociente [b]/[a]obtenida dividiendo [b] entre [a] en Zn.
Si d = mcd (a, n) > 1 existen, sin embargo, mas de unaclase [x] (cuando d divide a b), o ninguna (cuando d nodivide a b), por lo que no podemos definir, en este caso, laclase cociente [b]/[a].
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Congruencias lineales
Ejemplo
Consideremos la congruencia
7x ≡ 3 (mod 12).
Aquı a = 7 y n = 12 por lo que, al ser primos entre sı, soloexiste una clase solucion; esta es la clase [x] = [9], ya que7× 9 = 63 ≡ 3 (mod 12).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Propiedades de las congruencias lineales
1 Sea m un divisor de a, b y n y sean a′ = a/m, b′ = b/m yn′ = n/m;
ax ≡ b (mod n) ⇐⇒ a′x ≡ b′ (mod n′).
2 Sean a y n primos entre sı, m un divisor de a y b y seana′ = a/m y b′ = b/m;
ax ≡ b (mod n) ⇐⇒ a′x ≡ b′ (mod n).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Calculo de una solucion particular de ax ≡ b (mod n)
Vamos a desarrollar un proceso para tratar de eliminar elcoeficiente a de la congruencia, ya que en ese caso nos quedarıa
x ≡ b (mod n) ⇐⇒ x = b+ n t ∀ t ∈ Z
10x ≡ 6 (mod 12)
Paso 1 Calculamos d = mcd (a, n) y vemos si d | b. En casocontrario, no existen soluciones y paramos. Si lo divide,vamos al paso 2.
d = mcd (10, 12) = 2 | 6 = b =⇒ la congruencia admite soluciones
Paso 2 Como d divide a a, b y n,
ax ≡ b (mod n)⇒ a′x ≡ b′ (mod n′) con a′ ⊥ n′ Si a′ = 1, FIN
10x ≡ 6 (mod 12) ⇐⇒ 5x ≡ 3 (mod 6) con 5 ⊥ 6
Paso 3 Calculamos d′ = mcd (a′, b′) y llamando a′′ = a′/d′ yb′′ = b′/d′
a′x ≡ b′ (mod n′)⇒ a′′x ≡ b′′ (mod n′) Si a′′ = 1, FIN
mcd (5, 3) = 1 =⇒ 5x ≡ 3 (mod 6)Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Calculo de una solucion particular de ax ≡ b (mod n)
P4 Observando que
b′′ ≡ b′′ ± n′ ≡ b′′ ± 2n′ ≡ · · · (mod n′)
podemos sumar o restar al termino independiente multiplosdel modulo con vistas a que la aplicacion del paso 3reduzca en modulo el coeficiente de la congruencia.5x ≡ 3 (mod 6)⇒{
5x ≡ 3 + 1 · 6 = 9 (mod 6)5x ≡ 3 + 2 · 6 = 15 (mod 6)⇒ x ≡ 3 (mod 6)
Se ha eliminado el coeficiente, FIN. x = 3 + 6 t ∀ t ∈ Z.Otra alternativa consiste en multiplicar la congruencia (noel modulo) por algun numero primo con el modulo (inversodel paso 3) para que, el coeficiente se reduzca en funciondel modulo.
5 ⊥ 6⇒ 5·5x ≡ 5·3 (mod 6)⇒ 25x ≡ 15 (mod 6)⇒ x ≡ 3 (mod 6)
Se ha eliminado el coeficiente, FIN. x = 3 + 6 t ∀ t ∈ Z.Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Algoritmo
Algoritmo para convertir la congruencia ax ≡ b (mod n) en laecuacion diofantica equivalente ax− nt = b y hallar la soluciongeneral para la variable x mediante el Algoritmo Extendido deEuclides (AEE) el siguiente, que tiene por entradas los enterosa, b y n:
1 Calcular d = mcd (a, n)
2 Si b 6≡ 0 (mod d)
retornar No tiene solucion
si no, a = a/d, b = b/d, n = n/d
Aplicar el AEE al par (a, n)→ u · a+ v · n = 1
Retorna x = u · b (mod n)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo
Ejemplo
Consideremos la congruencia 4x ≡ 13 (mod 47).
dado que mcd (4, 47) = 1 | 13 la congruencia admite soluciones.
Al ser d = 1 el primer paso nos deja la congruencia invariante.
Al ser tambien mcd (4, 13) = 1 el segundo paso tampocomodifica la ecuacion.
Teniendo en cuenta que 13 ≡ 13 + 47 = 60 (mod 47), se tieneque 4x ≡ 60 (mod 47) y como 4 ⊥ 47, obtenemos
x ≡ 15 (mod 47)
Es decir, x = 15 + 47 t ∀ t ∈ Z.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Propiedades
1 Si a ≡ b (mod n) y d|n, entonces a ≡ b (mod d).
2 Si a · c ≡ b · c (mod n), entonces a ≡ b (modn
mcd (c, n))
Si mcd (c, n) = 1, se verifica la propiedad cancelativa delproducto.
3 Si m ⊥ n (es decir, mcd (m,n) = 1), entonces se verifica:{a ≡ b (mod m)a ≡ b (mod n)
⇐⇒ a ≡ b (mod m · n)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Sistemas de congruencias lineales
Es un sistema de la forma k ecuaciones pero con una solaincognita
a1x ≡ b1 (mod n1)a2x ≡ b2 (mod n2)
...akx ≡ bk (mod nk)
Para que el sistema tenga solucion deberan tenerla cadauna de las ecuaciones del sistema, lo que equivale a decirque se pueden eliminar todos los coeficientes ai, ya queeliminado ai esta resuelta la ecuacion i-esima.
Una vez eliminados todos los coeficientes ai lo unico quesabemos es que todas las ecuaciones tienen solucion, perodesconocemos si existe alguna solucion comun a todas ellas.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Teorema chino de los restos
En el siglo IV a.C. el matematico chino Sun TsuSuan-Ching estudio el problema de encontrar un x tal quelas congruencias
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
se satisfagan simultaneamente.
Observese que si x0 es una solucion, tambien lo esx = x0 + (3× 5× 7)t para cualquier entero t, por lo que lasolucion constituye una clase de congruencia modulo 105.
En cambio el sistema
x ≡ 3 (mod 9), x ≡ 2 (mod 6)
carece de soluciones, ya que si x ≡ 3 (mod 9) entonces 3 esun divisor de x, mientras que si x ≡ 2 (mod 6), 3 no puedeser un divisor de x.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Teorema chino de los restos
El problema consiste en que los modulos 9 y 6 tienen elfactor 3 comun, por tanto, ambas congruencias tienenimplicaciones sobre las clases de congruencia modulo 3, yen este caso particular, ambas implicaciones sonmutuamente inconsistentes.
Por tanto, en principio, nos limitaremos a los casos en losque los modulos son mutuamente primos entre sı.
Teorema
Sean n1, n2, . . . , nk enteros positivos tales que mcd (ni, nj) = 1siempre que i 6= j, y sean a1, a2, . . . , ak enteros cualesquiera.Entonces, las soluciones del sistema de congruencias lineales
x ≡ a1 (mod n1), x ≡ a2 (mod n2), . . . x ≡ ak (mod nk)
constituyen una unica clase de congruencia modulo n, donden = n1n2 · · ·nk.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Demostracion
ci =n
ni= n1 · · ·ni−1 · ni+1 · · ·nk para i = 1, . . . , k
Para cada j, nj ⊥ ni si i 6= j ⇒ nj ⊥ ci, si i = j
Para cada i, la congruencia cix ≡ 1 (mod ni) tiene unaunica clase di de soluciones modulo ni.
x0 = a1c1d1 + a2c2d2 + · · ·+ akckdk es una solucionparticular del sistema y toda la clase de congruencia [x0]modulo n esta compuesta de soluciones y es la unica.
La solucion general viene dada por x = x0 + nt para todot ∈ Z con n = n1 · n2 · · ·nk.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Teorema chino de los restos
Este resultado tiene aplicaciones en muchas areas,incluyendo la astronomıa: La conjuncion de los planetas ylos eclipses son ejemplos de eventos regulares, y elpronosticarlos fue la motivacion original de este teorema.
Lema
Consideremos la descomposicion de n en factores primos
n = pe11 · · · pekk ,
donde p1, . . . , pk son primos diferentes. Para cualesquieraenteros a y b
a ≡ b (mod n) ⇐⇒ a ≡ b (mod peii ) para cada i = 1, . . . , k
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo
Resolvamos la congruencia 91x ≡ 419 (mod 440).Al ser mcd (91, 440) = 1 tiene solucion y, por ser440 = 23 · 5 · 11, la congruencia es equivalente al sistema
91x ≡ 419 (mod 8)91x ≡ 419 (mod 5)91x ≡ 419 (mod 11)
⇐⇒
3x ≡ 3 (mod 8)x ≡ 4 (mod 5)3x ≡ 1 (mod 11)
⇐⇒
x ≡ 1 (mod 8)x ≡ 4 (mod 5)x ≡ 4 (mod 11)
a1 = 1, a2 = 4, a3 = 4, n1 = 8, n2 = 5, n3 = 11, n = n1·n2·n3 = 440
c1 =n
n1= 55 c2 =
n
n2= 88 c3 =
n
n3= 40
c1d1 ≡ 1 (mod n1)⇒ 55d1 ≡ 1 (mod 8)⇒ d1 ≡ 7 (mod 8)⇒ d1 = 7c2d2 ≡ 1 (mod n2)⇒ 88d2 ≡ 1 (mod 5)⇒ d2 ≡ 2 (mod 5)⇒ d2 = 2c3d3 ≡ 1 (mod n3)⇒ 40d3 ≡ 1 (mod 11)⇒d3 ≡ 8 (mod 11)⇒ d3 = 8
x0 = a1c1d1 +a2c2d2 +a3c3d3 = 1·55·7+4·88·2+4·40·8 = 2369,
por lo que la solucion general viene dada por la dex ≡ 2369 (mod 440) ⇐⇒ x ≡ 169 (mod 440)
x = 169 + 440 t ∀ t ∈ ZMagdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Metodo de resolucion de sistemas de congruenciaslineales
Buscamos la solucion de una de las congruencias(normalmente por la que tiene mayor modulo). Para elsistema
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
comenzamos por x ≡ 2 (mod 7); que tiene la solucionx = 2 + 7u ∀u ∈ ZObligamos ahora a que dicha solucion verifique la siguientecongruencia
2+7u ≡ 3 (mod 5) =⇒ 2u ≡ 1 (mod 5) =⇒ u ≡ 3 (mod 5) =⇒u = 3 + 5v ∀ v ∈ Z
por lo que
x = 2 + 7u = 2 + 7(3 + 5v) = 23 + 35v ∀ v ∈ Z
verificara simultaneamente ambas congruencias.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Metodo de resolucion de sistemas de congruenciaslineales
Llevando este resultado a la tercera
23+35v ≡ 2 (mod 3) =⇒ 2v ≡ 0 (mod 3) =⇒ v ≡ 0 (mod 3) =⇒
v = 3t ∀ t ∈ Z =⇒ x = 23 + 35(3 t) = 23 + 105 t ∀ t ∈ Z
La solucion general del sistema viene dada por
x = 23 + 105 t ∀ t ∈ Z
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Teorema chino de los restos generalizado
Nuestro resultado final, obtenido por Yih-Hing en el sigloVII, generaliza el Teorema Chino de los restos al caso en elque los modulos no son primos entre sı.
Teorema
Consideremos los enteros positivos n1, n2, . . . , nk y seana1, a2, . . . , ak enteros cualesquiera. El sistema de congruencias
x ≡ a1 (mod n1), . . . , x ≡ ak (mod nk)
admiten solucion si, y solo si, mcd (ni, nj) divide a ai − aj paracualesquiera i 6= j. Cuando se verifica esta condicion, lasolucion general constituye una unica clase de congruenciamodulo n, donde n es el mınimo comun multiplo de n1, . . . , nk.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo
Sea el sistema de congruencias lineales:
x ≡ 11 (mod 36), x ≡ 7 (mod 40), x ≡ 32 (mod 75).
Dado que
mcd (36, 40) = 4 | (a1 − a2) = 4mcd (36, 75) = 3 | (a1 − a3) = −21mcd (40, 75) = 5 | (a2 − a3) = −25
=⇒ El sistema tiene solucion
x ≡ 11 (mod 22 · 32)⇐⇒{x ≡ 11 (mod 22)⇐⇒ x ≡ 3 (mod 22)x ≡ 11 (mod 32)⇐⇒ x ≡ 2 (mod 32)
x ≡ 7 (mod 23 · 5) ⇐⇒{x ≡ 7 (mod 23)⇐⇒ x ≡ 7 (mod 23)x ≡ 7 (mod 5) ⇐⇒ x ≡ 2 (mod 5)
x ≡ 32 (mod 3 · 52) ⇐⇒{x ≡ 32 (mod 3) ⇐⇒ x ≡ 2 (mod 3)x ≡ 32 (mod 52)⇐⇒ x ≡ 7 (mod 52)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Ejemplo continuacion
Nos quedamos con las que involucran a la mayor potencia decada primo:
x ≡ 2 (mod 9), x ≡ 7 (mod 8), x ≡ 7 (mod 25)
cuyos modulos son mutuamente primos entre sı, y podemosaplicarle los metodos anteriores, basados en el Teorema Chinode los restos, para encontrar la solucion general
x ≡ 407 (mod 1800).
Este metodo descrito es muy util cuando se resuelve un sistemaa mano pero no es algoritmizable. Si lo que queremos es unalgoritmo que podamos programar en un ordenador nosbasamos en la demostracion del Teorema Chino de los restosuna vez resuelta cada una de las ecuaciones del sistemamediante el Algoritmo Extendido de Euclides.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Algoritmo de resolucion de un sistema de congruenciaslineales
P1 Resolver cada ecuacion aix ≡ bi (mod ni) del sistemapara convertirlo en uno del tipo x ≡ ai (mod ni)Si alguna carece de solucion el sistema no la tiene.
P2 Comprobar que mcd (ni, nj) divide a ai − ajSi falla algun caso, el sistema no tiene solucion.
P3 Descomponer cada ecuacion en un sistema.P4 Eliminar las ecuaciones que no son necesarias.P5 Calcular n (producto de los modulos resultantes),
ci = n/ni y di soluciones de las ecuacionescix ≡ 1 (mod ni)
P6 El sistema es equivalente a la congruenciax ≡
∑i aicidi (mod n)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Criterios de divisibilidad
Teorema
Sea P (x) un polinomio con coeficientes enteros y sea n ≥ 1.
a ≡ b (mod n) =⇒ P (a) ≡ P (b) (mod n)
Aplicacion: Obtencion de criterios de divisibilidad.Sea N = anan−1 . . . a1a0 con 0 ≤ ai ≤ 9 la expresiondecimal de un entero N .
N = an10n+· · · a110+a0 = P (10) con P (x) = anxn+· · · a1x+a0
Divisibilidad por 3:
10 ≡ 1 (mod 3) =⇒ N = P (10) ≡ P (1) =n∑i=0
ai (mod 3)
Un numero es divisible por 3 si, y solo si, lo es el numeroformado por la suma de sus cifras.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Criterios de divisibilidad
Criterio de divisibilidad por 9
10 ≡ 1 (mod 9)⇒ N = P (10) ≡ P (1) =
n∑i=0
ai (mod 9)
Un numero es divisible por 9 si, y solo si, lo es el numeroformado por la suma de sus cifras.
Criterio de divisibilidad por 11
10 ≡ −1 (mod 11)⇒ N ≡ P (−1) = a0−a1+··+(−1)nan (mod 11)
Un numero es divisible por 11 si, y solo si, lo es numeroresultante de sumar las cifras que ocupan lugar par yrestarle la suma de las cifras que ocupan lugar impar.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Aplicacion congruencias
Como n|m⇔ m ≡ 0 (mod n), se sigue que los problemas sobredivisibilidad son equivalentes a los problemas sobre congruenciasy, estos ultimos son, a veces, mas faciles de resolver.
EJEMPLO
Probar, mediante congruencias, que 32n+5 + 24n+1 es divisiblepor 7 cualquiera que sea el entero n ≥ 1.Trabajando modulo 7 se tiene que
32n+5+24n+1 = 35·32n+2·24n = 243·9n+2·16n ≡ 5·2n+2·2n = 7·2n ≡ 0
es decir, 7 divide a 32n+5 + 24n+1
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Aplicacion a Criptografıa
Numeramos las letras del alfabeto (en la practica, los 256codigos ASCII)
= 00 A = 01 B = 02 C = 03 D = 04 E = 05F = 06 G = 07 H = 08 I = 09 J = 10 K = 11
L = 12 M = 13 N = 14 N = 15 O = 16 P = 17Q = 18 R = 19 S = 20 T = 21 U = 22 V = 23W = 24 X = 25 Y = 26 Z = 27
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
Criptografıa asimetrica
La constituyen los codigos criptograficos que utilizan clavesdiferentes para cifrar y descifrar.Esto nos permite que la clave que se usa para cifrar puedaser publica siempre que la clave para descifrar sea privada,es decir, conocida unicamente por el destinatario, nisiquiera por el remitente.Codigos de clave publica: RSA (Este metodo fuedesarrollado en 1978 por R.L. Rivest, A. Shamir y L.Adleman y es conocido como sistema criptografico RSA).Para cifrar un mensaje se reagrupa el texto en bloques deigual longitud, es decir, en grupos de r letras cada uno.Ası, por ejemplo, si el texto es HOLA A TODOS yelegimos r = 4 quedara reagrupado de la forma
HOLA− A T−ODOS → 08161201−00010021−16041620
A cada uno de estos numeros lo denominaremos palabra yvamos a cifrar palabra a palabra.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
RSA
La clave publica: Es una pareja de enteros (n, e) talesque
n sea primo con cualquier posible palabra de un texto. Estacondicion se garantiza si cualquier divisor primo de n esmayor que la mayor palabra posible: para r = 4,pmın = 27272727.e debe ser primo con φ(n).
La clave privada: Es la pareja (n, d) donde
d = e−1 (mod φ(n))
Observese que al haber elegido e primo con φ(n), e esinvertible (es una unidad) en Zφ(n), por lo que tenemosgarantizada la existencia de d.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
El cifrado y el descifrado
El cifrado: Si N es una palabra del texto y (n, e) es laclave publica a utilizar, la palabra cifrada C se obtiene
N → C = N e (mod n)
El descifrado: Si C es una palabra cifrada del texto y(n, d) es la clave privada, la palabra descifrada N se obtiene
C → N = Cd (mod n)
Es decir, se trata de volver a cifrar la palabra cifrada Cutilizando ahora la clave privada. Por serd = e−1 (mod φ(n)), se tiene que ed+ αφ(n) = 1 conα ∈ Z. Al haber elegido n primo con cualquier posiblepalabra del texto tenemos asegurado que N ⊥ n y elteorema de Euler nos dice que Nφ(n) ≡ 1 (mod n).
Cd = N e·d ≡ N e·d(Nφ(n))α (mod n)
Nd·e+αφ(n) = N1 = N (mod n)
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La eleccion de una clave segura
Una clave segura es aquella que garantiza la privacidad dela clave privada (n, d). Como los enteros (n, e) son publicos,la seguridad de la clave consiste en la imposibilidad de laobtencion del entero d que forma parte de la clave privada.Dado que d = e−1 (mod φ(n)) y tanto e como n sonpublicos, parece imposible obtener una clave segura.Pero, para obtener d, primero debemos conocer φ(n) y paraello factorizar n, problema computacionalmente imposiblepara valores grandes de n.Si elegimos dos primos p y q de un numero de dıgitossuficientemente grande nos sera muy facil obtener n = p · qy dado que disponemos de los valores de p y q calcularφ(n) = (p− 1)(q − 1) para elegir posteriormente un enteroe primo con φ(n) que junto con el valor de n constituya laclave (n, e) que haremos publica, con la seguridad de quenadie podra calcular el valor de d, por lo que nadieconocera nuestra clave privada (n, d).
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
El proceso
Supongamos que tres personas A, B y C hacen publicassus respectivas claves (nA, eA), (nB, eB) y (nC , eC).
Si A quiere enviar un mensaje M a B lo cifra con la clavepublica (nB, eB) del destinatario B.
Cuando B recibe el mensaje, es capaz de descifrarlo puesconoce su clave privada (nB, dB).
Si C intercepta el mensaje, no puede descifrarlo pues noconoce la clave privada de B (nB, dB), ya que para ellonecesitarıa factorizar nB y eso no es posible.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular
La firma
Para evitar que B reciba un mensaje aparentementeenviado por A pero de hecho enviado por C para tratar deconfundirlo, se establece la denominada firma.
Dicha firma F se codifica dos veces:
F(nA,dA)→ F ′
(nB ,eB)→ F ′′
A conoce su clave privada (nA, dA) y la clave publica de B,(nB, eB).
Al recibirlo B, realiza el proceso inverso
F ′′(nB ,dB)→ F ′
(nA,eA)→ F
B conoce su clave privada (nB, dB) y la clave publica de A,(nA, eA).
Para que C le enviase un mensaje a B con vistas a que estepensase que procedıa de A serıa necesario que C conocierala clave privada (nA, dA) de A y eso no es posible.
Magdalena Fernandez Lebron [email protected] Tema 4: Aritmetica Modular