Formulario Matematica discreta

MATEMATICA DISCRETA

A

ARITMETICA Studio delle proprietà della somma e del prodotto in Z (insieme

n

MODULARE delle classi di congruenza modulo n)

Relazione Una relazione d’equivalenza su un insieme A è una relazione che è:

d’equivalenza - Riflessiva: aRa

- Simmetrica: aRb bRa



- Transitiva: aRb e bRc aRc



Classe di Se R è una relazione d’equivalenza su A introduciamo la classe

equivalenza d’equivalenza di a:

∈

[a] = {b A | aRb}

Relazione di

congruenza ∈

La relazione R:= { (a,b) ZxZ tali che n|a-b} è detta RELAZIONE

≡

DI CONGRUENZA MODULO n. Si può scrivere a b mod n oppure

≡

a b

n ≡

La relazione è di congruenza

n

Due interi sono congrui modulo n divisi per n danno lo stesso



resto

PROPRIETA’ SOMMA E PRODOTTO

[a] + [b] = [a+b] e [a] * [b] = [a*b]

n n n n n n

11+3=14=2

Es.

Per la somma vale la proprietà associativa, commutativa, c’è lo

zero, c’è l’opposto

Congruenza Per la moltiplicazione vale la proprietà associativa, commutativa,

lineare distributiva, ha l’unità e una classe è invertibile se esiste una classe

b a∗b=1

(inversa) tale che ≡

Una congruenza lineare è un’espressione del tipo ax c mod n

Risolverla vuol dire determinare gli u soluzioni della congruenza

lineare ≡

!!! ax c mod n ha soluzioni u l’equazione diofantea



ax+ny=c ha soluzioni,

≡

quindi ax c mod n ha soluzioni u d:=MCD(a,n)|c e



a c n

x ≡ mod

d d d ≡

Esercizio: Risolvere 12x 7 mod 15

Sol: d:= MCD(12,15)=3, 3 non divide 7 quindi non ci sono soluzioni

≡1

Esercizio: Risolvere 12x 5 mod 21

Sol: MCD(12,21)=3, 3 divide 15, ok

≡

Divido per d: 4x 5 mod 7

Risolvo l’equazione diofantea 4x+7y=5

La mia u è l’equazione delle soluzioni particolari di x, cioè u = 10 +

Equazioni 7k al variare di k

lineari in Z n Per raggrupparle divido k per d:= MCD(12,21)=3. Quindi k = q*3+r,

0 <= r < d(3)

u = 10+7k = 10+7(3q+r) = 10+21q+7r = (10+7r)+21q, 0 <= r <

d u 10+7r mod 21, 0 <= r < 3

≡

 Le soluzioni sono

quindi:

≡ ≡

r = 0 : u 10 + 7*0 10

21 21 ≡

x 10 mod 21

≡ ≡

r = 1 : u 10 + 7*1 17

21 21 ≡

x 17 mod 21

≡ ≡ ≡

r = 2 : u 10 + 7*2 24 3

21 21 21 ≡

x 3 mod 21

a x=c

Si tratta di espressioni della forma

a x=c ≡

ha soluzioni se e solo se ax c mod n ha soluzioni u

6 x=5∈Z

Esempio: risolvere 4 ≡

Dobbiamo risolvere la congruenza lineare 6x 5 mod 4, ma il

MCD(6,4)=2 non divide 5 quindi non ha soluzioni

Funzione di 12 x=15∈Z

Esempio: risolvere 21

φ

Eulero ( ) ≡

Dobbiamo risolvere 12x 15 mod 21. Le soluzioni sono

n u=17, 3, 10

UNA CLASSE IN Z è INVERTIBILE SE E SOLO SE IL MCD(a,n)=1

n x

In tal caso l’inverso è dove (x ,y ) è soluzione particolare della

0 0 0

diofantea ax+ny=1 2

Esempio: Stabilire se è invertibile in Z e nel caso determinare

15

l’inverso x

Esso è dove (x ,y ) è soluzione particolare di 2x+15y=1

0 0 0

MCD(2,15)=1 , ok quindi applico beizout: 2 * (-7) + 15 * (1) = 1 ->

Teorema di x = -7 in Z

0 15

Eulero-Fermat −7 +15=8

x

Siccome è negativo aggiungo 15: =

0

E Piccolo 2∗8=16=1

Per verificare: (posso sottrarre 15 quante volte

Teorema di voglio)

Fermat) φ

È utile per calcolare le classi invertibili in Z che indichiamo con

n

n - Consideriamo un numero primo positivo p e un naturale m

allora:

p ( ) φ φ

φ 2

m m m-1

) = p – p Es: =2-1=1; (3)=3-1=2;

¿

φ

(5)=5-1=4 φ φ 2 2 2-1

(4)= (2 )=2 -2 =2

ecc. per tutte le potenze di primi … φ φ

- Se a,b sono COPRIMI [MCD(a,b)=1] allora (a*b)= (a)*

φ (b)

φ φ φ

φ(2∗3)

Es: (6)= = (2)* (3) = (2-1)(3-1) = 2

) φ φ φ φ

φ(24 3 3 3

= (3*8)= (3*2 )= (3)* (2 )= (3-1)(2 -

2

2 )= 8

φ φ φ φ φ φ

(60)= (3*20)= (3*5*4)= (3)* (5)* (4)=(

3-1)(5-1)(4-2)= 16

(Qualsiasi numero si può scrivere come prodotto di numeri positivi)

( )

∈ ∈ φ n

≠

Se a Z, n N, con n 0 e MCD(a,n)=1 allora 1 mod

a ≡

n ∈

Se p è un primo positivo e a Z è tale che p non divide a, allora

≡

p-1

a 1 mod p 864533

Esercizio: calcolare il resto della divisione 5 per 42

Algoritmo RSA ( )

φ n

Sol: MCD(5,42)=1 1 mod n

 a ≡

( ) ( )∗φ ( )∗φ (7)

φ 42 ; Calcolo = = 12

φ 2 3

 φ( 42)

5 ≡1 mod 42

≡

12

Quindi: 5 1 mod 42. Per trovare il resto posso dividere

l’esponente per 12:

≡ ≡ ≡ ≡

864533 72044*12+5 72044*12 5 12 72044 5

5 5 5 *5 (5 ) *5

42 42 42 42

≡ ≡ ≡

72044 5 5

1 *5 5 3125 17

42 42 42

86453

Esercizio: “ ” di 131 per 42

Sol: siccome 131>42 posso dividerlo per 42 per semplificare:

≡ ≡

864533 864533

131=3*42+5 quindi 3 5. Quindi 131 5 e poi

42 42

continuo. 4382 2789

Esercizio: “ “ di 7 +13 per 30.

Sol: solito procedimento prima per uno e poi per l’altro e infine:

≡ ≡ ≡

4382 2789 4382 2789

7 19 e 13 13, quindi 7 +13 = 19+13 32

30 30 30

≡ 2

30 140

Esercizio: determinare le ultime due cifre di 3

Sol: Le ultime due cifre sono il resto della divisone per 100

( )

φ 100

Quindi MCD(3;100)=1 e per E.F: 3 ≡ 1mod 100

( )=40 ≡ ≡ ≡

φ 100 40 140 3*40+20 20

-> 3 1 quindi: 3 3 3 =

100 100 100

≡

3486784401 1

100

Le ultime due cifre sono 01.

Destinatario:

Sceglie due numeri primi molto grandi p e q, calcola il prodotto

φ φ

n=p*q e poi (n) e sceglie un numero e>1 tale che MCD(e,

(n))=1. La coppia (n,e) è la chiave pubblica.

Mittente:

Trasforma il messaggio in un numero M e lo suddivide in k blocchi di

lunghezza tale che M < MIN(p,q), per ogni i. Calcola il resto C della

i i

divisione di ciascun M per n: 0<= C < n per i=1,...,k e spedisce al

i i

destinatario il messaggio codificato C=(C C ,…,C )

1, 2 K

- Solo il destinatario può decodificare il messaggio: poiché MCD(e,

φ ≡ φ

(n))=1 la congruenza lineare ex 1 mod (n) ha

soluzione. Per trovarla basta risolvere l’equazione diofantea (ex+

φ ≡ φ

(n)y=1). Possiamo trovare d tale che ed 1 mod (n).

φ

Possiamo sostituire d con il resto della sua divisione per (n). La

coppia (n,d) saà la chiave privata con cui il destinatario

decodificherà il messaggio.

DECODIFICA:

≡ φ φ

ed 1 mod (n) -> (n)|ed-1 -> esiste h tale che ed=h*

φ (n)+1 ≡ ≡ ih*p(n)+1

id id ied

Calcola il resto della divisione C mod n. C M M

n n

≡ ip(n) h

(M ) *M

n i ≡ ≡

ip(n)

Poiché M <MIN(p,q) allora MCD(M ,n)=1 -> M 1

i i n

h

(1) *M =M cioè:

n i i

≡

d

C M (o<=M >=l<n) dove M è il resto. Riassemblo: M =

i n i i i

M ,M ,M ,…,M

1 2 3 k

Esempio: φ φ φ

p=11; q= 13 -> n=p*q=11*13=143; (n)= (11)*

(13)=10*12=120 φ

Scelgo e tale che MCD(e, (n))=1. e=7. La coppia (n,e)=(143,7) è

la chiave pubblica

Affinché M Max(p,q)=11, basta considerare blocchi di lunghezza

i<

l=1

Codifica: M=306 -> M =3, M =0, M =6

1 2 3

≡

1e 7

M = 3 =2187 42 =: C C = 42 0 85



143 1

2e 7

M = 0 =0 =: C 2 ≡

3e 7

M = 6 = 279936 85 =: C

143 3 ≡ φ

Per decodificare trovo d risolvendo ex 1 mod (n) cioè 7x

≡ 1mod 120 -> 7x+120y=1

Per Bezout trovo 7*(-17)+120*(1)=1. Allora -17 è una soluzione.

Scelgo d= -17+120=103. La coppia (n,d)=(143,103) è la chiave

privata ≡

1d 103

Decodifica: C =42 3 := M

143 1

M = M M M = 3 0 6



≡

2d 103

C = 0 0 := M 1 2 3

143 2

≡

d 103

C3 = 85 6 := M

143 3 C

COMBINATO DEF: Studio della cardinalità di insiemi finiti

RICA PRINCIPIO DELLA SOMMA

Se A e B sono insiemi disgiunti allora |A U B|= |A|+|B|

PRINCIPIO DEL PRODOTTO

A A

|A₁ x A₂ x … x | = | A₁| x | A₂| x … x | |

n n

PRINCIPIO DI INCLUSIONE-ESCLUSIONE

- Se A e B sono due insiemi, allora |A U B| = |A| + |B| - |A ∩ B|

- Se A, B e C sono tre insiemi, allora

|A U B U C | = |A|+|B|+|C|-|A ∩ B|-|A ∩ C|-|B ∩ C|+|A ∩ B ∩

C|

METODO DELLE SCELTE SUCCESSIVE

k

|P|= k₁ * k₂ * … * n

COEFFICIENTE BINOMIALE:

( ) n!

n = ( )

k k ! n−K !

BINOMIO DI NEWTON:

n ( )

n

∑

n k n−k

( ) =

x+ a x a

k

k=0

Esempi:

Su 100 studenti 80 hanno superato matematica, 70 logica e 60

entrambe.

Quanti di loro hanno superato almeno una delle due parti? Quanti

nessuna?

S: insieme studenti |S|= 100

M: studenti che hanno superato mate |M|=80

L: studenti che hanno superato logica |L|=70

M ∩ L M ∩ L

: studenti che hanno superato entrambe | |=60

∪ ∪

M L M L

: studenti che hanno superato