Appunti di Aritmetica, aritmetica modulare, crittografia e combinatoria

La fattorizzazione di un numero

La fattorizzazione è un processo lento per trovare i fattori primi di un numero. Se un numero, chiamato a, non è primo, allora esistono due numeri, chiamati b e c, tali che a = b * c. Il più piccolo dei multipli comuni si chiama minimo comune multiplo (mcm).

Inoltre, il massimo comune divisore (mcd) di a e b, indicato come mcd(a, b), è il più grande numero intero che divide sia a che b. L'ordine di a modulo b, indicato come ord(a, b), è la potenza più alta di p che divide a.

Definizione di aritmetica modulare:

Siano a, b, m numeri interi. Diciamo che a è congruente a b modulo m se a - b è un multiplo di m, cioè a ≡ b (mod m).

Vogliamo studiare le classi di equivalenza. Diciamo che a è congruente a c modulo m se a ≡ b (mod m) e b ≡ c (mod m). Questa relazione di equivalenza divide l'insieme degli interi in classi di equivalenza.

Ad esempio, se a = 12 e m = 5, allora il resto della divisione intera tra a e m è 2, quindi possiamo indicare a ≡ 2 (mod 5).

se e solo se Jk ez, web+kmDati a intezi au b, c, d con a=b (mod m)ord (mod am)1) atos bud mod m)2) a-cabd (mod m)wiczb.d mod miEsempi :ISBN-10to .. Xg, Xio Ko;-Kg EXO...9} 40620...Xio è il numero di contcollo, infattiŹ ixi 30 mod 1)EAN-13 Xo... X13 E{0--9}, Xio numero di:Einfatti mnt 3X+X3+3*4 + X5+3% + X2 + 2xg+Yg +3% +X4+34**= (modio)4:13 2 come ISBN 60 com prefissi 914,978, 979 e lo10stessa regola di Eoun 13Kaioi=1siamosia a 67a ē invertibile nodulo m se esiste bed: au-b=1 (mod m)inoltre b é amico modulo minoltre a ê invertibile mod m so a solo se madlar, mota, mn 27Wib, c, m, x 6 Z, mo, acz1(mood m). AllowsAlbonaax=b (mod m) se e solo se x=bc (mod m)Inoltre, l'equazione axa b(mood, my how solutionse e solo se med(or, m) Ib e me ha macam manaLe solution, di ax=b (mod mi sono le stesse (pot x) diax+ bn y=bPer i sistemi: Teorema cinese dei restoSiamo mai.., mm interi positivi relativamente primicsiano an,...gount ,sia m = m.m. Allorail sistema (x= a (mod

ma) ha un'unica soluzione

modulo mx = a (mod man

Per trovarlo : consideriamo Mism...mic, Mira

quindi mcd (Mi, mi)=1 => Fy;: Mig; = 1 (modra

La soluzione ē : *= au Mageto Mayo (moon)

il terrena cinese dei resti si uso per fare

calcoli com grossi numeri nei computer

inoltre piccolo teorema di Fermat

sia pun primo e a Ga. Allora

Nzafnod p)& se pta allora al = 1(mod p)

il teorema implica aume I, nr1, madla, n) = 1

se an- 1 (modmy alloca in mon é paimo"

Posso dire che un numero non é pamo se

uta trovare a.fattoritzauzione, ma non funziona sempre

Lasono- Ccrittografia: Applicazione dekk aritmetica modulare

il mittente trasforma un messaggio Mim Ce mond

le destinatario ha una funzione che trasforma

in M. Le funzionibasate su chiavifiſh) : M -> C hi chiave di criptazioney (e):c-Me, chiave di decriptatione

Simmetrica: he e sono in relazione tra le

Execupio: Crittografia di Cesaresi spostano di an posti le lettere

dell'alfabeto

Asimmetrica: hel nom somo collegate

loemolto difficile scoprire la relazionela chiave di criptatione puó esserpubblicaEsempio: l'algoritmo RSASiamo Pia due primi, n= pq e siamoe, de tali che ed = imod (p-1) (9-1))sios AEZ, allo ca 43 A (mod p) = 4&euro; (mod q)O<45 msomo soluzioni del sistena(x=A (modalda teorema cinese dei resti AFA (mod n)Quindi: mie, pubblicoAccomod m = Ad, privatoper un messaggio deo :codifico M > Me=c (mod n)M•decodifico ch_> cd= M (mod myLa sicuretta è basata sual fatto che non si conosce uned{x a modesA e pedAedse conosco pe o l'algoritmo non e sicuw 12345