Download IMD-IS. Aritmética modular

IMD-IS. Aritmética modular
Emmanuel Briand
ETSII. Universidad de Sevilla.
Emmanuel Briand
IMD-IS. Aritmética modular
Clases de congruencia modulo n
Pares e impares: clases modulo 2
Pares =
Impares
{. . . , −2, 0, 2, 4, 6, . . .} (resto 0)
= {. . . , −1, 1, 3, 5, 7, . . .} (resto 1).
Emmanuel Briand
IMD-IS. Aritmética modular
Clases de congruencia modulo n
Pares e impares: clases modulo 2
Pares =
Impares
{. . . , −2, 0, 2, 4, 6, . . .} (resto 0)
= {. . . , −1, 1, 3, 5, 7, . . .} (resto 1).
Clases modulo 3
{. . . , −3, 0, 3, 6, 9, . . .} (resto 0)
{. . . , −2, 1, 4, 7, 10, . . .} (resto 1)
{. . . , −1, 2, 5, 8, 11, . . .} (resto 2)
Más generalmente, tenemos n clases modulo n.
Emmanuel Briand
IMD-IS. Aritmética modular
Suma y producto modulo 2
+
PAR
IMPAR
×
PAR
IMPAR
PAR
PAR
IMPAR
PAR
PAR
PAR
IMPAR
IMPAR
PAR
IMPAR
PAR
IMPAR
+
[0] [1]
[0] [0] [1]
[1] [1] [0]
Emmanuel Briand
×
[0] [1]
[0] [0] [0]
[1] [0] [1]
IMD-IS. Aritmética modular
Suma y producto modulo 6
+
0
1
2
3
4
5
×
0
1
2
3
4
5
0
0
1
2
3
4
5
0
0
0
0
0
0
0
1
1
2
3
4
5
0
1
0
1
2
3
4
5
2
2
3
4
5
0
1
2
0
2
4
0
2
4
3
3
4
5
0
1
2
3
0
3
0
3
0
3
4
4
5
0
1
2
3
4
0
4
2
0
4
2
5
5
0
1
2
3
4
5
0
5
4
3
2
1
Emmanuel Briand
IMD-IS. Aritmética modular
Suma y producto modulo 7
+
0
1
2
3
4
5
6
×
0
1
2
3
4
5
6
0
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
1
2
3
4
5
6
0
1
0
1
2
3
4
5
6
2
2
3
4
5
6
0
1
2
0
2
4
6
1
3
5
3
3
4
5
6
0
1
2
3
0
3
6
2
5
1
4
4
4
5
6
0
1
2
3
4
0
4
1
5
2
6
3
5
5
6
0
1
2
3
4
5
0
5
3
1
6
4
2
6
6
0
1
2
3
4
5
6
0
6
5
4
3
2
1
Emmanuel Briand
IMD-IS. Aritmética modular
Los tres tipos de elementos en Zn
Los elementos de
Zn
se reparten entre tres clases:
Unidades
Divisores de cero
y ponemos el [0] aparte.
Emmanuel Briand
IMD-IS. Aritmética modular
Notaciones
Las tres expresiones siguientes son sinónimas:
[x ]n = [y ]n
x
≡y
Existe un entero k tal que x
mod n
= y + kn
Ejemplo importante
[x ]n
es una unidad si y solo si
existe a, ax
≡1
mod n.
Emmanuel Briand
IMD-IS. Aritmética modular
Notaciones
Las tres expresiones siguientes son sinónimas:
[x ]n = [y ]n
x
≡y
Existe un entero k tal que x
mod n
= y + kn
Ejemplo importante
[x ]n
es una unidad si y solo si
existe a, existe k tal que ax
+ kn = 1
Emmanuel Briand
IMD-IS. Aritmética modular
Notaciones
Las tres expresiones siguientes son sinónimas:
[x ]n = [y ]n
x
≡y
Existe un entero k tal que x
mod n
= y + kn
Ejemplo importante
[x ]n
es una unidad si y solo si
a y n son coprimos.
Emmanuel Briand
IMD-IS. Aritmética modular
Cálculo del inverso
Modulo 1745, ¾ cuáles son los inversos de las clases de:
1485 ?
1744 ?
2 ?
333 ?
Calcular un inverso se puede hacer por medio del algoritmo de
Euclides extendido.
Emmanuel Briand
IMD-IS. Aritmética modular
Sistemas de ecuaciones modulares




≡1
x ≡ 2
2x ≡ 1



x ≡ 4
3x
mod 2
mod 3
mod 5
mod 7
Emmanuel Briand







x
x
x
x
≡1
≡2
≡3
≡4
IMD-IS. Aritmética modular
mod 2
mod 3
mod 5
mod 7
ax ≡ b mod n
ax
≡b
mod n
Hay tres casos:
Si [a] es una unidad (a y n coprimos): sea [c ] su inversa. La
ecuación es equivalente a:
x
Sino, sea d
≡ bc
mod n
= Mcd(a, n).
Si d no divide b, no hay solución.
Si d divide b, la ecuación se simplica en:
a
d
x
≡
Emmanuel Briand
b
d
mod
n
d
IMD-IS. Aritmética modular
Resolución: dos ecuaciones
x
x
≡ b1
≡ b2
Emmanuel Briand
mod q1
mod q2
IMD-IS. Aritmética modular
Resolución: dos ecuaciones
x
x
≡ b1
≡ b2
mod q1
mod q2
La primera ecuación es equivalente a:
Existe k tal que x
= b1 + q1 k
Ahora resolvemos en k .
Puede no haber soluciones, pero si hay soluciones, son de la forma:
k
≡c
mod q2
Es equivalente a:
Existe j tal que k
= c + q2 j
Para x :
x
= b1 + q1 (c + q2 j ) = . . . + jq1 q2
Es decir
x
≡ ...
Emmanuel Briand
mod q1 q2
IMD-IS. Aritmética modular
La forma del conjunto de las soluciones









x
x
≡ b1
≡ b2


mod q1
mod q2
.
.
.
x
≡ br

x
x
x
≡1
≡0
≡2
mod 2
mod 3
mod 5
mod qr
Teorema chino de los restos, caso fácil
Si para cada par
(i , j )
con i
6= j ,
los moduli qi y qj son coprimos,
entonces el conjunto de los soluciones es una clase modulo el
producto de los moduli q1 q2
· · · qr ..
Emmanuel Briand
IMD-IS. Aritmética modular
La forma del conjunto de las soluciones









x
x
≡ b1
≡ b2


mod q1
mod q2
.
.
.
x
≡ br

x
x
x
≡1
≡0
≡2
mod qr
Teorema chino de los restos, caso general
En general, el conjunto de las soluciones es:
o bien vacío
o bien una clase modulo mcm(q1 , q2 , . . . , qr ).
Emmanuel Briand
IMD-IS. Aritmética modular
mod 2
mod 3
mod 5
Forma más completa del teorema chino de los restos
Consecuencia del teorema chino de los restos:
Ej: 30
= 2 × 3 × 5,
los factores son coprimos.
[x ]30 7−→ ([x ]2 , [x ]3 , [x ]5 )
Es una biyección de
Z30
en
Z2 × Z3 × Z5 .
07→(0, 0, 0)
107→(0, 1, 0)
207→(0, 2, 0)
17→(1, 1, 1)
117→(1, 2, 1)
217→(1, 0, 1)
27→(0, 2, 2)
127→(0, 0, 2)
227→(0, 1, 2)
37→(1, 0, 3)
137→(1, 1, 3)
237→(1, 2, 3)
47→(0, 1, 4)
147→(0, 2, 4)
247→(0, 0, 4)
57→(1, 2, 0)
157→(1, 0, 0)
257→(1, 1, 0)
67→(0, 0, 1)
167→(0, 1, 1)
267→(0, 2, 1)
77→(1, 1, 2)
177→(1, 2, 2)
277→(1, 0, 2)
87→(0, 2, 3)
187→(0, 0, 3)
287→(0, 1, 3)
97→(1, 0, 4)
197→(1, 1, 4)
297→(1, 2, 4)
Emmanuel Briand
IMD-IS. Aritmética modular
El número de unidades en Zn
Recordamos: [a] es una unidad de
La función
φ
Zn
si y solo si a es coprimo con n.
de Euler
La aplicación que asocia a n el número de unidades modulo n se
llama función
φ
de Euler () y se nota
φ.
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
Emmanuel Briand
IMD-IS. Aritmética modular
Formulas para la función φ de Euler
Unos casos particulares simples:
n
=p
(primo)
n
= pr
n
(potencia de primo)
= pq
(producto de dos primos distintos
φ(n) = p − 1
φ(n) = p r −1 (p − 1)
φ(n) = (p − 1)(q − 1)
φ(n)
φ(n)
φ(n)
n
= (1 − p1 )
n
= (1 − p1 )
Emmanuel Briand
n
= (1 − p1 )(1 − q1 )
IMD-IS. Aritmética modular
Formula general para la función φ de Euler
Formula general para la función de Euler
Si n
= p1r1 p2r2 · · · pkrk
(descomposición en primos, es decir los pi son
primos distintos y los ri son
> 0),
entonces
φ(n)/n = (1 − 1/p1 )(1 − 1/p2 ) · · · (1 − 1/pr )
Emmanuel Briand
IMD-IS. Aritmética modular
Las potencias de una unidad
2
Calculamos a, a , a
3
. . . modulo n.
Emmanuel Briand
IMD-IS. Aritmética modular
Las potencias de una unidad
2
Calculamos a, a , a
3
. . . modulo n.
Teorema de Euler
Sea
φ(n)
el número de unidades modulo n. Entonces:
a
φ(n)
≡1
mod n
Emmanuel Briand
(para a coprimo con n)
IMD-IS. Aritmética modular
Las potencias de una unidad
2
Calculamos a, a , a
3
. . . modulo n.
Teorema de Euler
Sea
φ(n)
el número de unidades modulo n. Entonces:
a
φ(n)
≡1
(para a coprimo con n)
mod n
Pequeño teorema de Fermat
Si p es primo entonces:
a
p −1
≡1
mod p
(para a no múltiplo de p )
Emmanuel Briand
IMD-IS. Aritmética modular
Simplicación de cálculos de grandes potencias (con un
pequeño modulo)
Calcular 2
1000
modulo 53.
Emmanuel Briand
IMD-IS. Aritmética modular
Simplicación de cálculos de grandes potencias (con un
pequeño modulo)
Calcular 2
1000
modulo 53.
El número 53 es primo (y 2 no es múltiplo de 53). Por el pequeño
teorema de Fermat, 2
52
≡1
mod 53.
Claro , tenemos también
2
Calculamos 1000
104
≡ 2156 ≡ · · · ≡ 1
mod 53
mod 52, tenemos:
1000
= 19 × 52 + 12
Por lo tanto:
2
1000
= (252 )19 × 212 ≡ 119 × 212 ≡ 212
mod 53
Este cálculo puede hacerse a mano.
Emmanuel Briand
IMD-IS. Aritmética modular
Test de primalidad: test de Fermat
Sea a con 0
< a < p.
Si p NO pasa el test de Fermat en base a (es decir: si a
p
6≡ 1
mod p) entonces queda demostrado que p no es primo.
Si p pasa el test de Fermat en base a, entonces p puede ser
primo o no. Pero probablemente lo es.
Emmanuel Briand
IMD-IS. Aritmética modular
Test de primalidad: test de Fermat
Sea a con 0
< a < p.
Si p NO pasa el test de Fermat en base a (es decir: si a
p
6≡ 1
mod p) entonces queda demostrado que p no es primo.
Si p pasa el test de Fermat en base a, entonces p puede ser
primo o no. Pero probablemente lo es.
Para los enteros
< 100 000:
Proporción de primos: 9, 6 %.
Porporción de no primos que pasan el test de Fermat en base
2: 0, 078 %. La probabilidad de no ser primo pasando el test
es: 0, 81 %.
Emmanuel Briand
IMD-IS. Aritmética modular
Exponenciación rápida modular
Ejemplo de cálculo de a
En
Zn , donde n
e=
e mod n
tiene 520 cifras decimales, queremos calcular 2
e con
21296030073134284288338650858589188423664700096843949738
30389790731064167107488788931123422658660437316652890057
87483780386120271622964903883759506751921231714044369373
07484337419905426252983925649385894548909400852148161881
75481883182508834409971051959433672221049428272799288060
33089390061346156788765830755067658931895709032029937028
58343604716055508161586473290122638688568546900544834155
2620802273008678257385909313
Exponenciación ingenua:
e −1
multiplicaciones ½ Tarda una
eternidad !
Exponenciación rápida: 1788 multiplicaciones. ½ Inmediato !
Emmanuel Briand
IMD-IS. Aritmética modular
Pequeño ejemplo con RSA
Trabajamos modulo n
= 91
y mandamos como mensajes m
números entre 1 y 6 (incluidos).
Ciframos con m
7→ me
(n, e ) = (91, 5).
Desciframos con c
mod n, con e
7→ c d
= 5.
mod n, con d
La clave pública es
= 29.
La clave privada es
(n, d ) = (91, 29).
Diccionario:
Emmanuel Briand
IMD-IS. Aritmética modular
Pequeño ejemplo con RSA
Trabajamos modulo n
= 91
y mandamos como mensajes m
números entre 1 y 6 (incluidos).
Ciframos con m
7→ me
(n, e ) = (91, 5).
Desciframos con c
mod n, con e
7→ c d
= 5.
mod n, con d
La clave pública es
= 29.
La clave privada es
(n, d ) = (91, 29).
Diccionario:
Mensaje en claro
Mensaje cifrado
1
1
2
32
3
61
4
23
5
31
6
41
Emmanuel Briand
IMD-IS. Aritmética modular
Transmisión de un mensaje con RSA
Transmitimos números=mensajes codicados en un canal inseguro.
m
=
número entre 1 y M , mensaje en claro.
Codicamos el mensaje antes de transmitirlo (lo representamos
como un número, por medio de un proceso público).
Ciframos: c
= me
mod n, c es el mensaje cifrado
Trasmitimos c .
A la recepción, se descifra c por medio de la formula: m
mod n y se descodica.
Emmanuel Briand
IMD-IS. Aritmética modular
= cd
Transmisión de un mensaje con RSA
Transmitimos números=mensajes codicados en un canal inseguro.
m
=
número entre 1 y M , mensaje en claro.
Codicamos el mensaje antes de transmitirlo (lo representamos
como un número, por medio de un proceso público).
Ciframos: c
= me
mod n, c es el mensaje cifrado
Trasmitimos c .
A la recepción, se descifra c por medio de la formula: m
= cd
mod n y se descodica.
Hace falta que m
= (me )d
mod n para todos los mensajes en claro
posibles.
Emmanuel Briand
IMD-IS. Aritmética modular
Transmisión de un mensaje con RSA
Transmitimos números=mensajes codicados en un canal inseguro.
m
=
número entre 1 y M , mensaje en claro.
Codicamos el mensaje antes de transmitirlo (lo representamos
como un número, por medio de un proceso público).
Ciframos: c
= me
mod n, c es el mensaje cifrado
Trasmitimos c .
A la recepción, se descifra c por medio de la formula: m
= cd
mod n y se descodica.
Hace falta que m
= (me )d
mod n para todos los mensajes en claro
posibles. Esto ocurre cuando:
Todos los mensajes en claro son coprimos con n. Elegir
M
<
ed
≡1
menor factor primo de n.
mod
φ(n)
(por el Teorema de Euler).
Emmanuel Briand
IMD-IS. Aritmética modular
¾ Como fueron elegidos les claves (n, e ) y (n, d ) ?
Trabajamos modulo n
= 91
y mandamos como mensajes m
números entre 0 y 6 (incluidos).
Ciframos con m
7→ me
(n, e ) = (91, 5).
Desciframos con c
mod n, con e
7→ c d
= 5.
mod n, con d
La clave pública es
= 29.
La clave privada es
(n, d ) = (91, 29).
Emmanuel Briand
IMD-IS. Aritmética modular
¾ Como fueron elegidos les claves (n, e ) y (n, d ) ?
Trabajamos modulo n
= 91
y mandamos como mensajes m
números entre 0 y 6 (incluidos).
Ciframos con m
7→ me
(n, e ) = (91, 5).
Desciframos con c
mod n, con e
7→ c d
= 5.
mod n, con d
La clave pública es
= 29.
La clave privada es
(n, d ) = (91, 29).
= 7 y q = 13.
= pq. Tenemos n = 91, φ(n) = 72.
Elegimos M = 6 (importa que M < p). Elegimos
corresponde es d = 29.
Hemos elegido dos primos p
Ponemos: n
Emmanuel Briand
e
= 5.
IMD-IS. Aritmética modular
El d que le
Ejemplo de clave RSA 1024 bits
p
=
1088674954135031448070360672486207340789233108502873
9956397237105547037176615145623548568640250593833590
973843267235567109644848147330427379985520112979269,
q
=
1102966700842980716537314503991462186490108279882492
0292638334301839453387017970315771818785871989403805
508820838149133951943902116850319780199515561950161,
n
=
=
p
×q
1200772222452698983587363892507754632069773183051649
3143139194894316519075033872598235904950479409900825
1045283703751376633771055728609203858170596884456881
2459785890404876326478825394048109189324147035669670
8392439679232254365104192153883529037509434620051856
0043825917460473370490508587653084011973404212309.
Emmanuel Briand
IMD-IS. Aritmética modular
φ(n) = (p − 1)(q − 1)
= 1200772222452698983587363892507754632069773183051649
3143139194894316519075033872598235904950479409900825
1045283703751376633771055728609203858170596884456859
3295620392603659865711307746281156461390008197133068
3488882538493605308740880559951490294897176296312207
7379720532759411781740244406905923826937729282880,
e
=
17,
d
=
=
inverso de e modulo
φ(n),
2825346405771056431970267982371187369575936901297998
3866209870339568280176550288466437423412892729178412
0106549891179709726520131126139303195695522081074963
1283812688479199684026606461838015203270607522666043
1738547149396718373507954258709388929169826579558135
854051890061038066291822213389629135750053948913.
Emmanuel Briand
IMD-IS. Aritmética modular
Otro ejemplo con RSA
Encodamos MARTES, cambiando cada letra por su posición en el
alfabeto inglés (26 letras, A=1, B=2,. . . ). Esto nos da 6 enteros,
que son considerados como 6 mensajes diferentes:
13, 1, 18, 20, 5, 19
Con la clave pública
(n, e ) = (2491, 17),
cifrar estos mensajes.
Se intercepta el mensaje cifrado [1838,764,1072,2081,1072,2470],
cifrado con las misma clave publica, ¿ Como lo descifrarías ?
Emmanuel Briand
IMD-IS. Aritmética modular