Matematiques aplicades a la vida quotidiana
Merce Llabres
UOM, 2013
L’aritmetica del rellotge: els codis decontrol
2 de 28
L’aritmetica del rellotge
3 de 28
L’aritmetica del calendari
Si consideram els dies de la setmana, si estam a divendres ipassen 3 dies, on estarem?
Si miram els numerets d’abaix resulta que 5+3=1
4 de 28
Aritmetica modular
Fixem enter N > 1:
Congruencies
• a, b ∈ Z congruent modul N si N |a− b o, equivalentment si elresidu de dividir a i b per N es el mateix
• Notacio: a ≡ b (mod N)
Exemple
53 ≡ 5 (mod 8) 42 ≡ 9 (mod 11)
5 de 28
ExemplePrenem N = 6; aleshores Z6 te 6 elements:
[0] = {. . . ,−6, 0, 6, 12, . . . }[1] = {. . . ,−5, 1, 7, 13, . . . }[2] = {. . . ,−4, 2, 8, 14, . . . }[3] = {. . . ,−3, 3, 9, 15, . . . }[4] = {. . . ,−2, 4, 10, 16, . . . }[5] = {. . . ,−1, 5, 11, 17, . . . }
6 de 28
Calcul de la lletra de control de DNI
Pel calcul de la lletra de control del DNI, s’utilitza l’aritmeticamodular a Z23:
• es consideren 23 lletres de l’alfabet per fer la identificacio ambel residu, una vegada eliminades aquelles que no existeixen enl’alfabet internacional (com la n) o les dobles (com Ll o Ch)
• es calcula el residu de la divisio del numero de DNI entre 23 is’assigna una lletra, segons la taula seguent
7 de 28
Calcul de la lletra de control de DNI
Residu Lletra Residu Lletra0 T 12 N1 R 13 J2 W 14 Z3 A 15 S4 G 16 Q5 M 17 V6 Y 18 H7 F 19 L8 P 20 C9 D 21 K10 X 22 E11 B
Exemple: 55555555-K
55555555 = 23× 2415458 + 21
ExerciciComprova la lletra del teu DNI
8 de 28
9 de 28
10 de 28
Calcul del dıgit de control d’un codi de barres
Exercici
Cerca codis de barres de productes que no tenguin el prefixespanyol
11 de 28
Operacions amb classes de congruencia
Sobre ZN : operacions de suma i de producte:
[a] + [b] = [a + b]
[a] · [b] = [a · b]
12 de 28
Aplicacio: la prova del 9
Divisio:
13 de 28
Aplicacio: la prova del 9
Multiplicacio:
14 de 28
ExempleLa taula de la suma a Z6 es:
+ [0] [1] [2] [3] [4] [5][0] [0] [1] [2] [3] [4] [5][1] [1] [2] [3] [4] [5] [0][2] [2] [3] [4] [5] [0] [1][3] [3] [4] [5] [0] [1] [2][4] [4] [5] [0] [1] [2] [3][5] [5] [0] [1] [2] [3] [4]
15 de 28
ExempleLa taula del producte a Z6 es:
· [0] [1] [2] [3] [4] [5][0] [0] [0] [0] [0] [0] [0][1] [0] [1] [2] [3] [4] [5][2] [0] [2] [4] [0] [2] [4][3] [0] [3] [0] [3] [0] [3][4] [0] [4] [2] [0] [4] [2][5] [0] [5] [4] [3] [2] [1]
16 de 28
Proposicio[a] ∈ ZN invertible ⇐⇒ mcd(a, N) = 1
Exemple
Z∗6 = {[1], [5]}
Maxim comu divisorDonats a, b ∈ Z :
• mcd(a, b) major divisor comu positiu de a i b
Mınim comu multiple
• mcm(a, b) menor multiple comu positiu de a i b
17 de 28
Algoritme d’Euclides
• Donats a, b ∈ Z>0 l’altoritme d’Euclides serveix per calcular elmcd(a, b)
• A mes, l’algoritme extes d’Euclides serveix per trobar dosenters x , y tals que
mcd(a, b) = x · a + y · b
• L’algortime d’Euclides es bassa en el seguent fet:el residu r de dividir a entre b es el mateix que el de dividir bentre r
Com ho feim?...
18 de 28
Exemplemcd(4864, 3458):
i r q x y
0 4864 − 1 01 3458 − 0 12 1406 1 1 −13 646 2 −2 34 114 2 5 −75 76 5 −27 386 38 1 32 −457 0 2 −91 128
rk−2 = rk−1qk + rk xk = xk−2 − qkxk−1 yk = yk−2 − qkyk−1
Per tant, mcd(4864, 3458) = 38 = 32 · 4864 + (−45) · 3458.19 de 28
Calcul d’inversosSi [a] invertible, es pot trobar l’invers [a]−1 amb algorismed’Euclides estes:
mcd(a, N) = 1 =⇒ ∃x , sy : xa + yN = 1 =⇒
=⇒ [x ][a] = 1 =⇒ [a]−1 = [x ]
ExempleInvers de 35 modul 2452: 1 = (−17) · 2452 + 1191 · 35
[35]−12452 = [1191]2452.
ExerciciCalcular l’invers de [8]3520 de 28
El sistema criptografic RSA
Teorema petit de FermatSi p es primer, aleshores np ≡ n modul p
Per exemple:
• n2 ≡ n modul 2, perque o tots dos son parells o tots dos sonimparells
• 133 ≡ 13 modul 3: 133 − 13 = 2184 = 728× 3
Teorema d’EulerSi p, q son primers i n ∈ N, aleshores n · n(p−1)(q−1) ≡ n modulp · q
21 de 28
El sistema criptografic RSA
El sistema d’encriptat RSA (R. Rivest, A. Shamir, L. Adleman,1977) te 3 parts:
• Generacio de claus
• Encriptat
• Desencriptat
22 de 28
El sistema criptografic RSA
Generacio de claus:
• Trio dos primers grans de mida semblant p, q
• Faig N = p × q
• Calcul (p − 1)(q − 1)
• Trio 1 < e < (p − 1)(q − 1) coprimer amb (p − 1)(q − 1)
• Trob d ∈ N tal que d · e ≡ 1 modul (p − 1)(q − 1)
• Faig publics els valors de N i de e, guard els valors de p, q, d .
A banda, hem de disposar d’un metode convingut per codificartextos en nombres naturals (comunicam nombres)
23 de 28
El sistema criptografic RSA
Generacio de claus:
• Jo trio dos primers grans de mida semblant: 5 i 7
• Calcul N = 5× 7 = 35
• Calcul (p − 1)(q − 1) = 4× 6 = 24
• Trio 1 < e < 24 coprimer amb 24: e = 7 (mal fet!)
• Trob d ∈ N tal que 7d ≡ 1 modul 24: d = 7(7× 7− 1 = 48 = 2× 24)
• Faig publics els valors de N = 35 i de e = 7, guard els valorsde p = 5, q = 7, d = 7.
24 de 28
El sistema criptografic RSA
Encriptat: Quan em voleu comunicar un missatge:
• El tranformau en un nombre natural M (suposam M < N ; sino, el feu a bocinets)
• Calculau Me modul N
• M’enviau aquest valor M
Exemple:
• Em voleu comunicar el numero 8
• Calculau 87 modul 35: es 22(87 = 2.097.152 = 59.918× 35 + 22)
• M’enviau el 22
25 de 28
El sistema criptografic RSA
Desencriptat: Per llegir el missatge:
• Calcul Md modul N
• Dona M
• Ho traduesc a text
Exemple:
• Calcul 227 modul 35:227 = 2.494.357.888 = 71.267.368× 35 + 8
• El missatge que rep es 8, com volıeu
26 de 28
El sistema criptografic RSA
Per que el consideram segur?
• Es considera molt difıcil descompondre n = p · q en els seusfactors p, q. Els nombres mes grans que s’han pogutdescompondre amb algoritmes generals son ∼ 10230, i ara p, qs’agafen ∼ 10300
(100 milions d’ordinadors com aquest tardarien mes de 1000 anys, demitjana, en descompondre el p · q resultant)
• Sense coneixer una factoritzacio de n, es considera molt difıcilel problema d’extreure arrels modul n; es a dir, donat X ,trobar Y tal que Y e = X modul n
Pero no son problemes impossibles de resoldre: simplement no sesaben resoldre prou aviat27 de 28
Codificacio missatges
Xifrat de Cesar
• Missatges: M = Z26 (blocs de 1 caracter llatı)
• Criptogrames: C = Z26
• Funcions d’encriptacio i desencriptacio:
E (m) = m + 3 mod 26, D(c) = c − 3 mod 26
ExempleATAQUEU s’encripta en DWDTXHX
28 de 28