Appunti di Matematica Discreta - people.unipmn.itpeople.unipmn.it/manzini/matdis/matdis.pdf · 1.2...

1

Appunti di Matematica Discreta (19 novembre 2009)

1 I numeri interi

Indichiamo con Z l’insieme dei numeri interi, cioe

Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.

Se parliamo di interi positivi indichiamo l’insieme {1, 2, 3, . . .}. Con l’espressione interi negativiindichiamo invece l’insieme {−1,−2,−3, . . .}.

1.1 Operazioni sui numeri interi

Sappiamo che su Z sono definite le due operazioni di somma e moltiplicazione che soddisfano alleseguenti proprieta:

s1) a+ b = b+ a la somma e commutativa

s2) a+ (b+ c) = (a+ b) + c la somma e associativa

s3) a+ 0 = 0 + a = a 0 e l’elemento neutro per la somma

s4) a+ (−a) = (−a) + a = 0 ogni elemento ha un inverso rispetto alla somma

p1) ab = ba il prodotto e commutativo

p2) a(bc) = (ab)c il prodotto e associativo

p3) a · 1 = 1 · a = a 1 e l’elemento neutro per il prodotto

d1) a(b+ c) = ab+ ac il prodotto e distributivo rispetto alla somma.

(1)

E importante osservare che per la somma e il prodotto non valgono le stesse proprieta. La proprietas4 dice che per ogni intero n possiamo trovare un altro intero y tale che n + y e uguale all’elementoneutro della somma (cioe 0). La stessa proprieta per il prodotto suonerebbe cosı: per ogni intero zpossiamo trovare un intero x tale che z · x e uguale all’elemento neutro del prodotto (cioe 1). Ma noisappiamo che tra gli interi l’equazione zx = 1 ha soluzione solo per z = 1 e z = −1. Quindi in Z tuttigli elementi hanno un inverso rispetto alla somma ma non tutti gli elementi hanno l’inverso rispettoal prodotto. E importante a questo punto ricordare che per i numeri razionali e i numeri reali ogninumero diverso da 0 ha l’inverso rispetto al prodotto.

Osservazione 1 Qualcuno potrebbe osservare che esiste una terza operazione fra gli interi: la sot-trazione. Per semplicita non daremo alla sottrazione la dignita di una operazione a se stante, ma laconsidereremo semplicemente l’operazione “inversa” rispetto alla somma. 2

Lavorando con i numeri interi non e possibile in generale effettuare la divisione “classica” in quanto5 diviso 2 non e un numero intero. Sui numeri interi e possibile pero introdurre il concetto di divisioneeuclidea. Dati due interi a, b con b 6= 0, eseguire la divisione euclidea fra a e b significa calcolare dueinteri q, r, detti rispettivamente quoziente e resto, tali che

a = bq + r, e 0 ≤ r < |b|. (2)

Se a e b sono entrambi positivi, il calcolo di quoziente e resto e un’operazione familiare (intuitivamentesottraiamo b da a fino a quando non si ottiene un valore minore di b). Nel caso in cui a o b o entrambisiano negativi e necessario prestare piu attenzione e ricordarsi che deve valere (2) quindi il resto deveessere sempre positivo. Si consiglia di studiare attentamente gli esempi che seguono.

2 1 I NUMERI INTERI

Esempio 1

14 diviso 3 → quoziente = 4, resto = 2

14 diviso − 3 → quoziente = −4, resto = 2

−14 diviso − 3 → quoziente = 5, resto = 1

−14 diviso 3 → quoziente = −5, resto = 1







2

Per essere rigorosi dovremmo dimostrare che il quoziente ed il resto esistono sempre e sono unici,ma per semplicita omettiamo questa dimostrazione.

Definizione 1 Dati due interi a, b con b 6= 0, si dice che b divide a se il resto della divisione fra a e be zero. In questo caso si dice anche che a e divisibile per b, e che a e un multiplo di b. 2

Osserviamo che tutti i numeri interi sono multipli di 1 e −1 perche la divisione per 1 o −1 dasempre resto 0. Inoltre, per b 6= 0 abbiamo che 0 e divisibile per b in quanto 0 = b · 0 + 0 (cioe ladivisione fra 0 e b da quoziente 0 e resto 0).

Definizione 2 Un numero intero p > 1 e detto primo se i suoi soli divisori positivi sono 1 e p. 2

Se un numero non e primo e detto composto. Sappiamo dalla scuola media che i numeri compostipossono essere fattorizzati nel prodotto di numeri primi. In questo senso i numeri primi possonoessere visti come i “mattoni” con i quali tutti gli altri numeri vengono costruiti. Richiamiamo percompletezza questo risultato (noto anche come Teorema Fondamentale dell’Aritmetica) omettendonela dimostrazione.

Teorema 1 Ogni numero intero maggiore di 1 puo essere scomposto nel prodotto di numeri primi(non necessariamente distinti). La scomposizione e unica a meno dell’ordinamento dei fattori. 2

L’enunciato di questo teorema necessita di alcune spiegazioni. La precisazione che i primi non sononecessariamente distinti e dovuta al fatto che in una scomposizione un numero primo puo apparirepiu volte. Ad esempio 180 = 2 · 2 · 3 · 3 · 5. Dire che la scomposizione e unica a meno dell’ordinamentodei fattori, vuol dire che due fattorizzazioni dello stesso numero possono differire unicamente perl’ordinamento dei primi che vi compaiono. Ad esempio abbiamo 15 = 3 · 5 e 15 = 5 · 3, ma non epossibile che un intero N si fattorizzi contemporaneamente come N = 3 · 11 e N = 5 · 7.

I numeri primi sono usati in molti ambiti dell’informatica e sono particolarmente importanti pergli algoritmi di crittografia. Data la loro importanza e confortante sapere che di numeri primi neesistono infiniti, come dimostrato dal seguente teorema.

Teorema 2 I numeri primi sono infiniti.

Dimostrazione: Supponiamo per assurdo che esista un numero finito di numeri primi e indichiamolicon p1, p2, . . . , pn. Consideriamo il numero

M = 1 + p1p2 · · · pn.

1.2 Massimo Comun Divisore e algoritmo di Euclide 3

Il numeroM non e primo in quanto secondo la nostra ipotesi i numeri primi sono solamente p1, p2, . . . , pne M e maggiore di ciascuno di essi. Ma se M non e primo, per il Teorema 1 potra essere scompostonel prodotto di numeri primi. Di conseguenza devono esistere almeno un numero primo pi che divideM . Ma questo e impossibile in quanto la divisione fra M e un qualsiasi pi da resto 1. Abbiamo quindiraggiunto un assurdo e di conseguenza deve essere sbagliata l’ipotesi iniziale che esista solamente unnumero finito di numeri primi. 2

1.2 Massimo Comun Divisore e algoritmo di Euclide

Dati a, b con b 6= 0 scriviamo a mod b per indicare il resto della divisione fra a e b (ad esempio scriviamo17 mod 3 = 2). Scriviamo inoltre b|a per indicare che b divide a (cioe che a mod b = 0), e b 6 |a perindicare che b non divide a (cioe che a mod b 6= 0).

Dati due interi a, b non entrambi nulli, il Massimo Comun Divisore fra a e b e il piu grande interopositivo che divide sia a che b. Se d e il massimo comun divisore fra a e b scriviamo d = MCD(a, b).

Esempio 2

MCD(48, 15) = 3 MCD(10, 6) = 2 MCD(15, 14) = 1 MCD(0, 24) = 24

MCD(48,−15) = 3 MCD(−48,−15) = 3 MCD(−33, 21) = 3 MCD(−15, 0) = 15.

2

Per il calcolo di MCD(a, b) si puo utilizzare il metodo che abbiamo imparato alle scuole medie:si scrivono le fattorizzazioni di a e b e si prendono tutti i fattori comuni con il minimo esponente.Sfortunatamente, quando a e b sono grandi e molto dispendioso calcolare la loro fattorizzazione e diconseguenza questa strada non e praticabile. Nella pratica quindi per il calcolo del MCD si utilizzaun metodo diverso molto piu efficiente noto come algoritmo di Euclide.

Osserviamo che possiamo assumere che a e b siano non negativi in quanto MCD(a, b) = MCD(|a|, |b|).Se b = 0 abbiamo MCD(a, b) = a e non c’e nulla da calcolare. Se b 6= 0 l’algoritmo di Euclide con-siste in una serie di divisioni e termina quando una divisione produce un resto uguale a zero. Piuprecisamente, l’algoritmo di Euclide genera la sequenza di valori:

r0 = a, r1 = b, r2 = r0 mod r1, r3 = r1 mod r2, . . . ri = ri−1 mod ri−2, . . .

e cosı via fino a quando non si trova un valore rn = 0. Il MCD fra a e b e dato da rn−1 cioe dall’ultimoresto non zero della sequenza.

Esempio 3 Per calcolare il massimo comun divisore fra 388 e 123 procediamo nel seguente modo:







L’ultimo resto non nullo e 1, che quindi e il massimo comun divisore di 391 e 123. 2

Nell’esempio appena visto diciamo che l’algoritmo di Euclide ha generato la sequenza

391, 123, 22, 13, 9, 4, 1, 0 (3)

dove i primi due termini sono gli interi dei quali vogliamo calcolare il MCD mentre gli altri terminisono i resti delle divisioni effettuate durante il procedimento.

4 1 I NUMERI INTERI

Esempio 4 Per calcolare il massimo comun divisore fra 207 e 741 procediamo nel seguente modo:










L’ultimo resto non nullo e 3, che quindi e il massimo comun divisore di 207 e 741. La sequenza generatadall’algoritmo di Euclide e

207, 741, 207, 120, 87, 33, 21, 12, 9, 3, 0.

2

Data l’importanza dell’algoritmo di Euclide dimostriamo ora la sua correttezza, cioe che essorestituisce effettivamente MCD(a, b). Per semplicita spezziamo la dimostrazione in due parti: unprimo lemma che giustifica l’utilizzo della divisione euclidea, ed un teorema principale che mostra lacorrettezza dell’algoritmo.

Lemma 1 Dati due interi a, b con b 6= 0 sia r = a mod b. Abbiamo

MCD(a, b) = MCD(b, r).

Dimostrazione: Per dimostrare il Lemma, dimostreremo che ogni intero che divide sia a che b divideanche sia b che r, e viceversa, ogni intero che divide sia b che r divide anche sia a che b. Di conseguenzai divisori comuni di a e b coincidono con i divisori comuni di b e r. Avremo allora che anche il massimodei divisori comuni dovra essere uguale nei due casi e quindi MCD(a, b) = MCD(b, r).

Sia q il quoziente della divisione tra a e b. Abbiamo quindi a = bq + r. Sia ora c un intero chedivide sia a che b. Possiamo allora scrivere a = αc e b = βc. Abbiamo che

r = a− bq = αc− βcq = c(α− βq)

e di conseguenza r e un multiplo di c che quindi divide sia b che r.Analogamente, se d divide sia b che r abbiamo b = dγ e r = dρ da cui

a = bq + r = dγq + dρ = d(γq + ρ)

e quindi d divide sia a che b. 2

Teorema 3 L’algoritmo di Euclide calcola correttamente il Massimo Comun Divisore.

Dimostrazione: Per prima cosa dimostriamo che l’algoritmo di Euclide fornisce sempre un risultato,cioe che termina dopo un numero finito di passi. Osserviamo che essendo r2 il resto della divisionetra a e b abbiamo che 0 ≤ r2 < b (b e positivo per ipotesi). Analogamente, essendo r3 il resto delladivisione tra b e r2 abbiamo 0 ≤ r3 < r2. In generale abbiamo

b = r1 > r2 > r3 > · · · > rn−1 > rn = 0.

In altre parole, i resti generati dall’algoritmo di Euclide diminuiscono ad ogni passo. Dato che lasequenza parte con il valore b e termina non appena viene raggiunto lo zero abbiamo che l’algoritmo

1.3 L’algoritmo di Euclide esteso 5

di Euclide termina in al piu b passi (vedremo in seguito che il numero di passi realmente effettuato emolto minore).

Mostriamo ora che il valore restituito dall’algoritmo di Euclide e effettivamente il Massimo ComunDivisore tra a e b. Osserviamo che per il Lemma 1 abbiamo

MCD(a, b) = MCD(b, r2) = MCD(r2, r3) = · · ·MCD(rn−1, rn). (4)

Dato che rn = 0, MCD(rn−1, rn) = rn−1. Quindi abbiamo che MCD(a, b) e uguale a rn−1 (l’ultimoresto diverso da zero) che e il valore restituito dall’algoritmo di Euclide. 2

1.3 L’algoritmo di Euclide esteso

Abbiamo visto nella sezione precedente, che dati due interi a, b non entrambi nulli, l’algoritmo diEuclide permette di calcolare il loro massimo comun divisore. L’algoritmo di Euclide consiste in unaserie di divisioni e genera una sequenza di resti. Il procedimento termina quando si incontra un restouguale a 0 e l’ultimo resto non nullo e il massimo comun divisore fra a e b.

Esempio 5 Per calcolare il massimo comun divisore fra 1876 e 365 l’algoritmo di Euclide procede nelseguente modo:







Abbiamo quindi che l’algoritmo di Euclide genera la sequenza

1876, 365, 51, 8, 3, 2, 1, 0. (5)

L’ultimo elemento non nullo della sequenza e 1, che quindi e il massimo comun divisore. 2

L’algoritmo di Euclide esteso permette di calcolare, oltre a d = MCD(a, b), anche due interi s, ttali che as + bt = d. Nell’Esempio 5, dato che MCD(1876, 365) = 1, l’algoritmo di Euclide esteso cifornisce due interi s, t tali che 1876s+ 365t = 1. Diciamo che esprimiamo il MCD come combinazionelineare di a e b.

Il procedimento seguito dall’algoritmo di Euclide esteso e quello di esprimere ogni termine dellasequenza dei resti come combinazione lineare di a e b. Riprendendo l’Esempio 5 esprimiamo ognielemento della sequenza (5) come combinazione lineare di 1876 e 365. Per quanto riguarda i primi duetermini della sequenza non ci sono difficolta e scriviamo

1876 = 1876 · 1 + 365 · 0

365 = 1876 · 0 + 365 · 1(6)

Per il terzo termine della sequenza, 51, ricordiamo che esso e il resto della divisione tra 1876 e 365,divisione che ha come quoziente 5. Quindi vale:

51 = 1876− 365 · 5

Se al posto di 1876 e 365 scriviamo le combinazioni lineari (6) otteniamo:

51 = (1876 · 1 + 365 · 0)− 5(1876 · 0 + 365 · 1)

e svolgendo i conti:51 = 1876 · 1 + 365 · −5. (7)

6 1 I NUMERI INTERI

Per gli altri termini della sequenza si procede analogamente: abbiamo 8 = 365− 51 · 7, quindi usandola seconda di (6) e (7) abbiamo

8 = (1876 · 0 + 365 · 1)− 7(1876 · 1 + 365 · −5)

da cui8 = 1876 · −7 + 365 · 36. (8)

Per il successivo termine della sequenza abbiamo 3 = 51− 6 · 8, quindi, usando (7) e (8)

3 = (1876 · 1 + 365 · −5)− 6(1876 · −7 + 365 · 36)

da cui3 = 1876 · 43 + 365 · −221, (9)

e infine:2 = 8− 3 · 2 = 1876 · −93 + 365 · 478

1 = 3− 2 · 1 = 1876 · 136 + 365 · −699.

Abbiamo quindi trovato che 1876s+ 365t = 1 per s = 136 e t = −699.

Esempio 6 Applichiamo l’algoritmo di Euclide esteso per trovare il d = MCD(867, 120) e per trovaredue interi s, t tali che 867s+ 120t = d. Otteniamo la sequenza

867 = 867 · 1 + 120 · 0

120 = 867 · 0 + 120 · 1 867 diviso 120 → quoziente 7, resto 27

27 = 867 · 1 + 120 · −7 120 diviso 27 → quoziente 4, resto 12

12 = 867 · −4 + 120 · 29 27 diviso 12 → quoziente 2, resto 3


Abbiamo quindi che MCD(867, 120) = 3 e che 867 · 9 + 120 · −65 = 3. Osserviamo che la terzariga e stata ottenuta sottraendo 7 volte la seconda riga dalla prima (7 e il quoziente fra 867 e 120).Analogamente, la quarta riga e stata ottenuta sottraendo 4 volte la terza riga dalla seconda (4 e ilquoziente della divisione fra 120 e 27), e cosiı via fino a quando non e stato ottenuto un resto ugualea zero. 2

L’algoritmo di Euclide esteso si applica quando a e b sono entrambi non negativi. Per calcolarei coefficienti s, t nel caso in cui a, b o entrambi siano negativi, il metodo piu semplice consistenell’applicare l’algoritmo di Euclide esteso a |a| e |b| e nel cambiare successivamente il segno dei valoris e t trovati. Questo procedimento e descritto nel seguente esempio.

Esempio 7 Vogliamo calcolare d = MCD(519,−123) e trovare due interi s, t tali che 519s−123t = d.Cominciamo applicando l’algoritmo di Euclide esteso alla coppia 519, 123.

519 = 519 · 1 + 123 · 0

123 = 519 · 0 + 123 · 1 519 diviso 123 → quoziente 4, resto 27





Abbiamo quindi che 3 = MCD(519, 123) = MCD(519,−123). Inoltre

3 = 519 · −9 + 123 · 38 = 519 · −9 + (−123) · −38,

di conseguenza i valori cercati sono s = −9 e t = −38. 2

1.4 Il minimo comune multiplo 7

1.4 Il minimo comune multiplo

Dati due interi a, b non nulli, il minimo comune multiplo fra a e b e il piu piccolo intero positivo che emultiplo sia di a che di b. Se m e il minimo comune multiplo di a e b scriviamo m = mcm(a, b).

Esempio 8

mcm(48, 15) = 240 mcm(10, 6) = 30 mcm(15, 14) = 210

mcm(48,−15) = 240 mcm(−48,−15) = 240 mcm(−33, 21) = 231.

2

Anche per il calcolo di mcm(a, b) si puo utilizzare il metodo che abbiamo imparato alle scuolemedie: si scrivono le fattorizzazioni di a e b e si prendono i fattori comuni e non comuni con ilmassimo esponente. Sfortunatamente, come abbiamo gia osservato parlando del MCD, quando a e bsono grandi e molto dispendioso calcolare la loro fattorizzazione e di conseguenza questa strada none praticabile. Per il calcolo del mcm utilizzeremo invece la seguente formula (che per semplicita nondimostriamo):

mcm(a, b) =|ab|

MCD(a, b). (10)

Ad esempio abbiamo:

mcm(273, 399) =273 · 399

MCD(273, 399)=

273 · 39921

= 5187.

1.5 L’equazione diofantea ax + by = c

In questa sezione studieremo il seguente problema: dati tre interi qualsiasi a, b, c vogliamo trovare perquali coppie di numeri interi x, y vale la relazione ax+ by = c. Le equazioni di questo tipo sono detteequazioni diofantee.

Esempio 9 Un esempio di equazione diofantea e il seguente: trovare una coppia di interi x, y tali che867x+ 120y = −15. A prima vista questo problema puo sembrare molto difficile; tutte le tecniche chesono state studiate alle superiori non si possono applicare a causa della richiesta che le soluzioni x, ysiano intere. Possiamo pero osservare che l’Esempio 6 ci fornisce la coppia di numeri (9,−65) tali che867 · 9 + 120 · −65 = 3. Moltiplicando entrambi i membri di questa uguaglianza per −5 otteniamo larelazione

867 · (9 · −5) + 120 · (−65 · −5) = 3 · −5

da cui867 · −45 + 120 · 325 = −15.

Abbiamo quindi che l’equazione 867x+ 120y = −15 ammette la soluzione x = −45, y = 325. 2

Nel’esempio precedente abbiamo ottenuto la soluzione dell’equazione diofantea utilizzando i valorirestituiti dall’algoritmo di Euclide esteso. Il seguente lemma ci mostra che questa strada si puoapplicare in molte situazioni.

Lemma 2 Data l’equazione diofantea ax + by = c, se a e b non sono entrambi nulli e MCD(a, b)divide c allora possiamo trovare una soluzione dell’equazione utilizzando l’algoritmo di Euclide esteso.

Dimostrazione: Sia d = MCD(a, b), e siano s, t i valori restituiti dall’algoritmo di Euclide esteso taliche as+ bt = d. Dato che per ipotesi d|c abbiamo che c/d e un numero intero. Abbiamo allora

as+ bt = d ⇐⇒ a(sc/d) + b(tc/d) = c.

Possiamo concludere quindi che x = sc/d e y = tc/d sono due numeri interi e costituiscono unasoluzione dell’equazione diofantea. 2

8 1 I NUMERI INTERI

Esempio 10 Cosa succede se uno o entrambi gli interi a o b sono negativi? Il procedimento noncambia: e sufficiente stare attenti ai segni. Ad esempio, per risolvere l’equazione diofantea −116x +88y = 100 applichiamo l’algoritmo di Euclide esteso ai valori 116, 88 ottenendo che il loro MCD e 4 eche 116 · −3 + 88 · 4 = 4. Abbiamo quindi che

−116 · 3 + 88 · 4 = 4

Moltiplicano entrambi i termini per 25 = 100/4 otteniamo

−116 · 75 + 88 · 100 = 100

e possiamo concludere che una soluzione del problema proposto e x = 75, y = 100. 2

Osservazione 2 I risultati precedenti ci mostrano che quando d = MCD(a, b) divide c, siamo ingrado di trovare una soluzione dell’equazione diofantea ax + by = c. E immediato pero osservareche partendo da una soluzione particolare x0, y0 possiamo calcolare una famiglia infinita di soluzioni.Ponendo infatti α = a/d, β = b/d abbiamo che se x0, y0 e una soluzione dell’equazione diofantea lo eanche la coppia

x0 + kβ, y0 − kα (11)

per ogni intero k. Abbiamo infatti

a(x0 + βk

)+ b(y0 − αk

)= ax0 + (ab/d)k + by0 − (ab/d)k = ax0 + by0 = c.

2

Esempio 11 Dall’Esempio 6 sappiamo che MCD(867, 120) = 3 e che x = −45, y = 325 e unasoluzione dell’equazione diofantea 867x + 120y = −15. Dato che 867/3 = 289 e 120/3 = 40, perl’osservazione precedente abbiamo che anche le coppie x = −45 + 40k, y = 325− 289k sono soluzionedell’equazione per qualsiasi valore di k. Ad esempio per k = 1, 2, 3,−2 otteniamo rispettivamente lesoluzioni

x = −5, y = 36; x = 35, y = −253; x = 75, y = −542; x = −125, y = 903.

2

Abbiamo quindi che l’equazione (11) ci fornisce una famiglia infinita di soluzioni dell’equazionediofantea ax + by = c data una qualsiasi soluzione x0, y0. E naturale chiedersi se ci possono esserealtre soluzioni al difuori di questa famiglia. Mostriamo ora che questo non e possibile. Sia x1, y1

un’altra soluzione dell’equazione diofantea. Deve essere:

ax1 + by1 = ax0 + by0

(in quanto entrambi i termini sono uguali a c). Otteniamo allora:

a(x1 − x0) = b(y0 − y1)

dividendo per d = MCD(a, b) e ricordando che α = a/d, β = b/d otteniamo

α(x1 − x0) = β(y0 − y1). (12)

Abbiamo quindi che β(y1 − y0) e un multiplo di α. Ma e facile verificare che α e β non hanno fattoriin comune, e di conseguenza tutti i fattori di α devono essere contenuti in (y0 − y1) che quindi saradella forma αt per un qualche intero t. Sostituendo questa relazione nella (12) otteniamo

α(x1 − x0) = βαt

da cui x1 − x0 = βt. Concludendo abbiamo che

x1 = x0 + βt, y1 = y0 − αt

1.6 Esercizi su MCD ed equazioni diofantee 9

e quindi anche x1, y1 appartiene alla famiglia (11).Possiamo concludere che quando d = MCD(a, b) divide c, siamo in grado di descrivere tutte le

infinite soluzioni dell’equazione ax + by = c. Cosa succede quando d non divide c? Il procedimentoche abbiamo visto non puo essere applicato, potrebbe pero esistere un diverso metodo di risoluzione.Il seguente lemma ci mostra che le cose non stanno cosı: in quanto se d 6 |c allora l’equazione diofanteanon ha soluzioni.

Lemma 3 Se d = MCD(a, b) non divide c, l’equazione diofantea ax+ by = c non ha soluzioni.

Dimostrazione: Supponiamo per assurdo che la coppia x0, y0 sia una soluzione dell’equazione dio-fantea, cioe che ax0 + by0 = c. Dato che d = MCD(a, b) esistono due interi α, β tali che a = dα eb = dβ. Ne segue che

c = ax0 + by0 = dαx0 + dβy0 = d(αx0 + βy0)

e quindi dovremmo avere che d divide c. 2

Possiamo riassumere i risultati di questa sezione nel seguente importante teorema.

Teorema 4 Data l’equazione diofantea ax+by = c con a e b non entrambi nulli, l’equazione ammettesoluzioni se e solo se d = MCD(a, b) divide c. Se le soluzioni esistono possiamo trovare una soluzioneparticolare mediante l’algoritmo di Euclide esteso, e tutte le altre soluzioni mediante la formula (11)dell’Osservazione 2. 2

Infine dobbiamo chiederci cosa succede quando a e b sono entrambi nulli. In questo caso nonpossiamo neanche calcolare il loro MCD e di conseguenza il precedente teorema non puo essere appli-cato. Per fortuna e immediato verificare che se a e b sono entrambi nulli, l’equazione diofantea non hasoluzioni se c e diverso da zero, mentre quando c e anch’esso uguale a zero ogni coppia di interi x0, y0

e soluzione dell’equazione.

1.6 Esercizi su MCD ed equazioni diofantee

La maggior parte degli esercizi che seguono si risolvono applicando quanto visto nella precedentesezione e in particolare il Teorema 4.

Esercizio 1 Determinare per quali punti di coordinata intere passa la retta di equazione

2x3

+ 3y = −1.

Soluzione. Ricordiamo che la retta passa per un punto se e solo se le coordinate del punto soddisfanol’equazione della retta. Quindi affinche il punto (x0, y0) stia sulla retta data e necessario che sia2x03 + 3y0 = −1. In altre parole vogliamo trovare le soluzioni (x, y) intere dell’equazione 2x

3 + 3y = −3.Come prima cosa rendiamo interi tutti i coefficienti moltiplicando l’equazione per 3 e ottenendo

l’equazione equivalente2x+ 9y = −3. (13)

Vogliamo quindi trovare tutte le soluzioni intere di questa equazione. Per il Teorema 4 esistonodelle soluzioni intere se e soltanto se MCD(2, 9) divide −3, condizione che e verificata in quantoMCD(2, 9) = 1.

Per trovare tutte le soluzioni intere (cioe tutti i punti a coordinate intere per cui passa la retta)procediamo nel seguente modo. Per prima cosa dobbiamo determinare due interi s, t tali che 2s+9t = 1.In questo caso si vede che una soluzione e s = −4, t = 1; se la soluzione non si vede ad occhiopossiamo determinarla usando la versione estesa dell’algoritmo di Euclide. Moltiplicando la relazione2(−4) + 9(1) = 1 per −3 otteniamo 2(12) + 9(−3) = −3 e quindi un primo punto che appartiene allaretta e (12,−3). Per trovare tutt le soluzioni dell’equazione (13) ricordiamo che data una soluzionex0, y0 tutte le altre soluzioni hanno la forma (x0 + 9λ, y0 − 2λ) con λ ∈ Z (vedere l’Osservazione 2).Nel nostro caso quindi le soluzioni hanno la forma: (12 + 9λ,−3− 2λ) con λ ∈ Z. 2

10 1 I NUMERI INTERI

Esercizio 2 Determinare per quali punti di coordinata intera passa la retta di equazione

3x2− y

6=

14.

Soluzione. Come per l’Esercizio 1 il primo passo consiste nel trasformare l’equazione data in un’equa-zione equivalente a coefficienti interi. Moltiplicando per 12 si ottiene l’equazione 18x − 2y = 3 dellaquale vogliamo trovare tutte le soluzioni intere. Il Teorema 4 ci dice che esistono soluzioni intere see solo se MCD(18,−2) divide 3. Tale condizione non e verificata in quanto MCD(18,−2) = 2. Diconseguenza non esistono punti di coordinate intere attraversati dalla retta data. 2

Esercizio 3 Dire per quali valori di t l’equazione 100x+ 120y = t ha soluzione.

Soluzione. Per il Teorema 4 l’equazione ha soluzione se e soltanto se MCD(100, 120) divide t. Dato cheMCD(100, 120) = 20 l’equazione ha soluzione quando t e un multiplo di 20, cioe ha la forma t = 20λcon λ ∈ Z. 2

Esercizio 4 Dire per quali valori di a l’equazione 999x− 99y = a+ 5 ha soluzione.

Soluzione. Per il Teorema 4 l’equazione ha soluzione se e soltanto se MCD(999,−99) divide a+ 5. Percalcolare MCD(999,−99) osserviamo che esso e uguale a MCD(999, 99) e utilizziamo l’algoritmo diEuclide che genera la sequenza:



Abbiamo quindi MCD(999,−99) = 9 e l’equazione ha soluzione quando a+ 5 e un multiplo di 9 cioequando a e della forma a = 9λ− 5 con λ ∈ Z. Quindi abbiamo a = {. . . ,−14,−5, 4, 13, . . .}. 2

Esercizio 5 Dire per quali valori di a l’equazione 3ax+ 2y = 1 ha soluzione.

Soluzione. Per il Teorema 4 l’equazione ha soluzione se e soltanto se MCD(3a, 2) = 1. Dato che 2 e3 non hanno fattori comuni, affinche MCD(3a, 2) = 1 basta che a non contenga il fattore 2. In altreparole l’equazione ha soluzione se a e dispari, mentre se a e pari l’equazione non ha soluzione. 2

Esercizio 6 Dire se la retta di equazione

7x6

+ 2y =23

passa per un punto le cui coordinate siano entrambe intere e pari.

Soluzione. Come al solito trasformiamo il problema iniziale in un’equazione diofantea. Moltiplicandoper 6 otteniamo l’equazione

7x+ 12y = 4 (14)

della quale vogliamo trovare le soluzioni x, y intere e pari. Usiamo il solito procedimento per de-terminare tutte le soluzioni, e poi verificheremo se ce ne sono con x, y entrambi pari. AbbiamoMCD(7, 12) = 1, e utilizzando eventualmente l’algoritmo di Euclide esteso, troviamo due interi s, ttali che 7s + 12t = 1. Ad esempio abbiamo 7(−5) + 12(3) = 1. Una soluzione particolare dell’equa-zione (14) e quindi x0 = −20, y0 = 12. Per l’Osservazione 2 abbiamo che le soluzioni di (14) sonodate da x = −20 + 12λ, y = 12 − 7λ con λ ∈ Z. E immediato vedere che le soluzione con coordi-nate entrambe pari sono quelle che si ottengono con λ pari, ad esempio: x = −20, y = 12 (λ = 0),x = 4, y = −2 (λ = 2), x = 28, y = −16 (λ = 4), etc. 2

11

2 Congruenze

In questo capitolo si introducono i concetti di modulo, congruenza e classe di resto. Si tratta diconcetti semplici che costituiscono la base dei risultati che saranno illustrati nei capitoli successivi.Ricordiamo che dati due interi a, b con b 6= 0 scriviamo a mod b (si legge a modulo b) per indicareil resto della divisione fra a e b. Ad esempio abbiamo: 17 mod 6 = 5, 24 mod 4 = 0, 15 mod 4 = 3,−15 mod 4 = 1. Introduciamo ora un’altra definizione collegata al concetto di modulo.

Definizione 3 Fissato un intero positivo n > 0, diciamo che a e congruo a b modulo n, e scriviamoa ≡n b [oppure a ≡ b (mod n)], se a− b e un multiplo di n. 2

Ad esempio abbiamo 12 ≡5 2 in quanto 12 − 2 = 10 e un multiplo di 5. Abbiamo −1 ≡3 8 inquanto −1 − 8 = −9 che e multiplo di 3. Se a = b non e un multiplo di n scriviamo a 6≡n b oppurea 6≡ b (mod n). Ad esempio 17 6≡4 3 e −2 6≡5 12.

Notiamo che in entrambe le scritture 17 mod 3 = 2 e 21 ≡ 6 (mod 5) il termine modulo si riferiscealla quantita per cui si divide (3 nel primo esempio, 5 nel secondo). In matematica e informatica capitaspesso si usa l’espressione “lavoriamo modulo n” per indicare che ogni operazione e fatta “modulo n”cioe considerando di ogni quatita, non il valore esatto, ma solamente il resto della divisione per n. Adesempio, se “lavoriamo modulo 10” vuol dire che di ogni grandezza intera consideriamo solamente ilresto della divisione per 10 (in pratica quindi consideriamo solo la cifra delle unita). Data l’importanzadi questo concetto, nella prossima sezione introduciamo formalmente gli insiemi nei quali tutte leoperazioni vengono effettuate modulo un fissato intero positivo n.

2.1 Gli insiemi Zn

Introduciamo gli insiemi Zn considerando inizialmente il caso particolare n = 5. Osserviamo che Zpuo essere suddiviso in 5 sottoinsiemi [0]5, [1]5, [2]5, [3]5, [4]5 cosı definiti:

1. [0]5 contiene gli interi k tali che k ≡5 0; quindi [0]5 = {. . . ,−5, 0, 5, 10, . . .};





Osserviamo che questi sottoinsiemi sono disgiunti e che ogni intero appartiene ad uno di questisottoinsiemi. In termini matematici si dice che questi sottoinsiemi formano una partizione di Z.Osserviamo anche che ogni intero t appartiene al sottoinsieme [r]5 dove r e il resto della divisione fra te 5 (cioe r = t mod 5). Ad esempio per sapere in quale sottoinsieme appartiene −99999 osserviamo che−99999 mod 5 = 1 quindi −99999 ∈ [1]5. Analogamente 1234567 ∈ [2]5, 100 ∈ [0]5 e cosı via. A causadi questa proprieta questi cinque sottoinsiemi sono chiamati classi di resto modulo 5. Indichiamo nelseguito con Z5 l’insieme delle classi di resto Z5 = {[0]5, [1]5, [2]5, [3]5, [4]5}. L’insieme Z5 ha quindiesattamente 5 elementi

Il motivo fondamentale per cui introduciamo le classi di resto e che date due classi di resto siamoin grado di sommarle e moltiplicarle in maniera simile a quanto facciamo per i numeri interi, razionali,reali, etc. Le regole fondamentali per eseguire la somma e le moltiplicazioni in Z5 sono le seguenti:

[a]5 + [b]5 = [(a+ b) mod 5]5, e [a]5 · [b]5 = [ab mod 5]5. (15)

Informalmente queste regole si possono riassumere nel seguente modo: eseguiamo la somma e ilprodotto tradizionale e poi prendiamo il resto della divisione per 5. Ad esempio abbiamo:

[2]5 + [1]5 = [3]5, [3]5 + [4]5 = [2]5, [4]5 + [1]5 = [0]5, [0]5 + [2]5 = [2]5,

[2]5[1]5 = [2]5, [3]5[3]5 = [4]5, [4]5[2]5 = [3]5, [0]5[2]5 = [0]5.

12 2 CONGRUENZE

Tutto cio che abbiamo appena visto nel caso n = 5, puo essere ripetuto per un qualsiasi n > 0.Fissato n possiamo definire le classi di resto [0]n, [1]n, . . . , [n − 1]n. La classe [i]n contiene tutti gliinteri k tali che k ≡n i cioe i numeri della forma i + λn con λ ∈ Z. Equivalentemente possiamo direche [i]n contiene tutti gli interi che divisi per n danno resto i. Ad esempio abbiamo:

[3]13 = {. . . ,−10, 3, 16, 29, . . .}.

Indichiamo con Zn l’insiemeZn = {[0]n, [1]n, . . . , [n− 1]n},

che quindi ha esattamente n elementi. Dati due elementi di Zn li possiamo sommare e moltiplicarecon le stesse regole viste nel caso n = 5:

[a]n + [b]n = [(a+ b) mod n]n, e [a]n · [b]n = [ab mod n]n. (16)

Ad esempio abbiamo:

[3]9 + [4]9 = [7]9, [3]7 + [4]7 = [0]7, [10]13 + [9]13 = [6]13, [1]2 + [1]2 = [0]2,

[3]6[2]6 = [0]6, [6]9[5]9 = [3]9, [9]11[8]11 = [1]11, [6]12[6]12 = [0]12.

E immediato verificare che le operazioni di somma e prodotto in Zn soddisfano alle stesse proprietache abbiamo visto per gli interi (vedi Sezione 1):

s1) [a]n + [b]n = [b]n + [a]n la somma e commutativa

s2) [a]n + ([b]n + [c]n) = ([a]n + [b]n) + [c]n la somma e associativa

s3) [a]n + [0]n = [0]n + [a]n = [a]n [0]n e l’elemento neutro per la somma

s4) [a]n + [n− a]n = [n− a]n + [a]n = [0]n ogni elemento ha un inverso rispetto alla somma

p1) [a]n[b]n = [b]n[a]n il prodotto e commutativo

p2) [a]n([b]n[c]n) = ([a]n[b]n)[c]n il prodotto e associativo

p3) [a]n · [1]n = [1]n · [a]n = [a]n [1]n e l’elemento neutro per il prodotto

d1) [a]n([b]n + [c]n) = [a]n[b]n + [a]n[c]n il prodotto e distributivo rispetto alla somma.

(17)

L’unica proprieta non banale e la s4 che dice che ogni elemento di Zn ha un inverso rispetto allasomma: in particolare, l’inverso dell’elemento [a]n e [n − a]n. Ad esempio, in Z13 l’inverso di [5]13 e[13−5]13 = [8]13, come possiamo verificare osservando che [5]13 + [8]13 = [0]13. L’esistenza dell’inversorispetto alla moltiplicazione sara l’argomento della prossima sezione.

Osservazione 3 Su Zn e possibile definire l’operazione di sottrazione secondo la regola [a]n−[b]n = [a−b mod n]n. Ad esempio: [4]13 − [8]13 = [−4 mod 13] = [9]13. Per semplicita nel seguito trasformeremospesso le sottrazioni in somme usando la formula [a]n − [b]n = [a]n + [n− b]n. 2

2.2 L’equazione [a]n · [x]n = [1]n

In questa sezione vogliamo stabilire quali sono gli elementi di Zn che hanno un inverso rispetto alprodotto. In altre parole, vogliamo sapere per quali elementi [a]n ∈ Zn esiste una classe di resto [b]ntale che [a]n · [b]n = [1]n. In altre parole ancora, vogliamo determinare per quali [a]n l’equazione

[a]n · [x]n = [1]n (18)

ammette soluzioni. Prima di procedere ricordiamo quello che gia sappiamo sugli altri insiemi numerici:in Z l’equazione ax = 1 ha soluzione solo per a = 1 e a = −1. In Q e in R, l’equazione ax = 1 ha

2.2 L’equazione [a]n · [x]n = [1]n 13

soluzione per ogni a 6= 0. Sorprendentemente, vedremo che la situazione in Zn e piu simile a quella diQ e R che non a quella di Z.

Osserviamo che l’equazione [a]n[x]n = [1]n equivale a [ax]n = [1]n. Ci chiediamo quindi per qualia esiste x tale che ax mod n = 1, cioe il resto della divisione tra ax e n e esattamente uguale a 1. Seindichiamo con q il quoziente della divisione, si vuole che

ax = nq + 1.

In altre parole, l’equazione (18) ha soluzione se e solo se esistono due interi x e q tali che

ax− nq = 1 (19)

Quest’ultima equazione e una nostra vecchia conoscenza e noi sappiamo che ammette soluzione se esolo se MCD(a,−n) = MCD(a, n) = 1. Inoltre se MCD(a, n) = 1 sappiamo che mediante l’algoritmodi Euclide esteso possiamo trovare x e q che soddisfano la (19). Il valore x mod n ci fornisce la classedi resto soluzione dell’equazione (18).

Esempio 12 Vogliamo risolvere l’equazione [5]22[x]22 = [1]22. Per quanto detto sopra deve essere5x mod 22 = 1. Abbiamo quindi l’equazione diofantea:

5x− 22t = 1

che e risolubile in quanto MCD(5, 22) = 1. Per tentativi, o utilizzando l’algoritmo di Euclide esteso,troviamo che una soluzione e x = −13, t = −3. La soluzione dell’equazione di partenza e quindi[−13 mod 22]22 = [9]22. Osserviamo che la soluzione e corretta in quanto [5]22[9]22 = [1]22. 2

Il risultato che abbiamo appena visto e sufficientemente importante da enunciarlo in un teorema.

Teorema 5 L’equazione [a]n · [x]n = [1]n ha soluzione se e solo se MCD(a, n) = 1. Se la soluzioneesiste possiamo trovarla mediante l’algoritmo di Euclide esteso. 2

Dato che [a]n ha un inverso moltiplicativo se e solo se l’equazione [a]n · [x]n = [1]n ha soluzione,usando il Teorema 5 siamo in grado di dare una risposta al problema di stabilire quali classi di restodi Zn hanno un inverso moltiplicativo.

Corollario 1 La classe di resto [a]n ∈ Zn ha un inverso moltiplicativo se e solo se MCD(a, n) = 1.Se l’inverso esiste lo possiamo trovare mediante l’algoritmo di Euclide esteso. 2

Esempio 13 Per trovare l’inverso moltiplicativo della classe [10]23, dobbiamo trovare x tale che10x mod 23 = 1. Quindi dobbiamo risolvere l’equazione 10x − 23t = 1. Una soluzione e data dax = 7, t = 3 per cui l’inversa della classe [10]23 e la classe [7]23. 2

Osservazione 4 In analogia con i numeri razionali e reali, quando esiste l’inverso moltiplicativodell’elemento [a]n si indica con [a]−1

n . Nell’esempio precedente abbiamo quindi [10]−123 = [7]23. Notiamo

che, per definizione, per ogni elemento [a]n invertibile vale la relazione [a]n · [a]−1n = [1]n. 2

Consideriamo ora il caso particolare in cui il modulo (cioe n) sia un numero primo. In questo casoabbiamo che per i = 1, . . . , n − 1 MCD(i, n) = 1 (n e primo quindi non ha divisori piu piccoli di luidiversi da 1). Di conseguenza, tutte le classi di resto, esclusa [0]n sono invertibili. Siamo quindi nellastessa situazione dei numeri razionali e dei numeri reali in cui tutti gli elementi diversi da zero hannoinverso moltiplicativo!

14 2 CONGRUENZE

2.3 Esercizi sulle congruenze

Esercizio 7 Risolvere in Z48 l’equazione [11]48[x]48 = [6]48.

Soluzione. Possiamo risolvere l’esercizio in due modi. Il primo consiste nel trovare l’inverso moltiplicati-vo di [11]48, cioe trovare [y]48 tale che [11]48[y]48 = [1]48 ([y]48 esiste in quanto MCD(11, 48) = 1). Pas-sando dall’equazione diofantea 11x−48q = 1 otteniamo [y]48 = [35]48. A questo punto moltiplichiamoentrambi i termini dell’equazione di partenza per [35]48 ottenendo

[35]48[11]48[x]48 = [35]48[6]48

da cui[1]48[x]48 = [18]48

e la soluzione e quindi [x]48 = [18]48.Il secondo metodo di risoluzione consiste nell’osservare che x deve essere tale che il resto della

divisione fra 11x e 48 sia 6. Quindi dobbiamo avere:

11x = 48q + 6.

Con calcoli analoghi al caso precedente si ottiene ancora [x]48 = [18]48. 2


Soluzione. Osserviamo che l’esercizio e simile all’Esercizio 7 per il quale avevamo visto due possibilemetodi di risoluzione. In questo caso pero, MCD(15, 36) 6= 1, quindi [15]36 non ha l’inverso moltipli-cativo in Z36. Di conseguenza, il primo metodo di risoluzione usato nell’Esercizio 7 non e applicabile.Utilizziamo allora il secondo metodo che consiste nel risolvere l’equazione diofantea:

15x− 36q = 6.

Dato che MCD(15, 36) divide 6, l’equazione e risolubile. Si vede immediatamente che una soluzionee x = −2, q = −1. L’insieme di tutte le soluzione e dato allora da x = −2 + 12λ e q = −1 + 5λcon λ ∈ Z. Osserviamo che al variare di λ i valori assunti da x sono {. . . ,−2, 10, 22, 34, 46, . . .}. Diconseguenza, le classi di resto soluzione dell’equazione [15]36[x]36 = [6]36 sono [x]36 = [10]36, [x]36 =[22]36, [x]36 = [34]36 (provare per credere!). 2


Soluzione. Procedendo come nell’esercizio precedente abbiamo che x deve essere una soluzione dell’e-quazione diofantea

12x− 36q = 6.

In questo caso pero MCD(12, 36) non divide 6, quindi l’equazione diofantea e la nostra equazione dipartenza non hanno soluzioni. 2

Osservazione 5 Combinando quanto abbiamo visto negli Esercizi 7, 8, e 9 possiamo concludere chel’equazione di primo grado [a]n[x]n = [b]n in Zn ha una e una sola soluzione quando MCD(a, n) = 1.Se MCD(a, n) > 1 e MCD(a, n) non divide b l’equazione non ha soluzioni, se infine MCD(a, n) >1 e MCD(a, n) divide b allora l’equazione ha piu di una soluzione. E possibile dimostrare che inquest’ultimo caso il numero di soluzioni coincide esattamente con MCD(a, n). 2

Esercizio 10 Risolvere in Z13 l’equazione [3]13[x]13 + [5]13 = [6]13 + [9]13[x]13.

Soluzione. Si procede come nelle equazioni di primo grado sui reali portando a sinistra dell’uguale itermini con la [x]13 e a destra gli altri termini. Otteniamo quindi

[3]13[x]13 − [9]13[x]13 = [6]13 − [5]13,

da cui (essendo [3]13 − [9]13 = [3]13 + [4]13)

[7]13[x]13 = [1]13.

Risolvendo l’equazione diofantea 7x − 13q = 1 (o calcolando l’inverso moltiplicativo di [7]13, [7]−113 =

[2]13) otteniamo [x]13 = [2]13. 2

2.3 Esercizi sulle congruenze 15

Esercizio 11 Risolvere l’equazione [13]80[x]80 + [20]80 = [68]80 − [13]80[x]80.

Soluzione. Riordinando i termini si ottiene l’equazione equivalente:

[26]80[x]80 = [48]80

Dato che MCD(26, 80) = 2 divide 48 l’equazione ha due soluzioni (vedi Osservazione 5). Risolvendol’equazione diofantea 26x− 80q = 48 si trovano le soluzioni [x]80 = [8]80 e [x]80 = [48]80. 2

Esercizio 12 Dire per quali valori di [a]12 l’equazione [a]12[x]12 = [1]12 + [9]12[x]12 ha soluzione.

Soluzione. Portiamo [9]12[x]12 a sinistra dell’uguale ottenendo

([a]12 − [9]12)[x]12 = [1]12

da cui[a+ 3]12[x]12 = [1]12.

I valori ammessi di [a]12 sono quindi quelli per cui [a + 3]12 ha l’inverso moltiplicativo. Dato che glielementi di Z12 con inverso moltiplicativo sono [1]12, [5]12, [7]12, [11]12 i valori ammessi di [a]12 sono[10]12, [2]12, [4]12, [8]12. 2

16 3 APPLICAZIONI DELLE CONGRUENZE

3 Applicazioni delle congruenze

Nella sezione precedente abbiamo introdotto il concetto di congruenza; in questa sezione vediamoalcune applicazioni. Per molte di queste applicazioni la proprieta fondamentale da ricordare e laseguente: se abbiamo un’espressione contenente solo somme e prodotti e siamo interessati a saperequanto vale modulo n (cioe a sapere il resto del risultato dell’espressione modulo n), allora tutti iconti e tutti i risultati intermedi li posso fare modulo n (cioe prendendo il resto della divisione per nad ogni passaggio). Ad esempio, per calcolare 99993 mod 7 possiamo scrivere:

[99993]7 = [9999]37 = [3]37 = [27]7 = [6]7.

In seguito vedremo altri esempi simili di utilizzo di questa proprieta.

3.1 Criteri di divisibilita in base 10

Il nostro modo usuale di rappresentare i numeri e detto in base 10 in quanto utilizza 10 cifre. Sappiamoinoltre che le cifre in base dieci di un numero rappresentano, da destra a sinistra le unita, decine,centinaia, migliaia, etc. Ad esempio abbiamo:

7241 = 7 · 103 + 2 · 102 + 4 · 10 + 1.

Nel seguito scriveremo (dk−1dk−2 · · · d0)10 per indicare un intero positivo di k cifre decimali (si assumequindi 0 ≤ di ≤ 9, e dk−1 6= 0); tale numero rappresenta il valore:

dk−1 · 10k−1 + dk−2 · 10k−2 + · · ·+ d1 · 10 + d0. (20)

Teorema 6 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 3 se e solo se la somma delle cifre e divisibileper 3, cioe se abbiamo dk−1 + dk−2 + · · ·+ d0 mod 3 = 0.

Dimostrazione: Osserviamo che per ogni i > 0 abbiamo

[10i]3 = ([10]3)i = ([1]3)i = [1]3;

in altre parole 10i diviso 3 da sempre resto 1. Di conseguenza abbiamo:

[dk−1 · 10k−1 + · · ·+ d1 · 10 + d0]3 = [dk−1]3[10k−1]3 + · · ·+ [d1]3[10]3 + [d0]3= [dk−1]3[1]3 + · · ·+ [d1]3[1]3 + [d0]3= [dk−1]3 + · · ·+ [d1]3 + [d0]3= [dk−1 + · · ·+ d1 + d0]3

2

Osservazione 6 Notiamo che la dimostrazione dice qualcosa di piu del teorema. Infatti la dimostra-zione ci dice che [dk−1 + · · ·+ d1 + d0]3 e uguale al resto della divisione fra (dk−1dk−2 · · · d0)10 e 3. Adesempio, se dividiamo 1234 per 3 otteniamo come resto 1 + 2 + 3 + 4 mod 3 = 1. Questa osservazionesi applica a tutti i criteri di divisibilita descritti in questa sezione. 2

Teorema 7 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 9 se e solo se la somma delle cifre e divisibileper 9, cioe se abbiamo dk−1 + dk−2 + · · ·+ d0 mod 9 = 0.

Dimostrazione: La dimostrazione e identica a quella del teorema precedente in quanto abbiamo[10i]9 = ([10]9)i = ([1]9)i = [1]9. 2

Teorema 8 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 2 se e solo se l’ultima cifra e pari, cioed0 mod 2 = 0.

3.1 Criteri di divisibilita in base 10 17

Dimostrazione: Dato che per i > 0 si ha [10i]2 = ([10]2)i = ([0]2)i = [0]2, abbiamo

[dk−1 · 10k−1 + · · ·+ d1 · 10 + d0]2 = [dk−1]2[10k−1]2 + · · ·+ [d1]2[10]2 + [d0]2= [dk−1]2[0]2 + [dk−2]2[0]2 + · · ·+ [d1]2[0]2 + [d0]2= [d0]2

2

Teorema 9 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 4 se e solo se il numero formato dalle ultimedue cifre e divisibile per 4, cioe (d1d0)10 mod 4 = 0.

Dimostrazione: Abbiamo che per i > 1 si ha [10i]4 = ([10]4)i = ([0]4)i = [0]4. di conseguenzapossiamo scrivere:

[dk−1 · 10k−1 + · · ·+ d1 · 10 + d0]4 = [dk−1]4[10k−1]4 + · · ·+ [d1]4[10]4 + [d0]4= [dk−1]4[0]4 + [dk−2]4[0]4 + · · ·+ [d1]4[10]4 + [d0]4= [d1 · 10 + d0]4

2

Osservazione 7 Il Teorema 9 puo essere generalizzato. Abbiamo infatti che per i ≥ j, 10i e multiplodi 2j cioe [10i]2j = [0]2j . Di conseguenza abbiamo che (dk−1dk−2 · · · d0)10 e divisibile per 2j se ilnumero formato dalle sue ultime j cifre lo e. In altre parole (dk−1dk−2 · · · d0)10 e divisibile per 2j

se (dj−1dj−2 · · · d0)10 lo e. Ad esempio 1483290160 e divisibile per 16 in quanto 0160 (cioe 160) edivisibile per 16. 2

Teorema 10 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 5 se e solo se l’ultima cifra e 0 o 5.

Dimostrazione: Dato che per i > 0 si ha [10i]5 = ([10]5)i = ([0]5)i = [0]5, abbiamo

[dk−1 · 10k−1 + · · ·+ d1 · 10 + d0]5 = [dk−1]5[10k−1]5 + · · ·+ [d1]5[10]5 + [d0]5= [dk−1]5[0]5 + [dk−2]5[0]5 + · · ·+ [d1]5[0]5 + [d0]5= [d0]5

2

Teorema 11 Il numero (dk−1dk−2 · · · d0)10 e divisibile per 11 se e solo se d0 − d1 + d2 − d3 +· · · (−1)k−1dk−1 e divisibile per 11.

Dimostrazione: Osserviamo che 10 ≡11 −1, quindi [10]i11 = [−1]i11. Di conseguenza per i pari[10]i11 = [1]11, mentre per i dispari [10]i11 = [−1]11. Abbiamo quindi:

[(dk−1dk−2 · · · d0)10]11 = [d0]11 + [d1]11[10]11 + [d2]11[102]11 + · · ·+ [dk−1]11[10k−1]11

= [d0]11 + [d1]11[−1]11 + [d2]11[1]11 + · · ·+ [dk−1]11[(−1)k−1]11

= [d0]11 + [−d1]11 + [d2]11 + · · ·+ [(−1)k−1dk−1]11

= [d0 − d1 + d2 + · · ·+ (−1)k−1dk−1]11

2

Ad esempio abbiamo che 231 e divisibile per 11 in quanto 2−3+1 = 0. Analogamente 5390 e multiplodi 11 in quanto −5 + 3− 9 = −11.

Concludiamo questa sezione osservando che e possibile ottenere altri criteri di divisibilita “com-ponendo” quelli che abbiamo appena visto. Ad esempio, utilizzando i Teoremi 6 e 8 otteniamo cheun numero e divisibile per 6 se e solo se la somma delle sue cifre e multipla di 3 e l’ultima cifra epari. Analogamente abbiamo che un numero e divisibile per 45 se e solo se la somma delle sue cifre emultipla di 9 e l’ultima cifra e 0 o 5.


Esercizio 13 Dimostrare che per un qualsiasi numero di 2 cifre (d1d0)10 si ha che (d1d0)10− (d0d1)10

e un multiplo di 9. Ad esempio 31− 13 = 18, 38− 83 = −45, etc.

Soluzione. Abbiamo

(d1d0)10 − (d0d1)10 = d1 · 10 + d0 − d0 · 10 + d1 = 9(d1 − d0).

2

3.2 Rappresentazione di un numero in base b 6= 10

E possibile rappresentare gli interi utilizzando una qualsiasi base b > 1. Lavorare in base b vuoldire rappresentare i numeri utilizzando b cifre che compongono i numeri con uno schema analogo allaformula (20). Ad esempio, se lavoriamo in base 3, abbiamo a disposizione le cifre 0, 1, 2, ed il numeroin base 3 (20010)3 rappresenta il valore:

(21011)3 = 2 · 34 + 1 · 33 + 0 · 32 + 1 · 3 + 1 = 2 · 81 + 1 · 27 + 1 · 3 + 1 = 104.

Gli interi 1, . . . , 10 scritti in base 3 risultano quindi:

1 = (1)3, 2 = (2)3, 3 = (10)3, 4 = (11)3, 5 = (12)3,

6 = (20)3, 7 = (21)3, 8 = (22)3, 9 = (100)3, 10 = (101)3.(21)

In generale, se lavoriamo in base b abbiamo b cifre i cui valori sono 0, 1, 2, . . . , b − 1. Un genericonumero in base b di k cifre lo scriviamo nella forma (dk−1dk−2 · · · d0)b e rappresenta il valore

dk−1 · bk−1 + dk−2 · bk−2 + · · ·+ d1 · b+ d0. (22)

Se b ≥ 10, per rappresentare le cifre di valore maggiore di 9 si usano solitamente le lettere dell’alfabeto.Ad esempio in informatica si usa a volte la base 16 e si usano le lettere A,B, . . . , F per rappresentarele cifre di valore da 10 a 15. Il numero in base 16 (2A3E)16 denota quindi il valore

(2A3E)16 = 2 · 163 + 10 · 162 + 3 · 16 + 14 = 10814.

Un’altra base che gli informatici devono conoscere e naturalmente la base 2 che e quella utilizzatainternamente dagli elaboratori elettronici. Lavorando in base 2 abbiamo a disposizione solo le duecifre 0 e 1. Il numero in base 2 (10101000111110)2 rappresenta quindi il valore

(10101000111110)2 = 213 + 211 + 29 + 25 + 24 + 23 + 22 + 21 = 10814.

Osserviamo che per rappresentare 10814 sono necessarie 4 cifre se lavoriamo in base 16, e 14 cifre selavoriamo in base 2. Questo e vero in generale: maggiore e la base, minore il numero di cifre necessarieper rappresentare un dato numero.

E importante sottolineare che i criteri di divisibilita che abbiamo visto nella Sezione 3.1 per inumeri rappresentati in base 10 non sono validi se lavoriamo in una base diversa. Ad esempio, leformule (21) mostrano che lavorando in base 3 non e vero che un numero e pari se e solo se la suaultima cifra e pari. E possibile pero stabilire dei criteri di divisibilita anche per numeri in base diversada 10 come mostrato dai seguenti esercizi.

Esercizio 14 Dimostrare che il numero (dk−1dk−2 · · · d0)3 e divisibile per due se e solo se la sommadelle cifre e pari, cioe se abbiamo dk−1 + dk−2 + · · ·+ d0 mod 2 = 0.

Soluzione. Osserviamo che per ogni i > 0 abbiamo

[3i]2 = ([1]2)i = [1]2;

in altre parole 3i diviso 2 da sempre resto 1. Di conseguenza abbiamo:

[dk−1 · 3k−1 + · · ·+ d1 · 3 + d0]2 = [dk−1]2[3k−1]2 + · · ·+ [d1]2[3]2 + [d0]2= [dk−1]2[1]2 + · · ·+ [d1]2[1]2 + [d0]2= [dk−1 + · · ·+ d1 + d0]2

2

3.3 Algoritmo veloce per l’elevamento a potenza 19

Osservazione 8 Questo esercizio puo essere generalizzato nel seguente modo: se c divide b−1 il numeroin base b (dk−1dk−2 · · · d0)b e divisibile per c se e solo se dk−1 +dk−2 + · · ·+d0 mod c = 0. (Provare peresercizio a dimostrare questa affermazione). Ad esempio, il numero in base sedici (dk−1dk−2 · · · d0)16 edivisibile per 5 se e solo se dk−1 + dk−2 + · · ·+ d0 mod 5 = 0. Quindi abbiamo che (3B1)16 e divisibileper 5 in quanto 3 + 11 + 1 = 15 (infatti (3B1)16 = (780)10). 2

Esercizio 15 Dimostrare che numero (dk−1dk−2 · · · d0)6 e divisibile per 7 se e solo se d0 − d1 + d2 −d3 + · · · (−1)k−1dk−1 e divisibile per 7.

Soluzione. Si osserva che [6i]7 = [−1]i7 e si procede come nella dimostrazione del Teorema 11. 2

Esercizio 16 Dimostrare che numero (dk−1dk−2 · · · d0)12 e divisibile per 9 se e solo se d1 · 12 + d0 edivisibile per 9. Ad esempio (316)12 e divisibile per 9 in quanto 1 · 12 + 6 = 18.

Soluzione. Si osserva che per i ≥ 2 si ha [12i]9 = [0]9 e si procede come nella dimostrazione delTeorema 9. 2

3.3 Algoritmo veloce per l’elevamento a potenza

Supponiamo di voler calcolare [3]6411. Invece di eseguire 63 moltiplicazioni [3]11 × [3]11 × · · · × [3]11,

osservando che 64 = 26 possiamo cavarcela con solo 6 moltiplicazioni. Abbiamo infatti:

[3]211 = [9]11, [3]411 = [9]211 = [4]11, [3]811 = [4]211 = [5]11,

[3]1611 = [5]211 = [3]11, [3]32

11 = [3]211 = [9]11, [3]6411 = [9]211 = [4]11.

Il risparmio e notevole: vale quindi la pena di cercare di generalizzare questo metodo anche nei casiin cui l’esponente non e una potenza di 2. Supponiamo ad esempio di voler calcolare [7]41

11. Comeprimo passo scriviamo l’esponente 41 in forma binaria (vedere Sezione 3.2), abbiamo: 41 = (101001)2.Questo vuol dire che:

41 = 25 + 23 + 20.

Per le proprieta delle potenze abbiamo:

[7]4111 = [7]2

5+23+20

11 = [7]25

11 · [7]23

11 · [7]20

11.

Di conseguenza, per calcolare [7]4111 dobbiamo semplicemente calcolare [7]2

5

11, [7]23

11, e [7]20

11 e moltiplicarequesti tre valori tra loro. Ma noi abbiamo appena visto che mediante elevamenti al quadrato successivipossiamo calcolare velocemente [7]11 elevato ad una potenza di 2. Abbiamo infatti:

[7]211 = [5]11, [7]22

11 = [5]211 = [3]11, [7]23

11 = [3]211 = [9]11, [7]24

11 = [9]211 = [4]11, [7]25

11 = [4]211 = [5]11,

e possiamo quindi concludere che

[7]4111 = [7]2

5

11 · [7]23

11 · [7]20

11 = [5]11 · [9]11 · [7]11 = [7]11.

Esempio 14 Supponiamo di dover calcolare [5]123419 . Abbiamo

1234 = (10011010010)2 = 210 + 27 + 26 + 24 + 21,

quindi[5]1234

19 = [5]210

19 · [5]27

19 · [5]26

19 · [5]24

19 · [5]21

19.

Calcoliamo [5]2i

19 per i = 1, 2, . . . , 10:

[5]219 = [6]19, [5]22

19 = [−2]19, [5]23

19 = [4]19, [5]24

19 = [−3]19, [5]25

19 = [9]19

[5]26

19 = [5]19, [5]27

19 = [6]19 [5]28

19 = [−2]19, [5]29

19 = [4]19, [5]210

19 = [−3]19


Abbiamo allora

[5]123419 = [5]2

10

19 · [5]27

19 · [5]26

19 · [5]24

19 · [5]21

19 = [−3]19 · [6]19 · [5]19 · [−3]19 · [6]19 = [5]19.

2

Riassumendo: per calcolare la potenza [t]mn scriviamo m in binario m = (dk−1 · · · d1d0)2, calcoliamole potenze

[t]2n, [t]22

n , [t]23

n , . . . [t]2k−1

n ,

e moltiplichiamo tra loro tutte le potenze [t]2i

n corrispondenti alle cifre di uguali a 1 (ricordiamo che ognidi puo essere solamente 0 o 1). Osserviamo che calcolare [t]mn utilizzando questo algoritmo eseguiamok−1 moltiplicazioni per calcolare le potenze [t]2

i

n per i = 1, . . . , k−1 e al piu altre k−1 moltiplicazioniper calcolare [t]mn . Si puo dimostrare che k−1 = blog2mc, quindi diciamo che il numero moltiplicazionieffettuate con questo algoritmo e al piu 2 blog2mc.

Esempio 15 Per calcolare [3]991000 in Z∗

1000 scriviamo 99 in binario

99 = (1100011)2 = 26 + 25 + 21 + 20.

Calcoliamo poi (mediante elevamenti al quadrato successivi)

[3]21000 = [9]1000, [3]41000 = [81]1000, [3]81000 = [561]1000,

[3]161000 = [721]1000, [3]32

1000 = [841]1000, [3]641000 = [281]1000.

Abbiamo quindi

[3]991000 = [3]64

1000[3]321000[3]21000[3]1000 = [281]1000[841]1000[9]1000[3]1000 = [667]1000.

2

3.4 Il teorema cinese del resto

Dati quattro interi a, b, x, y con a e b positivi, supponiamo di voler trovare tutti gli interi n tali chen− x e un multiplo di a e n− y e un multiplo di b. Ricordando la Definizione 3, abbiamo che questoproblema e equivalente a trovare tutti gli interi n che soddisfano al sistema{

n ≡a xn ≡b y. (23)

Ad esempio, risolvere il sistema {n ≡5 1n ≡3 2

vuol dire trovare tutti gli interi n tali che n−1 e multiplo di 5 e, contemporaneamente, n−2 e multiplodi 3. Una soluzione del sistema e il valore n = 11 in quanto 11− 1 = 5 · 2 e n− 2 = 3 · 3.

Un sistema del tipo (23) e detto sistema di congruenze e, come vedremo, ha un ruolo importante inmatematica discreta. Enunciamo ora il teorema cinese del resto che fornisce un meccanismo standardper risolvere un sistema di congruenze del tipo (23). Il primo passo verso la soluzione consiste neltrasformare il sistema (23) nella forma {

n = at+ xn = bs+ y

e osservare che le due nuove equazioni implicano che deve essere at + x = bs + y. Il sistema (23)e quindi risolubile se e solo se l’equazione diofantea at − bs = y − x (nelle incognite s, t) ammettesoluzione. Di conseguenza, il sistema e risolubile se e solo se d = MCD(a, b) divide y − x. Se talecondizione e verificata calcoliamo, utilizzando l’algoritmo di Euclide esteso, una coppia di valori t0, s0tali che at0 − bs0 = y − x. La soluzione generale dell’equazione diofantea e data allora da

t = t0 + λ(b/d), s = s0 + λ(a/d).

3.4 Il teorema cinese del resto 21

Sostituendo l’espressione di t nella relazione n = at + x otteniamo n = at0 + x + λ(ab/d). In altreparole, se il sistema (23) e risolubile allora le soluzione formano una classe di resto modulo (ab)/d.Ricordando che (ab)/d e uguale a mcm(a, b) (il minimo comune multiplo fra a e b, vedere Sezione 1.4),possiamo riassumere queste considerazioni nel seguente teorema.

Teorema 12 (Teorema cinese del resto). Il sistema di congruenze (23) e risolubile se e solo seMCD(a, b) divide y − x. Se il sistema e risolubile, le soluzioni formano una classe di resto modulomcm(a, b). 2

Una prima applicazione del teorema e il fatto che per risolvere un sistema del tipo (23) e sufficienteverificare che sia risolubile e trovare una singola soluzione n0. Infatti il teorema cinese del resto ci diceche tutte le altre soluzioni sono gli interi nella stessa classe di resto di n0 modulo mcm(a, b).

Esempio 16 Supponiamo di dover risolvere il sistema:{n ≡22 5n ≡12 1.

Abbiamo che MCD(22, 12) divide 1 − 5 = −4 quindi il sistema e risolubile. Dobbiamo risolverel’equazione 22s − 12t = −4, cioe 11s − 6t = −2. Una soluzione e s0 = 2, t0 = 4. Dalla questasoluzione ottengo n0 = 22 · 2 + 5 = 49. Dato che sappiamo che le soluzioni formano una classe di restomodulo mcm(12, 22) = 132 abbiamo che la soluzione del nostro sistema e [49]132, o, equivalentemente,n ≡132 49. 2

Esempio 17 Supponiamo di voler trovare gli interi n che soddisfano alle 3 congruenze:n ≡7 3n ≡4 1n ≡5 3.

(24)

Cominciamo risolvendo un sistema con le prime due congruenze:{n ≡7 3n ≡4 1.

(25)

Deve essere 7s+ 3 = 4t+ 1, cioe 7s− 4t = −2. Una soluzione e data da s0 = 2, t0 = 4 di conseguenzauna soluzione del sistema (25) e data da n0 = 17. Il teorema cinese del resto ci dice che la soluzionedel sistema (25) e una classe di resto modulo 28, quindi gli interi n che soddisfano la (25) sono quellidella forma n ≡28 17. Abbiamo allora che gli interi che soddisfano alle tre congruenze (24) sono quelliche soddisfano al sistema {

n ≡28 17n ≡5 3.

(26)

Quest’ultimo sistema e equivalente all’equazione diofantea 28x + 17 = 5y + 3, cioe 28x − 5y = −14.Con l’algoritmo di Euclide si trova 28 · 2− 5 · 11 = 1, quindi una soluzione dell’equazione diofantea ex0 = −28, y0 = −154. Abbiamo quindi che una soluzione del sistema (25) e n0 = 5 ·−154 + 3 = −767.Per il teorema cinese del resto la soluzione di (26), e quindi anche del sistema iniziale (24), e data dan ≡140 −767, cioe n ≡140 73. 2

Esercizio 17 Dire per quali valori del parametro a ∈ Z e possibile trovare un intero n tale che ilsistema {

n ≡180 21 + an ≡105 2a− 1.

ammette soluzioni. Si trovino tutte le soluzioni per a = −68.

Soluzione. Il sistema e equivalente all’equazione diofantea 21 + a + 180x = 2a − 1 + 105y, cioe180x− 105y = a− 22. L’equazione e risolubile quando a− 22 e un multiplo di 15 = MCD(105, 180),cioe [a]15 = [22]15 = [7]15. Per a = −68 l’equazione diofantea diventa 180x − 105y = −90 che eequivalente a 12x− 7y = −6. Quest’ultima ha come soluzioni x = −18− 7k, y = −30− 12k per i qualisi ottiene n = −3287− 1260k (o equivalentemente n ≡1260 493). 2


Esercizio 18 I lavoratori di una fabbrica, oltre al riposo domenicale hanno diritto ad un riposo extraogni 19 giorni contati a partire dal primo gennaio (quindi il primo riposo extra sara il primo gennaio,il secondo il 20 gennaio e cosı via). Sapendo che nel 2008 il primo gennaio e giovedı si dica quantevolte nel corso del 2008 il riposo extra e il riposo domenicale capiteranno in due giorni consecutivi.

Soluzione. Numeriamo i giorni dell’anno da 1 a 366 (il 2008 e bisestile). Dato che il primo gennaio egiovedı, le domeniche cadono nei giorni n ≡7 4 con 1 ≤ n ≤ 366. Il riposo extra cade invece nei giornin ≡19 1. Si hanno due giorni di riposo consecutivo quando il riposo extra cade di sabato o di lunedı.Dobbiamo quindi contare il numero di soluzioni dei due sistemi{

n ≡19 1n ≡7 3

{n ≡19 1n ≡7 5

con il vincolo 1 ≤ n ≤ 366. Il primo sistema e equivalente a n ≡133 115 e quindi in [1, 366] ha lesoluzioni 115 e 248. Il secondo sistema e equivalente a n ≡133 96 e quindi in [1, 366] ha le soluzioni 96,229, e 362. In totale quindi il numero di volte che si hanno 2 giorni di riposo consecutivi e 5. 2

3.5 Condivisione di segreti

Il Presidente Hush ha un problema. Ha una cassaforte piena di materiale segreto ed e necessarioche, in sua assenza, i suoi tre piu importanti collaboratori ci possano accedere. Hush pero non sifida totalmente di loro e quindi non vuole dare la combinazione completa ad ognuno di loro; l’idealesarebbe un meccanismo che permetta di aprire la cassaforte solamente se due di essi collaborano peraprirla. Idealmente vorremmo quindi dividere la combinazione in 3 “pezzi” tali che solamente l’unionedi due qualsiasi di questi “pezzi” permetta di ricostruire la combinazione.

Il consigliere per la sicurezza nazionale, Compostezza Ribe, ha studiato Matematica Discretaall’universta e fornisce a Hush la soluzione. Siano a, b, c tre numeri primi tra loro con a < b < c. Adesempio prendiamo a = 31, b = 32, c = 33. Sia n = ab (n = 992 nel nostro esempio); la combinazionex deve essere un numero compreso fra 0 e n − 1. Nel nostro caso prendiamo x = 711. Il presidenteHush comunica al primo collaboratore x mod a, al secondo x mod b e al terzo x mod c (i valori a, b, ced n invece sono noti a tutti). Nel nostro esempio quindi, al primo collaboratore viene comunicato711 mod 31 = 29, al secondo 711 mod 32 = 7, al terzo 711 mod 33 = 18. E evidente che un singolocollaboratore non possiede sufficiente informazioni per aprire la cassaforte. Supponiamo invece cheil secondo e il terzo collaboratore decidano congiuntamente di aprire la cassaforte. Per ricostruire lacombinazione non devono fare altro che risolvere il sistema di congruenze{

x ≡32 7x ≡33 18

la cui soluzione generale e x = 711 + 1056k. In questo insieme di soluzioni l’unica compresa fra 0 e992 e 711 che quindi sara la combinazione della cassaforte.

Osserviamo che questo metodo puo essere generalizzato al caso in cui ci sono n collaboratori e sivuole che k di essi siano necessari per la ricostruzione di un segreto (con 1 ≤ k ≤ n).

Esercizio 19 Costruire uno schema di condivisione di segreti che permetta a cinque partecipanti A,

B, C, D, E di condividere un segreto. Lo schema deve essere tale che il segreto deve poter esserericostruito solo mediante la collaborazione di A e di altri 2 partecipanti. Il modulo assegnato ad ognipartecipante deve essere maggiore o uguale a 40.

Soluzione. E sufficiente scegliere 7 numeri primi tra loro maggiori o uguali a 40. Possiamo prendere41, 42, 43, 47, 49, 51, 53. Il segreto e identificato da una chiave k compresa fra 0 e 41 · 42 · 43 ·47 · 49 − 1 = 170527937 (usiamo quindi il prodotto di 5 moduli). Ad A viene assegnato il valorek mod 41 · 42 · 43 = 74046. Ai partecipanti B, C, D, E vengono assegnati rispettivamente i valori kmodulo 47, 49, 51, 53. E immediato verificare che senza la collaborazione di A il segreto non puo esserericostruito in quanto gli altri partecipanti insieme possono ottenere solo k mod 47·49·51·53 = 6225009.Utilizzando invece i 3 moduli conosciuti da A e altri due moduli qualsiasi e sempre possibile ricostruireil segreto. 2

23

4 Il teorema di Eulero

In questo capitolo verra illustrato un importante teorema dimostrato per la prima volta dal matematicosvizzero Leonhard Euler (Eulero) nel 1736. Questo teorema e solo uno dei tanti contributi dati allafisica e alla matematica da questo prolifico studioso le cui opere complete assommano a piu di 60volumi. La particolarita di questo teorema e che, a distanza di 200 anni dalla sua prima enunciazione,e stato recentemente utilizzato per la costruzione di algoritmi di crittografia.

4.1 La funzione ϕ di Eulero

La funzione ϕ di Eulero associa ad ogni intero n ≥ 1 il numero di interi compresi tra 0 e n − 1 chesono coprimi con n. Formalmente abbiamo:

ϕ(n) =def |{0 ≤ b < n | MCD(b, n) = 1}| . (27)

Ad esempio, alcuni valori della funzione ϕ sono dati da

ϕ(6) = 2 in quanto {0 ≤ b < 6 | MCD(b, 6) = 1} = {1, 5};

ϕ(7) = 6 in quanto {0 ≤ b < 7 | MCD(b, 7) = 1} = {1, 2, 3, 4, 5, 6};

ϕ(8) = 4 in quanto {0 ≤ b < 8 | MCD(b, 8) = 1} = {1, 3, 5, 7};

ϕ(1) = 1 in quanto {0 ≤ b < 1 | MCD(b, 1) = 1} = {0};

Dato n, possiamo sempre ottenere ϕ(n) calcolando MCD(i, n) per i = 0, 1, . . . , n − 1 e contandoquante volte il MCD e uguale a 1. Questo procedimento chiaramente non e molto veloce. Nel caso incui conosciamo la fattorizzazione di n e possibile calcolare molti piu velocemente ϕ(n) utilizzando ilseguente risultato.

Teorema 13 Se n = pk con p primo k ≥ 1, allora ϕ(n) = pk − pk−1. Se MCD(m,n) = 1 alloraϕ(mn) = ϕ(m)ϕ(n). 2

La prima parte del teorema ci dice, ad esempio, che ϕ(32) = 25−24 = 16. La seconda parte del teoremaci dice, ad esempio, che ϕ(35) = ϕ(5)ϕ(7). Dato che per la prima parte del teorema ϕ(5) = 51−50 = 4e ϕ(7) = 71 − 70 = 6 abbiamo che ϕ(35) = 24.

Esempio 18 Per calcolare ϕ(12) osserviamo che per la seconda parte del Teorema 13 abbiamo ϕ(12) =ϕ(3)ϕ(4). Per la prima parte del teorema abbiamo ϕ(3) = 31 − 30 = 2, e ϕ(4) = 22 − 21 = 2. Diconseguenza ϕ(12) = 4. Per verificare la correttezza di questo risultato osserviamo che

{0 ≤ b < 12 | MCD(b, 12) = 1} = {1, 5, 7, 11}.

2

Esempio 19 Per calcolare ϕ(30) osserviamo che per la seconda parte del Teorema 13 abbiamo ϕ(30) =ϕ(5)ϕ(6). Sempre per la seconda parte del teorema abbiamo ϕ(6) = ϕ(3)ϕ(2). Di conseguenzaϕ(30) = ϕ(5)ϕ(3)ϕ(2) = 4 · 2 · 1 = 8. Per verificare la correttezza di questo risultato osserviamo che

{0 ≤ b < 30 | MCD(b, 30) = 1} = {1, 7, 11, 13, 17, 19, 23, 29}.

2

Gli esempi precedenti mostrano che il Teorema 13 permette di calcolare la funzione ϕ per ogniintero n del quale conosciamo la fattorizzazione. Infatti, se la scomposizione in fattori primi di n e

n = pk11 pk22 · · · p

khh

24 4 IL TEOREMA DI EULERO

allora, applicando piu volte la seconda parte del teorema abbiamo

ϕ(n) = ϕ(pk11 pk22 p

k33 · · · p

khh )

= ϕ(pk11 )ϕ(pk22 pk33 · · · p

khh )

= ϕ(pk11 )ϕ(pk22 )ϕ(pk33 · · · pkhh )

= ϕ(pk11 )ϕ(pk22 )ϕ(pk33 ) · · ·ϕ(pkhh );

e per la prima parte del teorema abbiamo

ϕ(n) =(pk11 − p

k1−11

) (pk22 − p

k2−12

) (pk33 − p

k3−13

)· · ·(pkhh − p

kh−1h

).

Ad esempio abbiamo ϕ(30000000000) = ϕ(3)ϕ(210)ϕ(510) = 2(210 − 29)(510 − 59) = 8 · 109.

4.2 Il teorema di Eulero

Per n > 1 indichiamo con Z∗n il sottoinsiene di Zn formato delle classi di resto [i]n tali che MCD(i, n) =

1. Formalmente definiamoZ∗n =def {[i]n ∈ Zn | MCD(i, n) = 1}.

Per i risultati delle sezione precedente abbiamo che Z∗n contiene esattamente ϕ(n) elementi. Inoltre,

per i risultati della Sezione 2.2 sappiamo che Z∗n contiene tutte e sole le classi di resto di Zn che hanno

l’inverso moltiplicativo.

Esempio 20 Abbiamo ϕ(24) = 8 e Z∗24 = {[1]24, [5]24, [7]24, [11]24, [13]24, [17]24, [19]24, [23]24}. 2

Teorema 14 (Teorema di Eulero). Sia n > 1. Per ogni a ∈ Z∗n abbiamo

aϕ(n) = [1]n.

2

Esempio 21 Come primo esempio di applicazione del teorema di Eulero consideriamo il caso n = 10.Abbiamo ϕ(10) = 4, quindi il teorema ci dice che le classi [1]10, [3]10, [7]10, [9]10 (che sono gli elementidi Z∗

10) elevate alla potenza 4 danno la classe [1]10. Che [1]410 = [1]10 e immediato. Negli altri casiabbiamo:

[3]210 = [9]10 [3]310 = [7]10 [3]410 = [1]10

[7]210 = [9]10 [7]310 = [3]10 [7]410 = [1]10

[9]210 = [1]10 [9]310 = [9]10 [9]410 = [1]10.

2

Esempio 22 Come secondo esempio di applicazione del teorema di Eulero consideriamo il caso n = 7.Abbiamo ϕ(7) = 6, quindi il teorema ci dice che gli elementi di Z∗

7 elevati alla potenza 6 danno laclasse [1]7. Che [1]67 = [1]7 e immediato. Negli altri casi abbiamo:

[2]27 = [4]7 [2]37 = [1]7 [2]47 = [2]7 [2]57 = [4]7 [2]67 = [1]7

[3]27 = [2]7 [3]37 = [6]7 [3]47 = [4]7 [3]57 = [5]7 [3]67 = [1]7

[4]27 = [2]7 [4]37 = [1]7 [4]47 = [4]7 [4]57 = [2]7 [4]67 = [1]7

[5]27 = [4]7 [5]37 = [6]7 [5]47 = [2]7 [5]57 = [3]7 [5]67 = [1]7

[6]27 = [1]7 [6]37 = [6]7 [6]47 = [1]7 [6]57 = [6]7 [6]67 = [1]7.

2

4.2 Il teorema di Eulero 25

Osservazione 9 Una prima conseguenza del teorema di Eulero e che se a ∈ Z∗n l’inverso moltiplicativo

di a modulo n e b = aϕ(n)−1. Infatti

a · b = aaϕ(n)−1 = aϕ(n) = [1]n.

Abbiamo quindi una seconda strada (in aggiunta all’algoritmo di Euclide esteso) per calcolare l’inversomoltiplicativo di un elemento di Z∗

n. 2

Esercizio 20 Calcolare l’inverso di [3]19 in Z∗19.

Soluzione. Dato che ϕ(19) = 18 abbiamo che l’inverso di [3]19 e [3]1719. Abbiamo:

[3]219 = [9]19, [3]419 = [9]219 = [5]19, [3]819 = [5]219 = [6]19, [3]1619 = [6]219 = [17]19.

Di conseguenza l’inverso di [3]19 e dato da [3]1719 = [3]19[17]19 = [13]19. 2

Osservazione 10 Un’altra conseguenza del fatto che aϕ(n) = [1]n e che se MCD(a, n) = 1 lavorandoin Z∗

n gli esponenti di a possono essere ridotti modulo ϕ(n). Ad esempio, se si deve calcolare a10000

modulo n con con 10000 > ϕ(n) possiamo dividere 10000 per ϕ(n) ottenendo un quoziente q ed unresto r. Abbiamo allora

a10000 = aqϕ(n)+r = (aϕ(n))q · ar = ([1]n)q · ar = ar.

In altre parole non e mai necessario eseguire elevamenti a potenze maggiori di ϕ(n). 2

Esercizio 21 Calcolare [7]1234567890100 in Z∗

100.

Soluzione. Abbiamo ϕ(100) = 40. La divisione fra 1234567890 e 40 da resto 10 (applicando i criteridi divisibilita sappiamo infatti che 1234567880 e multiplo di 40). Abbiamo quindi

[7]123456789100 = [7]10

100 = [49]100.

2

Dato un elemento a ∈ Z∗n si definisce l’ordine di a come il piu piccolo intero positivo t ≥ 1 per cui

si ha at = [1]n. Ad esempio, nel caso n = 7, la tabella delle potenze appena vista ci dice che l’ordine di[2]7 e 3, l’ordine di [3]7 e 6, l’ordine di [4]7 e 3, l’ordine di [5]7 e 6, e l’ordine di [6]7 e 2. Infine abbiamoche l’ordine di [1]7 e 1 (in generale abbiamo che per ogni n > 1, l’ordine di [1]n e 1). Osserviamo chel’ordine degli elementi di Z∗

7 sono tutti divisori di 6. Il seguente corollario del teorema di Eulero cidice che questo non e un caso.

Corollario 2 Per ogni a ∈ Z∗n l’ordine di a e un divisore di ϕ(n).

Dimostrazione: Sia t l’ordine di a, cioe il piu piccolo intero positivo per cui at = [1]n. Osserviamoche per il teorema di Eulero aϕ(n) = [1]n quindi sicuramente t ≤ ϕ(n). Vogliamo mostrare che t divideϕ(n). Eseguiamo la divisione euclidea tra ϕ(n) e t, ottenendo un quoziente q ed un resto r. Abbiamoallora che

ϕ(n) = tq + r, con 0 ≤ r < t. (28)

Il nostro obbiettivo e dimostrare che r = 0. Dalla (28), ricordando che at = [1]n, segue che

aϕ(n) = atq+r = atqar = (at)q ar = ([1]n)qar = ar.

Abbiamo quindi che ar = aϕ(n) = [1]n. Ricordiamo che t e il piu piccolo intero positivo per cuiat = [1]n. Se fosse r > 0 avremmo trovato un intero positivo piu piccolo di t per cui ar = [1]n. Maquesto e impossibile, quindi deve essere r = 0 e di conseguenza t divide ϕ(n). 2


Esempio 23 Consideriamo Z∗15 = {[1]15, [2]15, [4]15, [7]15, [8]15, [11]15, [13]15, [14]15}. Abbiamo ϕ(15) =

8, quindi gli ordini degli elementi di Z∗15 possono essere 1,2,4, oppure 8. La classe [1]15 ha ordine 1.

Per quanto riguarda le altre classi abbiamo:

[2]215 = [4]15 [2]315 = [8]15 [2]415 = [1]15

[4]215 = [1]15

[7]215 = [4]15 [7]315 = [13]15 [7]415 = [1]15

[8]215 = [4]15 [8]315 = [2]15 [8]415 = [1]15

[11]215 = [1]15

[13]215 = [4]15 [7]315 = [13]15 [13]415 = [1]15

[14]215 = [1]15

Quindi le classi [2]15, [7]15, [8]15, e [13]15 hanno ordine 4, mentre le classi [4]15, [11]15, e [14]15 hannoordine 2. 2

Nell’Esempio 23 abbiamo che ϕ(15) = 8 ma in Z∗15 non esistono elementi di ordine 8. In generale,

abbiamo che se d divide ϕ(n) non e detto che esista un elemento di Z∗n che abbia ordine d. Osserviamo

anche che la classe [1]n ha ordine 1, ma tutte le altri classi hanno ordine maggiore di 1 (in quanto[a]1n = [a]n).

Esercizio 22 Calcolare l’ordine di [2]11 in Z∗11.

Soluzione. Dato che ϕ(11) = 10 l’ordine puo essere 2, 5, o 10. Abbiamo:

[2]211 = [4]11, [2]311 = [8]11, [2]411 = [5]11, [2]511 = [10]11

quindi l’ordine di [2]11 e maggiore di 5. Possiamo concludere, senza ulteriori calcoli, che l’ordine di[2]11 e 10. 2


Soluzione. Dato che ϕ(32) = 16 l’ordine puo essere 2, 4, 8, o 16. Osserviamo che per calcolare l’ordinedi [11]32 non e necessario calcolare [11]i32 per i = 1, 2, 3, . . ., ma possiamo limitarci agli esponenti dellaforma 2j . Abbiamo

[11]232 = [25]32, [11]432 = ([11]232)2 = [25]232 = [17]32, [11]832 = ([11]432)2 = [17]232 = [1]32

quindi l’ordine di [11]32 e 8. 2


Soluzione. Dato che ϕ(13) = 12 l’ordine puo essere 2, 3, 4, 6, o 12. Abbiamo

[11]213 = [4]13, [11]313 = [5]13, [11]413 = ([11]213)2 = [4]213 = [3]13, [11]613 = ([11]313)2 = [5]213 = [12]13



Soluzione. Dato che ϕ(100) = (4− 2)(25− 5) = 40 l’ordine puo essere 1, 2, 4, 8, oppure uno di questiquattro numeri moltiplicati per 5. Abbiamo

[3]2100 = [9]100, [3]4100 = [81]100, [3]8100 = [81]2100 = [61]100.

Proviamo ora con gli ordini 5, 10, 20, 40:

[3]5100 = [81]100[3]100 = [43]100, [3]10100 = [43]2100 = [49]100, [3]20

100 = [49]2100 = [1]100.


4.3 Il problema del logaritmo discreto 27

4.3 Il problema del logaritmo discreto

Ricordiamo che dato a ∈ Z∗n scriviamo a−1 per indicare l’inverso moltiplicativo di a, cioe la classe di

resto b tale che ab = [1]n. Ad esempio [3]−17 = [5]7 in quanto [3]7[5]7 = [1]7. Inoltre definiamo per ogni

a ∈ Z∗n a

0 = [1]n. E immediato verificare che con queste definizioni valgono le usuali proprieta dellepotenze

an am = an+m, (an)m = anm

per una qualsiasi coppia di interi n,m ∈ Z e per ogni a ∈ Z∗n.

Si ricorda che nei numeri reali indichiamo con loga b l’esponente che bisogna dare ad a per avereb, cioe se k = loga b allora ak = b. Avendo definito le potenze in Z∗

n e naturale introdurre il concettodi logaritmo anche in questo insieme.

Esempio 24 Sia a ∈ Z∗n, calcolare il logaritmo in base a di [1]n vuol dire trovare quali sono gli

esponenti k ∈ Z tale che ak = [1]n. Noi sappiamo che se t e l’ordine di a, allora t e il piu piccolo interopositivo per cui at = [1]n. Ma t non e l’unico intero per cui at = [1]n, e immediato verificare che perogni λ ∈ Z abbiamo aλt = [1]n. Di conseguenza l’insieme degli esponenti k per cui ak = [1]n coincidecon l’insieme dei multipli di t, cioe k ≡t 0, dove t e l’ordine di a. 2

Esercizio 26 Calcolare per quali interi k si ha [3]k100 = [1]100.

Soluzione. Nell’Esercizio 25 abbiamo visto che l’ordine di [3]100 e 20. La soluzione e quindi k ≡20 0,cioe k = . . . ,−40,−20, 0, 20, 40, 60, . . .. 2

Consideriamo ora il caso piu generale nel quale vogliamo calcolare per quali esponenti k si haak = b con a, b ∈ Z∗

n. Un metodo generale per risolvere questo problema e illustrato nel seguenteesempio.

Esempio 25 Vogliamo calcolare per quali k si ha [3]k11 = [4]11. Calcoliamo le potenze di [3]11 fino adottenere [1]11:

[3]211 = [9]11, [3]311 = [5]11, [3]411 = [4]11, [3]511 = [1]11. (29)

Abbiamo quindi che [3]411 = [4]11, inoltre l’ordine di [3]11 e uguale a 5. Di conseguenza abbiamo perogni λ ∈ Z

[3]4+5λ11 = [3]411 · ([3]511)λ = [4]11[1]λ11 = [1]11.

La soluzione al nostro problema sono quindi gli interi k della forma k = 4 + 5λ, cioe k ≡5 4.Osserviamo che se avessimo dovuto trovare per quali k si ha [3]k11 = [2]11, il problema non avrebbe

avuto soluzione. Dalla (29) possiamo infatti vedere che le potenze di [3]11 sono solamente le classi[3]11, [9]11, [5]11, [4]11, [1]11 che si ripetono ciclicamente. 2

Riassumendo, per calcolare per quali k ∈ Z si ha [a]kn = [b]n dobbiamo determinare l’ordine t di[a]n e dobbiamo verificare se esiste un k0 tale che [a]k0n = [b]n. Se tale k0 esiste la soluzione e k ≡t k0,se invece k0 non esiste (cioe calcolando le potenze successive di [a]n si ottiene [1]n senza aver ottenuto[b]n) allora il problema non ha soluzione (cioe non esistono k tali che [a]kn = [b]n). Nel caso particolarein cui [b]n = [1]n allora e sufficiente calcolare l’ordine t e la soluzione e k ≡t 0 (quindi se [b]n = [1]n lasoluzione esiste sempre).


Soluzione. Calcoliamo le potenze successive di [5]19 fino a quando non otteniamo [1]19

[5]219 = [6]19, [5]319 = [11]19, [5]419 = [17]19, [5]519 = [9]19,

[5]619 = [7]19, [5]719 = [16]19, [5]819 = [4]19, [5]919 = [1]19.

La soluzione e quindi k ≡9 7, cioe k = . . . ,−11,−2, 7, 16, . . .. 2



Soluzione. Per risolvere il problema dobbiamo solamente determinare l’ordine di [7]90. Essendo ϕ(90) =ϕ(2)ϕ(9)ϕ(5) = 24, l’ordine di [7]90 puo essere 2, 3, 4, 6, 8, 12, o 24. Abbiamo

[7]290 = [49]90, [7]390 = [73]90, [7]490 = [61]90,

[7]690 = [7]290[7]490 = [19]90, [7]890 = [31]90, [7]1290 = [7]490[7]890 = [1]90.

La soluzione e quindi k ≡12 0. 2

Esercizio 29 Calcolare per quali a ∈ Z∗17 il problema [4]k17 = [a]17[3]17 ammette soluzioni.

Soluzione. Calcoliamo le potenze di [4]17

[4]117 = [4]17, [4]217 = [16]17, [4]317 = [13]17, [4]417 = [1]17.

Il problema ammette soluzione quando [a]17[3]17 ∈ {[4]17, [16]17, [13]17, [1]17}. Dato che [3]−117 = [6]17,

abbiamo che i valori ammissibili di [a]17 sono quattro e precisamente

[a]17 = [6]17[4]17 = [7]17, [a]17 = [6]17[16]17 = [11]17,

[a]17 = [6]17[13]17 = [10]17, [a]17 = [6]17[1]17 = [6]17.

2

Esercizio 30 Dire per quali interi k si ha

777k ≡13 35 · 18k. (30)

Soluzione. La (30) e equivalente a[777k]13 = [35]13[18k]13

che a sua volte equivale a[10]k13 = [9]13[5]k13.

Per trasformare questa equazione in un problema di logaritmo discreto moltiplichiamo entrambi imembri per [5]−k13 .

[10]k13[5]−k13 = [9]13.

Abbiamo [5]−k13 = ([5]−113 )k = [8]k13. La nostra equazione diventa quindi

[10]k13[8]k13 = [9]13.

Essendo [10]k13[8]k13 = [80]k13 = [2]k13, l’equazione (30) risulta quindi equivalente a

[2]k13 = [9]13,

che risolta con le tecniche viste negli esercizi precedenti porta alla soluzione k ≡12 8. 2

Esercizio 31 Dire per quali interi k si ha

7 · 10k ≡11 8 · 9k. (31)

Soluzione. L’equazione (31) e equivalente a

[7]11 · [−1]k11 = [8]11 · [9]k11

Moltiplicando entrambi i membri per [8]−111 = [7]11 otteniamo

[7]11 · [7]11 · [−1]k11 = [9]k11,

4.3 Il problema del logaritmo discreto 29

da cui[5]11 · [−1]k11 = [9]k11.

Moltiplicando entrambi i membri per [−1]−k11 otteniamo

[5]11 = [9]k11[−1]−k11 = [9]k11([−1]−111 )k = [9]k11[−1]k11 = ([9]11[−1]11)k = [−9]k11 = [2]k11.

Dobbiamo quindi risolvere il problema[2]k11 = [5]11.

Abbiamo:[2]211 = [4]11, [2]311 = [8]11, [2]411 = [5]11, [2]511 = [10]11.

Abbiamo allora che [2]411 = [5]11 e che l’ordine di [2]11 e 10 (deve essere un divisore di ϕ(11) = 10 eabbiamo appena visto che non e ne 2 ne 5). La soluzione del problema (31) e quindi k ≡10 4. 2

Esercizio 32 Risolvere il sistema {62n ≡13 35n+ 3 ≡16 0.

(32)

Soluzione. Per risolvere il sistema dobbiamo portare ognuna delle due equazioni nella forma n ≡a xper poi applicare il teorema cinese del resto (vedi Sezione 3.4). Dato che [62n]13 = [62]n13 = [10]n13, laprima equazione diventa

[10]n13 = [3]13. (33)

Abbiamo:

[10]213 = [9]13, [10]313 = [12]13, [10]413 = [3]13, [10]513 = [4]13, [10]613 = [1]13.

La soluzione della (33) e quindi n ≡6 4.La seconda equazione del sistema si puo riscrivere come

[5]16 · [n]16 = [−3]16.

Dato che [5]−116 = [13]16, moltiplicando entrambi i termini per [13]16 otteniamo

[n]16 = [13]16[−3]16 = [−39]16 = [9]16.

La seconda equazione del sistema (32) ha quindi come soluzione n ≡16 9, e di conseguenza il siste-ma (32) e equivalente a {

n ≡6 4n ≡16 9.

Questo sistema pero non e risolubile in quanto MCD(6, 16) = 2 non divide 4 − 9 = −5. Possiamoconcludere allora che il sistema iniziale (32) non ammette nessuna soluzione intera. 2

Esercizio 33 Risolvere il sistema {2103n ≡11 42n ≡17 3n.

(34)

Soluzione. Come nell’esercizio precedente per risolvere il sistema dobbiamo portare ognuna delle dueequazioni nella forma n ≡a x per poi applicare il teorema cinese del resto (vedi Sezione 3.4). La primaequazione la scriviamo nella forma:

([2]10311 )n = [4]11. (35)

Dato che ϕ(11) = 10 abbiamo che [2]10011 = [1]11, quindi

[2]10311 = [2]100

11 [2]311 = [1]11[2]311 = [8]11

e l’equazione (35) diventa[8]n11 = [4]11.


Abbiamo[8]211 = [9]11, [8]311 = [6]11, [8]411 = [4]11, [8]511 = [10]11

quindi, ragionando come nell’Esercizio 31, otteniamo che la soluzione della prima equazione delsistema (34) e n ≡10 4.

Per quanto riguarda la seconda equazione del sistema (34) essa e equivalente a

[2]n17 = [3]n17.

Moltiplichiamo entrambi i membri per [2]−n17 e otteniamo

[2]n17[2]−n17 = [3]n17[2]−n17

da cui[1]17 = ([3]17[2]−1

17 )n.

Essendo [2]−117 = [9]17 abbiamo

[1]17 = [3 · 9]n17 = [10]n17.

Per risolvere questa equazione e sufficiente calcolare l’ordine di [10]17 che dovra essere un divisore diϕ(17) = 16. Abbiamo

[10]217 = [15]17, [10]417 = [4]17, [10]817 = [16]17, [10]1617 = [1]17.

La soluzione della seconda equazione del sistema (34) e quindi n ≡16 0.Abbiamo allora che il sistema (34) e equivalente al nuovo sistema{

n ≡10 4n ≡16 0.

Il teorema cinese del resto ci dice che questo sistema e risolubile in quanto MCD(10, 16) = 2 divide4 − 0 = 4. Inoltre sappiamo che la soluzione sara una classe di resto modulo mcm(10, 16) = 80.Svolgendo i conti come nella Sezione 3.4 si ottiene n ≡80 64. 2

Esercizio 34 Dire per quali valori del parametro a il sistema{8k ≡13 125k ≡21 a.

(36)

ammette soluzione.

Soluzione. Per risolvere la prima equazione del sistema dobbiamo calcolare le potenze di [8]13. Abbia-mo:

[8]213 = [12]13, [8]313 = [5]13, [8]413 = [1]13.

La soluzione della prima equazione della (36) e quindi k ≡4 2. Per risolvere la seconda equazionecalcoliamo le potenze di [5]21. Abbiamo:

[5]221 = [4]21, [5]321 = [20]21, [5]421 = [16]21 [5]521 = [17]21, [5]621 = [1]21.

La soluzione della seconda equazione della (36) e quindi della forma k ≡6 b dove b dipende dalla classedi a (ad esempio se a ∈ [4]21, b = 2, se a ∈ [20]21, b = 3, ecc.). Affinche l’equazione k ≡6 b abbiasoluzioni in comune con k ≡4 2 e necessario che MCD(6, 4) = 2 divida b − 2 e quindi b deve esserepari. Quindi affinche il sistema (36) sia risolubile deve essere a ∈ {[4]21 ∪ [16]21 ∪ [1]21}. 2

31

5 Applicazioni alla crittografia

La crittografia e quella disciplina a cavallo fra la matematica e l’informatica che studia le tecniche pertrasmettere informazioni in maniera “segreta”. L’obiettivo e quello di assicurarsi che solo il legittimodestinatario possa ricostruire il significato del messaggio e che esso sia incomprensibile per una personanon autorizzata che eventualmente intercetti il messaggio. E chiaro quindi che le tecniche di crittografiasono utilizzate tutte le volte in cui informazioni riservate devono essere trasmesse attraverso canali nonsicuri. Fino ad una trentina di anni fa, la crittografia era usata prevalentemente in ambito diplomaticoe militare. Con l’avvento dell’informatica e delle reti di calcolatori la crittografia e entrata a fare partedella vita di ogni giorno di ognuno di noi. Ogni volta che inseriamo una password, usiamo comandicome ssh, o visitiamo una pagina la cui URL inizia per https, stiamo facendo uso della crittografia.

5.1 Il cifrario di Augusto

In questa sezione mostriamo un semplice algoritmo di crittografia che pare risalga all’epoca dell’im-peratore Augusto. Supponiamo ad esempio di voler trasmettere il messaggio ALESSANDRIA. Comeprima cosa trasformiamo il messaggio in una sequenza di numeri secondo la trasformazione spazio→ 0,A → 1, B → 2, . . . , Z → 26. Scegliamo poi una chiave ad esempio la parola CIAO. Scriviamo poila codifica numerica del messaggio e sotto di essa la codifica numerica della chiave ripetuta piu voltein modo da ottenere tanti valori quanti quelli presenti nel messaggio. Nel nostro esempio, dato che lacodifica numerica di CIAO e [3, 9, 1, 15], abbiamo

A L E S S A N D R I A

1 12 5 19 19 1 14 4 18 9 1

3 9 1 15 3 9 1 15 3 9 1

Il messaggio cifrato e costituito dalla somma modulo 27 dei valori contenuti nelle ultime due righedella tabella. Nel nostro caso il messaggio cifrato e quindi [4, 21, 6, 7, 22, 10, 15, 19, 21, 18, 2].

Nel seguito indicheremo questo algoritmo di crittografia con l’espressione “cifrario di Augusto, conchiave CIAO”. Tale espressione mette in risalto che l’algoritmo e composto da un metodo generale(il metodo di Augusto di sommare modulo 27) e dalla chiave CIAO. Evidentemente per avere unamaggiore sicurezza e consigliabile tenere segreti sia il metodo utilizzato che la chiave. Non sempre peroquesto e possibile: ad esempio non e ragionevole pensare che un sito web di commercio elettronico possamantenere un metodo diverso di crittografia per ogni possibile utente. Nelle applicazioni informatichecapita spesso quindi che il metodo usato e noto a tutti e che la segretezza dei messaggi e affidatacompletamente alla segretezza della chiave. Questo fatto ha comportato lo sviluppo di sofisticatetecniche di crittografia al fine di rendere sicure le trasmissioni.

5.2 Algoritmi efficienti e inefficienti

Un concetto fondamentale per la moderna crittografia e la distinzione fra algoritmi efficienti e ineffi-cienti. Nel seguito daremo solo una definizione informale ma sufficiente per illustrare il funzionamentodei protocolli di crittografia che saranno visti nel seguito.

Definizione 4 Un algoritmo si dice efficiente se risolve un problema eseguendo un numero di opera-zioni aritmetiche che e al massimo proporzionale al logaritmo, o a una potenza del logaritmo, di unodei dati di input. 2

Per operazioni aritmetiche si intendono somma, sottrazione e prodotto—sia tra interi che tra classi diresto—e il calcolo della divisione euclidea tra due interi. Come detto la definizione data e informalee quindi non e immediato afferrarne il significato. Per chiarirsi le idee e opportuno studiare conattenzione i seguenti esempi.

32 5 APPLICAZIONI ALLA CRITTOGRAFIA

Esempio 26 Consideriamo il problema di calcolare [t]mn . I dati di input sono quindi i tre numeriinteri n, t, e m. L’algoritmo veloce di elevamento a potenza visto nella Sezione 3.3 e un algoritmoefficiente in quanto esegue ≈ 2 log2m operazioni. Il numero di operazioni e quindi proporzionale, concostante di proporzionalita 2, al logaritmo di uno dei dati di input (l’esponente m). 2

Esempio 27 L’algoritmo tradizionale per il calcolo di [t]mn che esegue m − 1 moltiplicazioni [t]n ×[t]n× · · ·× [t]n, non e efficiente. Infatti il numero di operazioni non e proporzionale ad una potenza dilogm: per m grande infatti la quantita m − 1 e molto piu grande di una qualsiasi potenza di log2m

(questo lo avete imparato ad analisi). 2

Osservazione 11 Per capire il motivo per cui introduciamo la distinzione fra algoritmi efficienti e inef-ficienti consideriamo il problema di calcolare [7]1030

1050 . Supponiamo di avere a disposizione un computerin grado di eseguire il prodotto fra due elementi in Z1050 in un milionesimo di secondo. Se utilizziamol’algoritmo veloce dobbiamo eseguire ≈ 2 log2 1030 = 60 log2 10 ≈ 200 operazioni che richiedono in to-tale circa 0.2 millesimi di secondo. L’algoritmo tradizionale esegue 1030−1 moltiplicazioni impiegando≈ 1024 secondi che corrispondono a ≈ 300000 miliardi di anni (ricordiamo che si stima che l’universoesista da “solo” 14 miliardi di anni). La conclusione da tenere a mente e che un algoritmo efficientee in grado di risolvere in pochi secondi problemi che sono in pratica irrisolubili con un algoritmo nonefficiente. 2

Esempio 28 L’algoritmo di Euclide esteso e un algoritmo efficiente in quanto e possibile dimostrareche esegue al piu 2 log max(a, b) passi. In altre parole, la sequenza dei resti e lunga al piu 2 log max(a, b):entro tale numero di passi si ottiene sicuramente un resto 0. Dato che ad ogni passo vengono eseguite 5operazioni (una per calcolare quoziente e resto, e quattro per aggiornare i coefficienti s e t), il numerodi operazioni complessive e proporzionale al logaritmo del piu grande tra a e b. 2

Esempio 29 L’algoritmo che stabilisce se un intero n e primo provando a dividerlo per tutti i numerifino a

√n non e efficiente in quanto se n e primo esegue un numero di operazioni (divisioni) pari

appunto a√n (e voi avete studiato al corso di analisi che per n grande

√n e molto piu grande di una

qualsiasi potenza di log2 n). Notiamo che se n e, ad esempio, multiplo di 3 riusciamo ad accorgerciche non e primo con poche operazioni: a noi pero interessa il numero di operazioni svolte nei casi piudifficili (o sfortunati). Se per alcuni input l’algoritmo esegue un numero di operazioni molto elevatolo classifichiamo inefficiente anche se per altri input l’algoritmo e molto veloce. 2

Osservazione 12 L’algoritmo considerato nell’esempio precedente non e l’unico algoritmo esistenteper stabilire se un intero e primo o composto. Nella Sezione 6.4 vedremo il test di primalita di Miller-Rabin che e un algoritmo efficiente per questo problema in quanto esegue un numero di operazioniproporzionale a log2 n. 2

Strettamente correlato al problema di stabilire se un numero n e primo, c’e il problema di calcolarela fattorizzazione di n. Questo secondo problema e piu difficile del primo: infatti se di un numeroriusciamo a calcolare la fattorizzazione e immediato poi stabilire se esso e primo oppure no. E im-portante sottolineare che non vale il viceversa: il sapere che un numero non e primo non ci aiuta adeterminare la sua scomposizione in fattori.

Osservazione 13 Attualmente non si conoscono algoritmi efficienti per il calcolo della fattorizzazionedi un numero. Di conseguenza ci troviamo nella seguente situazione: dato un numero di ≈ 200 cifredecimali utilizzando il test di primalita di Miller-Rabin (vedi Sezione 6.4) un moderno PC puo stabilirein pochi secondi se esso e primo oppure no; ma lo stesso PC impiegherebbe decine di anni per calcolarnela fattorizzazione. Come vedremo, il fatto che sia “facile” stabilire se un numero e primo e che sia“difficile” calcolare la fattorizzazione e alla base di diversi risultati di crittografia. 2

Il motivo per cui ci interessa la distinzione fra algoritmi efficienti e inefficienti e che nel seguito mo-streremo come costruire dei sistemi di crittografia nei quali i “buoni” possono codificare e decodificarei messaggi utilizzando algoritmi efficienti mentre i “cattivi” per decodificare un messaggio non direttoa loro si trovano a dover risolvere un problema per il quale non si conoscono algoritmi efficienti. Unesempio di questi metodi e dato dal protocollo di Diffie-Hellman descritto nella prossima sezione.

5.3 Il protocollo di Diffie-Hellman 33

5.3 Il protocollo di Diffie-Hellman

Consideriamo ancora il problema di un sito web di commercio elettronico che deve gestire transazioniriservate con migliaia di utenti ogni giorno. Possiamo pensare che tutte le transazioni siano crittogra-fate con lo stesso metodo, ma e chiaramente necessario che per ogni utente venga utilizzata una chiavediversa che deve essere nota solamente all’utente e al sito stesso. Abbiamo pero il problema di comeil sito e il singolo utente si possano scambiare una chiave segreta. Lo scambio infatti deve avvenirein tempi brevi e utilizzando Internet che non e un canale di comunicazione sicuro nel senso che i datitrasmessi posso essere intercettati e letti durante il tragitto.

Nel 1976 Diffie e Hellman hanno proposto un metodo che permette a due persone (o computer) diconcordare una chiave segreta utilizzando un canale non sicuro. Il metodo di Diffie e Hellman sfrutta ilfatto che non si conoscono algoritmi efficienti per il calcolo del logaritmo discreto (vedere Sezione 4.3).Indichiamo con Alice e Bobo due persone che desiderano concordare una chiave segreta. Come primacosa Alice calcola un primo p e un elemento g ∈ Z∗

p di ordine p− 1 e li comunica a Bobo (si dimostrache un tale elemento g esiste sempre; il suo calcolo in maniera efficiente richiede un po’ di Teoria deiNumeri avanzata).

Successivamente Alice sceglie un intero positivo a < p − 1 e comunica a Bobo il valore ka =(ga mod p). Analogamente Bobo sceglie un intero positivo b < p − 1 e comunica ad Alice il valorekb = (gb mod p). A questo punto Alice e Bobo usano il valore k = (gab mod p) come chiave segreta.Osserviamo che Alice non conosce b ma puo calcolare k con la formula k = (kab mod p). AnalogamenteBobo non conosce a ma puo calcolare k con la formula k = (kba mod p). Notiamo che Alice e Bobodevono solamente calcolare degli elevamenti a potenza e possono farlo con l’algoritmo veloce descrittonella Sezione 3.3.

Supponiamo ora che Carlo abbia intercettato tutte le comunicazioni fra Alice e Bobo. Carlo conoscei valori g, p, ka, e kb, ma non e in grado di calcolare direttamente k. Per calcolare k Carlo ha bisogno diricavare a o b ma per fare questo deve risolvere un problema di logaritmo discreto in Z∗

p cioe calcolarequal e l’intero a tale che ga = ka. Attualmente non si conoscono algoritmi efficienti per il calcolo dellogaritmo discreto in Z∗

p: se p ha un centinaio di cifre tale calcolo richiede anni di tempo macchina.Alice e Bobo possono quindi tranquillamente scambiarsi messaggi riservati utilizzando la chiave k.Per maggiore sicurezza nelle applicazioni informatiche le chiavi segrete possono essere cambiate piuvolte durante una sessione di comunicazione (il procedimento e gestito dai computer e l’utente non siaccorge di nulla).

Osservazione 14 Abbiamo visto che il protocollo di Diffie-Hellman e sicuro quando il primo p e“grande”. E lecito chiedersi come possa fare Alice a generare un numero primo con, ad esempio,duecento cifre. Il procedimento e il seguente: si prende un numero n qualsiasi di 200 cifre, e si applicaun test di primalita per verificare se e primo. Se n e primo abbiamo finito, altrimenti applichiamoil test di primalita a n + 1, n + 2, etc. fino a quando non troviamo un numero primo. Questoprocedimento e efficiente in quanto 1) esistono algoritmi efficienti per stabilire se un numero e primo(vedere Osservazione 12) e 2) la distanza fra due primi successivi e generalmente “piccola”: piuprecisamente partendo dall’intero n il procedimento che abbiamo visto trova un numero primo dopo≈ log2 n tentativi. 2

Concludiamo osservando che nessuno hai mai dimostrato che non possono esistere algoritmi effi-cienti per il calcolo del logaritmo discreto. Rimane quindi aperta la possibilita che un giorno qualcunotrovi algoritmo efficiente per questo problema: in tal caso il protocollo di Diffie-Hellman non potrebbepiu essere considerato sicuro.

5.4 Il protocollo RSA

Il protocollo RSA e stato introdotto nel 1977 dai ricercatori del MIT Ronald Rivest, Adi Shamir eLeonard Adleman ed e attualmente il piu famoso sistema di crittografia a chiave pubblica (vedremo nelseguito il significato di questa espressione). La sicurezza del protocollo RSA e basata sostanzialmentesul fatto che non si conoscono algoritmi efficienti per il problema della fattorizzazione.

34 5 APPLICAZIONI ALLA CRITTOGRAFIA

Supponiamo che Alice voglia ricevere dei messaggi da Bobo ma che tutte le loro comunicazionipossano essere intercettate. Per garantire la riservatezza dei messaggi diretti a lei Alice puo utilizzareil protocollo RSA che consiste nei seguenti passi:

1. Alice genera due primi “grandi” p e q, ne calcola il prodotto n e calcola ϕ(n) = (p− 1)(q − 1).

2. Alice sceglie un intero e, con 1 < e < ϕ(n) tale che MCD(e, ϕ(n)) = 1.

3. Alice rende pubblica (diciamo sul proprio sito web) la coppia di interi (n, e) che costituisce lasua chiave pubblica.

4. Utilizzando l’algoritmo di Euclide esteso Alice calcola d tale che de ≡ϕ(n) 1 (quindi d e l’inversomoltiplicativo di e modulo ϕ(n)). La coppia (n, d) costituisce la chiave privata di Alice.

Per spedire messaggi ad Alice, Bobo per prima cosa recupera la chiave pubblica (n, e) e trasformail suo messaggio in una serie di interi m1,m2, . . . ,mk con 0 ≤ mi < n per i = 1, . . . , k (i messaggipossono essere trasformati in numeri utilizzando lo schema descritto nella Sezione 5.1 eventualmenteconsiderando blocchi di lettere invece che lettere singole). Successivamente, per i = 1, . . . , k, Bobocalcola ci = (me

i mod n) e spedisce la sequenza di interi c1, c2, . . . , ck. Alice decodifica il messaggiocalcolando i valori xi = (cdi mod n) per i = 1, . . . , k.

Esempio 30 Supponiamo che Alice scelga p = 31, q = 43 da cui deriva n = 1333 e ϕ(n) = 1260.Alice sceglie poi e = 17: la chiave pubblica risultera quindi essere la coppia (n = 1333, e = 17).Successivamente, utilizzando l’algoritmo di Euclide esteso, Alice calcola l’inverso moltiplicativo di 17modulo 1260 che risulta essere d = 593. La chiave privata di Alice sara quindi la coppia (n = 1333, d =593). Supponiamo che Bobo debba inviare il valore 456. Usando la chiave pubblica di Alice, Bobocalcola 45617 mod 1333 = 880. Il valore 880 e il messaggio crittografato che viene trasmesso da Boboad Alice. Alice usa la sua chiave privata e calcola 880593 mod 1333 = 456 riottenendo cosı il valoreoriginale. 2

Il seguente teorema dimostra che il meccanismo di decodifica ricostruisce esattamente il messaggiooriginale.

Teorema 15 Siano n, e, d definiti come sopra. Sia m tale che 0 ≤ m < n e siano

c = me mod n, x = cd mod n.

Allora si ha x = m.

Dimostrazione: Per semplicita mostriamo il teorema solo nel caso in cui MCD(m,n) = 1. Perprima cosa osserviamo che essendo m e x entrambi compresi fra 0 e n− 1 e sufficiente dimostrare chex ≡n m. Abbiamo

x ≡n cd ≡n (me)d ≡n med

basta quindi dimostrare che med ≡n m. Dato che MCD(m,n) = 1, l’Osservazione 10 ci dice chel’esponente di m puo essere ridotto modulo ϕ(n). Essendo ed ≡ϕ(n) 1 possiamo concludere che

med ≡n med mod ϕ(n) ≡n m1 ≡n m.

2

Osservazione 15 E importante notare che una volta che Alice ha reso pubblica la chiave (n, e)chiunque, non solo Bobo, puo inviare messaggi cifrati ad Alice. L’espressione “sistemi di crittografiaa chiave pubblica” indica il fatto che la segretezza dipende da due chiavi: una pubblica e una privata.Il fatto che sia possibile divulgare la chiave pubblica fa sı che Alice possa ricevere messaggi privatida chiunque senza che ci sia stato in precedenza uno scambio di informazioni. Si confronti questasituazione con il cifrario di Augusto (Sezione 5.1) nel quale esiste solamente una chiave privata (laparola CIAO nell’esempio) che deve essere tenuta segreta e deve essere stata stabilita in anticipo trai partecipanti. 2

5.4 Il protocollo RSA 35

Il Teorema 15 mostra che il protocollo RSA funziona nel senso che Alice e in grado di ricostruirei messaggi diretti a lei. Ma chi ci assicura che il sistema sia sicuro, cioe che solo Alice sia in grado diricostruire questi messaggi? Supponiamo che Carlo intercetti la sequenza di interi c1, . . . , ck spediti daBobo ad Alice. Dato che la chiave pubblica (n, e) di Alice e disponibile, Carlo puo in teoria ricostruireil messaggio procedendo come segue: 1) calcola la fattorizzazione di n ottenendo cosı i due primip e q, 2) calcola ϕ(n) = (p − 1)(q − 1), 3) calcola d applicando l’algoritmo di Euclide esteso allacoppia (e, ϕ(n)). A questo punto Carlo puo ottenere il messaggio originale m1, . . . ,mk procedendonello stesso modo di Alice, cioe elevando alla d modulo n. Il procedimento appena descritto nonpuo pero essere utilizzato in pratica da Carlo perche non sono noti algoritmi efficienti per il calcolodella fattorizzazione di un numero. Se p e q (e di conseguenza n) sono “grandi”, ad esempio hannocentinaia di cifre, utilizzando questo metodo Carlo impiegherebbe decide di anni per decodificare imessaggi diretti ad Alice1. Osserviamo che possiamo utilizzare numeri primi p e q “grandi” in quantole operazioni di codifica e decodifica consistono semplicemente in elevamenti a potenza modulo n

che, anche quando l’esponente e “grande”, possono essere eseguiti velocemente utilizzando l’algoritmodescritto nella Sezione 3.3. Per trovare due primi “grandi” con in quali generare le chiavi pubblica eprivata Alice puo utilizzare il procedimento descritto nell’Osservazione 14.

Osservazione 16 Ripetiamo il concetto gia espresso nel caso del protocollo di Diffie-Hellman: nessunoha dimostrato che non possono esistere algoritmi efficienti per il problema della fattorizzazione. Seun giorno venisse scoperto un algoritmo efficiente il metodo RSA non potrebbe essere piu consideratosicuro2. 2

E importante sottolineare che anche se si riuscisse a dimostrare che con i computer attuali fatto-rizzare un numero di un centinaio di cifre richiede necessariamente decine di anni, il metodo RSA nonpotrebbe ancora essere considerato completamente sicuro. In linea di principio infatti Carlo potrebberiuscire a decodificare i messaggi diretti ad Alice usando un metodo che non richieda di fattorizzare n.Ad esempio, se si trovasse un algoritmo per calcolare ϕ(n) senza conoscere p e q allora si potrebberodecifrare i messaggi senza bisogno di fattorizzare n. E quindi piu esatto dire che la sicurezza del siste-ma RSA e basata sul fatto che, allo stato attuale delle conoscenze, non sono noti algoritmi efficientiper ricavare m1, . . . ,mk dati c1, . . . , ck e la chiave pubblica (n, e).

Concludiamo osservando che il metodo descritto garantisce la riservatezza solamente dei messaggiindirizzati ad Alice. Se Alice volesse mandare un messaggio riservato a Bobo, sara lui a dover calcolaree pubblicare una propria chiave pubblica. Bobo manterra anche la corrispondente chiave segreta chedovra usare per decodificare i messaggi diretti a lui.

Esercizio 35 In un sistema di crittografia RSA, la chiave pubblica consiste nel modulo n = 4762169e dell’esponente di codifica e = 593. Inoltre scoprite che la somma dei due primi che costituiscono ilmodulo e 4410. Calcolare l’esponente di decodifica d.

Soluzione. Indicando con p e q i due primi che compongono il modulo abbiamo p+ q = 4410. Essendoϕ(n) = (p− 1)(q − 1) = n− (p+ q) + 1 abbiamo ϕ(n) = 4762169− 4410 + 1 = 4757760. L’esponentedi decodifica si ottiene applicando l’algoritmo di Euclide esteso alla coppia (4757760, 593) che fornisceil risultato d = 393137. 2

1Sottolineiamo che anche un algoritmo molto inefficiente e in grado di fattorizzare in pochi secondi un numero piccolo.Per questo motivo, con i numeri utilizzati nell’Esempio 30 il metodo RSA non e sicuro.

2In realta algoritmi efficienti per il problema della fattorizzazione (e del logaritmo discreto) esistono gia, ma richiedonol’uso di computer quantistici. Computer quantistici sono gia stati realizzati, ma per problemi tecnici hanno una quantitadi memoria molto limitata. Attualmente il numero piu grande che si e riusciti a fattorizzare con un computer quantisticoe 15, ma le cose potrebbero cambiare in pochi anni. . . .

36 6 RADICI QUADRATE MODULO N E TEST DI MILLER-RABIN

6 Radici quadrate modulo n e test di Miller-Rabin

Sappiamo che ogni numero reale a > 0 possiede esattamente due radici quadrate ±√a. In questo

capitolo studieremo le proprieta delle radici quadrate in Zn. Vedremo poi una inaspettata applicazionedelle radici quadrate in Zn in crittografia. Tratteremo infine il test di primalita di Miller Rabin che eanch’esso basato sulle proprieta delle radici quadrate in Zn.

6.1 Radici quadrate modulo p

Cominciamo il nostro studio, dal caso particolare degli insiemi Zp con p primo.

Teorema 16 Se p e un numero primo l’equazione x2 = [a]p in Zp ha al piu due soluzioni x = [u]p ex = [−u]p = [p− u]p.

Dimostrazione: Supponiamo che esistano due interi u, v tali che

u2 ≡ a mod p e v2 ≡ a mod p.

Abbiamo allora u2− v2 ≡p 0 da cui (u− v)(u+ v) ≡p 0. Dovendo essere (u− v)(u+ v) un multiplo dip, abbiamo che p deve dividere (u− v) oppure (u+ v). Nel primo caso abbiamo u ≡p v, nel secondou ≡p −v. 2

Abbiamo quindi che ogni [a]p ammette al massimo due radici quadrate. Ci chiediamo ora quantielementi di Zp abbiano almeno una radice quadrata. Consideriamo come esempio il caso p = 7.Abbiamo che i quadrati degli elementi di Z7 sono [0]27 = [0]7, [1]27 = [1]7, [2]27 = [4]7, [3]27 = [2]7,[4]27 = [2]7, [5]27 = [4]7, e [6]27 = [1]7. Di conseguenza, abbiamo che [0]7 ha una sola radice quadrata,[1]7, [4]7, [5]7 hanno due radici quadrate, mentre [2]7, [3]7, [6]7 non hanno radici quadrate. Estendendoquesto ragionamento ad un primo p qualsiasi osserviamo che la classe [0]p ha un’unica radice quadrata,(p − 1)/2 classi hanno esattamente due radici quadrate (ricordare il Teorema 16) e di conseguenza(p− 1)/2 classi non hanno radici quadrate.

Il seguente teorema ci permette di stabilire facilmente quali elementi di Zp hanno una radicequadrata.

Teorema 17 Sia p un primo dispari. Se [a]p 6= [0]p, [a]p ha due radici quadrate se e solo se

ap−12 ≡ 1 mod p.

Dimostrazione: Supponiamo che sia [a]p = [b]2p per un qualche [b]p ∈ Zp. Allora abbiamo

[a]p−12

p = [b]p−1p = [1]p

per il teorema di Eulero. Viceversa sia a tale che ap−12 ≡ 1 mod p. Come abbiamo accennato nella

Sezione 5.3, se p e primo esiste un elemento g ∈ Z∗p che ha ordine p − 1 e che quindi ha la proprieta

che ogni elemento di Z∗p e una potenza di g. In particolare avremo che [a]p = gk per un qualche intero

k, con 1 ≤ k < p− 1. Dall’ipotesi su [a]p segue che

[1]p = [a]p−12

p = gkp−12 .

Dato che [g]p ha ordine p − 1 abbiamo che k p−12 deve essere un multiplo di p − 1 e di conseguenza

k deve essere pari. Abbiamo allora che [a]p ha come radici quadrate ±g(k/2) (ricordiamo infatti che[a]p = gk). 2

Esempio 31 Fissiamo p = 11. Abbiamo 5(p−1)/2 = 55 = 3125. Essendo 3125 ≡11 1, [5]11 ha dueradici quadrate (che sono infatti ±[4]11). Abbiamo invece 25 = 32. Dato che 32 ≡11 −1 concludiamoche [2]11 non ha radici quadrate. 2

6.1 Radici quadrate modulo p 37

Osservazione 17 Sia [c]p = [a]p−12

p mod p. Se [a]p non ha radici quadrate sappiamo che [c]p 6= [1]p.Mostriamo che in questo caso deve essere [c]p = [−1]p. Infatti, dato che [c]2p = [a]p−1

p = [1]p (per ilTeorema di Eulero) abbiamo che [c]p e una radice quadrata di [1]p. Per il Teorema 16 [1]p ha comeuniche radici quadrate ±[1]p e dato che [c]p 6= [1]p deve essere [c]p = [−1]p. 2

Supponiamo ora che, grazie al Teorema 17, abbiamo stabilito che una certa classe [a]p ha radiciquadrate. Come possiamo fare per trovarle? Nel caso in cui il primo p sia tale che p ≡4 3 il calcolo esorprendentemente facile.

Lemma 4 Se p ≡4 3 e [a]p ha radici quadrate, allora tali radici sono ±[a]p+14

p .

Dimostrazione: Osserviamo che se p ≡4 3 risulta che p + 1 e un multiplo di 4 e di conseguenzal’esponente p+1

4 e un intero. Inoltre ricordiamo che [a]p ha radici quadrate solo se ap−12 ≡p 1. Abbiamo(

±[a]p+14

p

)2

= [a]p+12

p = [a]1+ p−1

2p = [a]p · [a]

p−12

p = [a]p.

Di conseguenza ±[a]p+14

p sono entrambe radici quadrate di [a]p. 2

Esempio 32 Fissiamo p = 19 e a = [11]19. Dato che [11]919 = [1]19 abbiamo che [11]19 ha radiciquadrate. Applichiamo il Lemma 4 e calcoliamo [11](19+1)/4

19 = [11]519 = [7]19. Le radici sono quindi±[7]19 cioe [7]19 e [12]19. 2

Nel caso in cui sia p ≡4 1 il calcolo delle radici quadrate e piu complicato. Mostriamo ora ilprocedimento di calcolo omettendo la dimostrazione della correttezza (non dimostriamo cioe che ilvalore ottenuto e sempre la radice quadrata cercata). Dato [a]p ∈ Z∗

p tale che [a](p−1)/2p = [1]p, con

p ≡4 1, per trovare una radice quadrata di [a]p se puo procedere come segue.

1. Osserviamo che p − 1 e sicuramente pari. Raccogliamo tutte le potenze di 2 presenti in p − 1,scrivendo p− 1 = 2αs con s dispari (avremo sicuramente α ≥ 2 perche p− 1 e multiplo di 4).

2. Consideriamo gli elementi [2]p, [3]p, [4]p, . . . e li eleviamo alla potenza (p − 1)/2. Non appenatroviamo un elemento c tale che c(p−1)/2 = [−1]p, poniamo b = cs.

3. Poniamo r0 = as+12 . Dato che s e dispari s+ 1 e pari e r0 e ben definito. Successivamente, con

l’algoritmo di Euclide esteso, calcoliamo d = a−1 (quindi d e l’inverso moltiplicativo di a in Z∗p).

4. Per i = 0, 1, . . . , α − 2, usiamo ri per calcolare un nuovo elemento ri+1 ∈ Z∗p come segue. Sia

wi = (r2i d)2α−i−2

. E possibile dimostrare che wi puo essere uguale solamente a [±1]p. Se wi = [1]pponiamo ri+1 = ri, se wi = [−1]p poniamo ri+1 = rib

2i .

5. Una radice quadrata di a e data dall’elemento rα−1 (cioe dall’ultimo degli elementi ri calcolatial passo 4).

Esempio 33 Supponiamo di voler calcolare le radici quadrate di [2]41. Essendo 40 = 235 abbiamoα = 3 e s = 5. Elevando alla potenza (41− 1)/2 = 20 gli elementi [2]41, [3]41, . . ., il primo elemento lacui potenza risulta essere uguale a [−1]41 e [3]41. Abbiamo quindi c = [3]41 e b = c5 = [38]41. Poniamopoi r0 = [2](5+1)/2

41 = [2]341 = [8]41. Infine calcoliamo d = [2]−141 = [21]41.

A questo punto dobbiamo eseguire il passo 4 della procedura vista sopra e calcolare gli elementir0, r1, r2. Essendo α = 3 abbiamo che la radice quadrata sara l’elemento r2. Abbiamo:

w0 = (r20d)2α−2

= ([8]241[21]41)2 = [32]241 = [−1]41

che implica r1 = r0b20

= [8]41[38]41 = [17]41. Abbiamo poi

w1 = (r21d)2α−3

= ([17]241[21]41)20

= [1]41

che implica r2 = r1 = [17]41. Le radici quadrate di [2]41 sono quindi ±[17]41. Abbiamo infatti:172 = 289 = 2 + 41 · 7. 2


Esempio 34 Supponiamo di voler calcolare le radici quadrate di [7]1201. Essendo 1200 = 2475 abbia-mo α = 4 e s = 75. Elevando alla potenza (41 − 1)/2 = 600 gli elementi [2]1201, [3]1201, . . ., il primoelemento la cui potenza risulta essere uguale a [−1]1201 e [11]1201. Abbiamo quindi c = [11]1201

e b = c75 = [473]1201. Poniamo poi r0 = [7](75+1)/21201 = [7]38

1201 = [1152]1201. Infine calcoliamod = [7]−1

1201 = [858]1201.A questo punto dobbiamo eseguire il passo 4 della procedura vista sopra e calcolare gli elementi

r0, r1, r2, r3. Essendo α = 4 abbiamo che la radice quadrata sara l’elemento r4. Abbiamo:

w0 = (r20d)2α−2

= ([1152]21201[858]1201)22

= [343]41201 = [−1]1201


= [1152]1201[473]1201 = [843]1201. Abbiamo poi

w1 = (r21d)2α−3

= ([843]21201[858]1201)21

= [1152]21201 = [−1]1201

che implica r2 = r1b2 = [909]1201. Abbiamo infine

w2 = (r22d)2α−4

= ([909]21201[858]1201)20

= [−1]1201


= [1097]1201. Le radici quadrate di [7]1201 sono quindi ±[1097]1201. Abbiamoinfatti: 10972 = 1203409 ≡1201 7. 2

6.2 Radici quadrate modulo n = pq

I metodi che abbiamo visto nella sezione precedente costituiscono un algoritmo efficiente (nel sensodella Definizione 4) per il calcolo delle radici quadrate in Zp, con p primo. Tali metodi permettonodi calcolare radici quadrate in pochi secondi (con un computer) anche quando il modulo ha centinaiadi cifre. E naturale a questo punto chiedersi cosa possiamo dire sul problema del calcolo delle radicequadrate in Zn quando n non e un numero primo. In seguito considereremo il caso in cui n = pq e ilprodotto di due numeri primi in quanto questo caso e il piu semplice da trattare e importante per leapplicazioni.

Cominciamo vedendo cosa succede per n = 15. Abbiamo

[0]215 = [0]15, [1]215 = [1]15, [2]215 = [4]15, [3]215 = [9]15, [4]215 = [16]15

[5]215 = [10]15, [6]215 = [6]15, [7]215 = [4]15, [8]215 = [4]15, [9]215 = [6]15

[10]215 = [10]15, [11]215 = [16]15, [12]215 = [9]15, [13]215 = [4]15, [14]215 = [1]15.

Osserviamo che [4]15 ha quattro radici quadrate; possiamo quindi concludere che se il modulo non e unnumero primo il Teorema 16 non e valido. Il seguente teorema mostra che quando n = pq e [a]n ∈ Z∗

n,allora le radici quadrate di [a]n in Zn sono strettamente correlate alla radici quadrate di [a]p in Zp edi [a]q in Zq.

Teorema 18 Sia n = pq con p e q primi dispari, e sia a tale che MCD(a, n) = 1. La classe [a]n haradici quadrate in Zn se e solo se [a]p ha radici quadrate in Zp e [a]q ha radici quadrate in Zq. Inoltre,se [a]n ha una radice quadrata in Zn allora ne ha esattamente quattro.

Dimostrazione: Affinche sia [b]2n = [a]n deve essere b2 − a ≡n 0. Ne segue che b2 − a deve esseremultiplo sia di p che di q. Dal fatto che b2 − a ≡p 0 ne segue che [b]2p = [a]p e quindi [a]p ha radiciquadrate in Zp. Analogamente, dal fatto che b2−a ≡q 0 ne segue che [b]2q = [a]q e quindi [a]p ha radiciquadrate in Zp.

Supponiamo ora che ±[s]p siano le radici quadrate di [a]p in Zp e che ±[t]q siano le radici quadratedi [a]q in Zq. Risolvendo i quattro sistemi di congruenze:{

x ≡p +sx ≡q +t

{y ≡p +sy ≡q −t

{u ≡p −su ≡q +t

{v ≡p −sv ≡q −t (37)

6.2 Radici quadrate modulo n = pq 39

otteniamo quattro classi di resto [x]n, [y]n, [u]n, [v]n che risultano essere radici quadrate di [a]n in Zn.Considerando ad esempio [u]n (ma per gli altri tre valori il discorso e analogo) abbiamo

u2 ≡p (−s)2 ≡p a, e u2 ≡q (t)2 ≡q a.

Ne segue che u2 − a e multiplo sia di p che di q e di conseguenza u2 − a ≡n 0.Concludiamo osservando che essendo p e q due numeri primi distinti, il Teorema cinese del resto

assicura che le soluzioni dei quattro sistemi (37) sono classi di congruenza modulo n = pq. 2

Esempio 35 Sia n = 55. Vogliamo trovare, se esistono, le radici di [14]55. Abbiamo che 14 mod 5 = 4;le radici di [4]5 sono ovviamente ±[2]5. Abbiamo poi 14 mod 11 = 3. Per il Teorema 17, la classe [3]11

ha radici quadrate in quanto 35 = 243 ≡11 1. Dato che 11 ≡4 3, per calcolare le radici quadrate di[3]11 possiamo usare il Lemma 4 che ci dice che le radici sono ±([3]311) = ±[5]11.

Possiamo quindi calcolare le radici di [14]55 risolvendo i sistemi di congruenze:{x ≡5 2x ≡11 5

{y ≡5 2y ≡11 −5

{u ≡5 −2u ≡11 5

{v ≡5 −2v ≡11 −5

che forniscono le quattro radici quadrate [27]55, [17]55, [38]55, [28]55. Le radici quadrate di [14]55 sonoquindi ±[17]55, e ±[27]55.

Supponiamo ora di voler calcolare le radici quadrate di [29]55. Abbiamo 29 mod 5 = 4 le cui radiciquadrate sono ±[2]5. Invece 29 mod 11 = 7 e [7]11 non ha radici quadrate in quanto 75 ≡11 −1.Concludiamo allora che [29]55 non ha radici quadrate in Z55. 2

Osservazione 18 Per calcolare le quattro radici quadrate di [a]n, e sufficiente risolvere soltanto iprimi due dei sistemi (37). Infatti e immediato verificare che le soluzioni del terzo e del quarto sistemasono date rispettivamente dalle soluzioni del secondo e del primo sistema cambiate di segno. Quindi,possiamo calcolare solamente le soluzioni x e y dei primi due sistemi e concludere che le radici quadratesono ±[x]n e ±[y]n. 2

Esercizio 36 Calcolare, se esistono, le radici quadrate di [271]943.

Soluzione. Per prima cosa e necessario calcolare la fattorizzazione di 943. Provando a dividerlo per3, 5, 7, 11, . . . si trova che 943 = 23 · 41. Essendo 271 mod 23 = 18 e 271 mod 41 = 25 abbiamo chele radici quadrate di [271]943 esistono se e solo se esistono le radici quadrate di [18]23 e [25]41. Per ilLemma 4 abbiamo che le radici quadrate di [18]23 sono ±([18]623) = ±[8]23. Per calcolare le radici di[25]41 possiamo utilizzare il procedimento di pagina 37 oppure piu semplicemente accorgerci che dueclassi di resto che elevate al quadrato danno [25]41 sono ±[5]41.

Per l’Osservazione 18 per calcolare le radici di [271]943 e sufficiente risolvere i due sistemi dicongruenze: {

x ≡23 8x ≡41 5

{y ≡23 8y ≡41 −5

che forniscono le quattro radici quadrate ±[169]943,±[77]943. 2

Il Teorema 18 mostra che se conosciamo la fattorizzazione n = pq e MCD(a, n) = 1, allora esisteun algoritmo efficiente (nel senso della Definizione 4) per calcolare le radici quadrate di [a]n in Zn.E possibile dimostrare che anche quando MCD(a, n) > 1, il calcolo delle radici quadrate di [a]n siriconduce al calcolo di radici quadrate in Zp e Zq (l’unica differenza e che se MCD(a, n) > 1 le radicisono al piu due). Mostriamo ora che se invece non si conosce la fattorizzazione di n, cioe i due primip e q, il calcolo delle radici quadrate in Zn e un problema “difficile”. Piu precisamente, il seguentelemma mostra che il calcolo delle radici quadrate in Zn e altrettanto difficile del problema di calcolarela fattorizzazione di n.

Lemma 5 Sia n = pq con p e q primi ma non noti. Sia [a]n tale che MCD(a, n) = 1 e sia [u]n unaradice quadrata di [a]n. Per il Teorema 37 [a]n ha esattamente quattro radici quadrate. Il calcolo diuna radice quadrata diversa da ±[u]n, e altrettanto difficile del calcolo della fattorizzazione di n.


Dimostrazione: Dobbiamo dimostrare che dalla conoscenza di una radice quadrata [v]n diversa da±[u]n siamo in grado di ricavare i due primi p e q. Dalle relazioni

u2 ≡n a e v2 ≡n a

segue che u2 − v2 ≡n 0. Abbiamo quindi che u2 − v2 = (u + v)(u − v) e un multiplo di n. Datoche [v]n 6= ±[u]n abbiamo che ne (u + v) ne (u − v) sono multipli di n. Ma allora se calcoliamoMCD(u+ v, n) il risultato non puo essere ne 1 ne n. Quindi il risultato deve essere uguale a uno deidue fattori p o q. Dalla conoscenza di u e v siamo quindi in grado di calcolare la fattorizzazione di neseguendo solamente il calcolo di un Massimo Comun Divisore. 2

Esempio 36 Supponiamo di riuscire a scoprire che le radici quadrate di [47]209 in Z209 sono ±[16]209

e ±[60]209. Possiamo allora calcolare MCD(16 + 60, 209) = MCD(76, 209) = 19 che e uno dei fattoridi 209. Dividendo 209 per 19 troviamo 11 che e il secondo fattore. 2

6.3 Lancio di una moneta al telefono

Due studenti di informatica, Alice e Bobo, si telefonano per decidere cosa fare la sera. Alice vorrebbeandare in pizzeria per guardare la partita del Pizzighettone sul megaschermo, mentre Bobo vorrebbeandare al cinema a vedere il remake di “Voglia di tenerezza”. Dopo un’accesa discussione, decidonodi affidarsi al caso e di tirare una moneta per stabilire dove andare. Il problema e che nessuno sifida dell’altro: chi deve essere a tirare la moneta e a dire all’altro qual e stato l’esito del lancio? Chinon tira la moneta infatti non ha nessun modo di verificare che l’altro riferisca onestamente l’esito dellancio. Questo problema non interessa solamente Alice e Bobo: in diversi protocolli di comunicazionee necessario che due entita possano “lanciare una moneta” e lo si vuole fare in modo che nessuno deipartecipanti possa imbrogliare.

A prima vista il problema sembra non risolubile a meno di non ricorrere a una terza entita impar-ziale e onesta. Alice e Bobo pero hanno appena passato l’esame di Matematica Discreta e sanno comerisolvere il problema sfruttando il fatto che calcolare le radici quadrate in Zn e un problema “difficile”.Alice e Bobo utilizzano il seguente procedimento:

1. Alice genera due primi “grandi” p e q, ne calcola il prodotto n e lo comunica a Bobo.

2. Bobo sceglie a caso un elemento [b]n in Z∗n, calcola [a]n = [b]2n e lo comunica ad Alice. Dato che

[a]n ∈ Z∗n, [a]n possiede quattro radici quadrate di cui Bobo ne conosce due: ±[b]n.

3. Alice, utilizzando il Teorema 37, calcola le quattro radici quadrate di [a]n. Siano esse ±[u]n e±[v]n. Due di queste radici coincidono con la coppia ±[b]n conosciuta da Bobo, ma Alice nonpuo sapere quali. Alice sceglie a caso un valore tra u e v (ad esempio u e dice a Bobo: “Le radiciin tuo possesso sono ±[u]n”.

4. Se Alice ha indovinato e lei a vincere. Se invece non ha indovinato Bobo risponde “No, le mieradici erano ±[b]n” e il vincitore e lui.

Esempio 37 Alice sceglie i due primi 13 e 17 e comunica a Bobo il loro prodotto 221. Bobo scegliea caso il valore 107 e ne calcola il quadrato modulo 221. Ottiene il valore 1072 mod 221 = 178 elo comunica ad Alice. Alice, usando la fattorizzazione di 221, calcola le quattro radici quadrate di[178]221 che sono ±[29]221 e ±[107]221. A questo punto Alice deve tentare di indovinare quali sonole due radici conosciute da Bobo: se indovina (dicendo ±[107]221) ha vinto, altrimenti (cioe se dice±[29]221) ha vinto Bobo. 2

Perche con questo metodo ogni partecipante ha effettivamente il 50% di probabilita di vincere?Il motivo e che Alice non sa nulla di quali siano le radici conosciute da Bobo e quindi ha il 50% diprobabilita di indovinare (e non ha nessuna possibilita di imbrogliare). Bobo potrebbe tentare diimbrogliare dicendo che ha vinto lui quando invece Alice aveva indovinato le radici in suo possesso.Pero per sostenere di avere vinto Bobo deve fornire una coppia di radici diverse da quelle indicate da

6.4 Il test di primalita di Miller-Rabin 41

Alice. Se Alice aveva indovinato Bobo non ha ricevuto da lei nessuna nuova informazione e quindidovrebbe calcolare in qualche modo due nuove radici. Ma per il Lemma 5 il calcolo di queste radici ealtrettanto difficile del calcolo della fattorizzazione di n e quindi si suppone che Bobo non sia in gradodi farlo velocemente (e Alice potrebbe insospettirsi se Bobo interrompesse la chiamata e si facesse vivodopo qualche decina di anni sostenendo di avere vinto lui).

6.4 Il test di primalita di Miller-Rabin

In questa sezione studieremo il funzionamento del test di Miller-Rabin che e attualmente il metodo piuusato per verificare se un numero e primo o composto. Come vedremo, questo test ha la particolaritadi poter commettere errori (cioe dichiarare che un numero e primo quando invece e composto), mala probabilita di errore puo essere resa molto piccola (piu piccola ad esempio della probabilita chemanchi la corrente sul computer che state usando per fare i conti).

Il test di Miller-Rabin e in realta un test di “non primalita” nel senso che tenta di scoprire se undato numero e composto. Il test e basato sui seguenti risultati sulle classi di resto.

Lemma 6 Sia n > 2 e sia a tale che 1 ≤ a < n. Se MCD(a, n) > 1 allora n e composto. Inoltre seMCD(a, n) = 1 ma (an−1 mod n) 6= 1 allora n e composto.

Dimostrazione: Sia d = MCD(a, n). Se d > 1 allora d e un divisore di n maggiore di 1 quindi n nonpuo essere primo. Se invece MCD(a, n) = 1 e n fosse primo, avremmo ϕ(n) = n− 1 e di conseguenzaper il Teorema di Eulero dovremmo avere an−1 ≡n 1. Quindi se (an−1 mod n) 6= 1 ne segue che n ecomposto. 2

Lemma 7 Sia n > 2 un numero dispari, e sia a tale che 1 ≤ a < n e MCD(a, n) = 1. Sia s lamassima potenza di 2 contenuta in n−1 (sicuramente s ≥ 1 in quanto n−1 e pari). Possiamo quindiscrivere n− 1 = 2st con t dispari. Consideriamo la sequenza di elementi di Z∗

n:

x0 = [a]tn, x1 = [a]2tn , x2 = [a]22tn , . . . , xs = [a]2

stn

(osserviamo che xi+1 = x2i ). Se xs 6= [1]n allora n non e primo. Inoltre, se xi 6= ±[1]n e xi+1 = [1]n

per un qualche i < s, allora n non e primo.

Dimostrazione: Dato che xs = [a]2stn = [a]n−1

n , se xs 6= [1]n allora n non puo essere primo peril Lemma 6. Supponiamo ora che xi+1 = [1]n ma xi 6= ±[1]n. Dato che xi+1 = x2

i avremmo chel’equazione x2 = [1]n in Zn avrebbe almeno tre soluzioni distinte: xi e ±[1]n. Ma allora per ilTeorema 16 n non puo essere primo. 2

Esempio 38 Sia n = 1173 e a = 7. Dato che 1172 = 22 · 293 dobbiamo calcolare la sequenza:

x0 = [7]2931173 = [28]1173, x1 = [28]21173 = [784]1173, x2 = [784]21173 = [4]1173.

Dato che x2 = [7]11721173 6= [1]1173 possiamo concludere che 1173 non e primo. 2

Esempio 39 Sia n = 561 e a = 7. Dato che 560 = 24 · 35 dobbiamo calcolare la sequenza:

x0 = [7]35561 = [241]561, x1 = [241]2561 = [298]561, x2 = [298]2561 = [166]561,

x3 = [166]2561 = [67]561, x4 = [67]2561 = [1]561.

Abbiamo quindi trovato che [67]561 e una radice quadrata di [1]561. Ma se 561 fosse primo, per ilTeorema 16 le uniche radici quadrate di [1]561 sarebbero ±[1]561 e di conseguenza possiamo concludereche 561 non e primo. 2


Esempio 40 Prendiamo ancora n = 561 ma a = 50. Calcoliamo la sequenza:

x0 = [50]35561 = [560]561, x1 = [560]2561 = [1]561, x2 = [1]2561 = [1]561,

x3 = [1]2561 = [1]561, x4 = [1]2561 = [1]561.

Essendo [560]561 = −[1]561 questo esperimento non ci fa scoprire che 561 e composto. 2

Osserviamo che l’esperimento descritto nel Lemma 7, cioe il calcolo della sequenza x0, x1, . . . , xs, cipuo soltanto dire che il numero n e composto e non potra mai dare il responso “n e un numero primo”.Inoltre, l’Esempio 40 mostra che anche quando n e composto il calcolo della sequenza x0, x1, . . . , xse l’uso del Lemma 7 non sempre riescono a “scoprire” la non primalita di n. E possibile dimostrarepero che i numeri compresi fra 1 e n− 1 che rivelano che n e composto sono piu della meta del totale.Ci limitiamo a dare l’enunciato di questo risultato in quanto la dimostrazione e piuttosto complessa.

Teorema 19 Sia n un numero dispari composto. Gli interi a compresi fra 1 e n−1 tali che applicandoil Lemma 7 alla coppia n, a ci permettono di scoprire che n e composto sono almeno (n− 1)/2. 2

Il test di Miller-Rabin e basato sul Teorema 19. Per vedere se un numero n e primo o compostovengono scelti a caso un numero elevato, per esempio 1000, di interi compresi fra 1 e n−1 (ricordiamoche questo test si applica solitamente quando n ha decine o centinaia di cifre). Per ognuno di questiinteri si esegue l’esperimento descritto nel Lemma 7. Se l’esperimento rivela che n e composto il testdi Miller-Rabin termina segnalando questo fatto. Se nessuno dei 1000 esperimenti ha rilevato che n ecomposto, il test di Miller-Rabin termina segnalando che n e primo. Cosı facendo il test potrebbe anchecommettere un errore in quanto n potrebbe essere composto e noi potremmo essere stati sfortunatinella scelta degli interi fra 1 e n − 1 non scegliendone nessuno di quelli che ci avrebbero permessodi scoprire la non primalita di n. Ma, in virtu del Teorema 19, la probabilita di essere sfortunatinella scelta per 1000 volte e minore di 2−1000. In altre parole, la probabilita di errore del Test diMiller-Rabin e minore della probabilita che alla roulette esca il rosso per 1000 lanci consecutivi. . . .

Osservazione 19 Il test puo apparire complicato concettualmente, cioe non e immediato capire ilperche il procedimento funzioni correttamente. Ma e importante riconoscere che le operazioni svoltedal test sono molto semplici in quanto consistono solamente nel calcolo di potenze in Zn. Comeconseguenza abbiamo che il test di Miller-Rabin e un algoritmo efficiente per il problema della primalitasecondo la Definizione 4. 2

43

7 Polinomi e codici di Reed-Solomon

In questo capitolo saranno descritte le principali proprieta dei polinomi e verra mostrato come i poli-nomi a coefficienti in Zp con p primo siano alla base dei codici a correzione di errore di Reed-Solomon.Questi codici permettono di correggere gli errori che si possono verificare durante la trasmissione ola memorizzazione dei dati e sono per questo usati in CD, DVD, dischi Blu-ray, linee ADSL, e per lecomunicazioni con le sonde interplanetarie (tipo Voyager per intenderci).

7.1 Terminologia sui polinomi

Dalla scuola superiore sappiamo che un polinomio e un’espressione contenente le potenze di unaquantita indeterminata. Ad esempio, p(x) = 4x3−x+ 15 e un polinomio nell’indeterminata x. Ancheespressioni che non contengono la quantita indeterminata x sono considerati particolari polinomi dettipolinomi costanti. Un esempio di polinomio costante e quindi p(x) = 3; volendo possiamo pensarlocome p(x) = 3x0 visto che per qualsiasi valore x si ha x0 = 1. Sempre dalla scuola superiore sappiamocome sommare e moltiplicare tra loro i polinomi e sappiamo che la somma e il prodotto tra polinomisoddisfano le proprieta s1-s4, p1-p3, e d1 viste nella Sezione 1.1. Ad esempio sappiamo che valea(x) + [b(x) + c(x)] = [a(x) + b(x)] + c(x) (proprieta s2), e che a(x)b(x) = b(x)a(x) (proprieta p1).L’elemento neutro rispetto all’addizione e il polinomio costante p(x) = 0, detto anche polinomio nullo.L’elemento neutro rispetto alla moltiplicazione e il polinomio costante p(x) = 1.

Un’operazione molto comune per i polinomi e la valutazione in un punto, cioe il calcolo di cosasi ottiene se sostituiamo un particolare valore α all’indeterminata x. Il valore ottenuto con questoprocedimento viene indicato con p(α). Ad esempio, se p(x) = 2x2 − 3 abbiamo p(0) = −3, p(1) = −1e p(10) = 197. Notiamo che se p e un polinomio costante non ci sono conti da fare e p(α) assumesempre lo stesso valore (e questo spiega l’uso dell’aggettivo “costante” per denotare questi polinomi).

Definizione 5 Il grado del polinomio p(x) = anxn + an−1x

n−1 + · · ·+ a2x2 + a1x+ a0 e il piu grande

intero i per cui ai 6= 0. Se tutti i coefficienti ai sono uguali a zero (quindi p(x) e il polinomio nullo)sia assume che il grado sia −1. 2

Osserviamo che in base alla definizione appena vista tutti i polinomi costanti hanno grado zero tranneil polinomio nullo3 che ha grado −1. Alla scuola superiore abbiamo visto polinomi a coefficienti interio razionali; ora che conosciamo le classi di resto possiamo definire e utilizzare polinomi i cui coefficientisono elementi di un particolare insieme Zn. Ad esempio

p(x) = [4]18 x3 + [11]18 x

2 − [7]18 x+ [2]18

e un polinomio di grado 3 a coefficienti in Z18. Notiamo che lavorando in Z18 il polinomio nullo e ilpolinomio costante p(x) = [0]18. E possibile valutare in un punto anche i polinomio a coefficienti inZn. Ad esempio se valutiamo il polinomio in Z18 appena visto in [2]18 abbiamo

p([2]18) = [4]18 · [2]318 + [11]18 · [2]218 − [7]18 · [2]18 + [2]18 = [10]18.

Naturalmente, il valore che si sostituisce alla x deve appartenere allo stesso insieme dei coefficienti:non ha alcun senso valutare un polinomio a coefficienti in Z18 in 1/3 o in [1]5.

7.2 Polinomi a coefficienti in un campo

Nel resto di questo capitolo ci restringeremo a studiare i polinomi i cui coefficienti appartengono adun campo, cioe ad un insieme in cui tutti gli elementi tranne lo zero hanno l’inverso moltiplicativo.Per questi polinomi infatti valgono alcune importanti proprieta che non sono vere quando i coefficientinon hanno questa proprieta. Per cominciare il nostro studio, diamo la definizione formale di campo.

3Non in tutti i testi di matematica il grado del polinomio nullo e definito allo stesso modo; in alcuni testi si puotrovare che il polinomio nullo ha grado −∞ o che il polinomio nullo non ha grado. La cosa non e molto importante:quello che conta e che il polinomio nullo e “diverso” dagli altri polinomi costanti.

44 7 POLINOMI E CODICI DI REED-SOLOMON

Definizione 6 Un insieme dotato delle operazioni di somma e prodotto che soddisfano alle prioprietadella Sezione 1.1 e in cui ogni elemento diverso da 0 ha l’inverso moltiplicativo e detto un campo. 2

Esempi di campi sono i numeri razionali (le frazioni) e i numeri reali (quelli che si usano nel corsodi Analisi). L’insieme dei numeri interi Z invece non e un campo in quanto solamente 1 e −1 hannol’inverso moltiplicativo: ad esempio il numero 3 non ha l’inverso moltiplicativo in Z in quanto nonesiste nessun intero a tale che 3a = 1. Per quanto riguarda gli insiemi Zn dal Corollario 1 segueimmediatamente che Zn e un campo se e soltanto se n e un numero primo. Quindi Z5 e un campoin quanto le classi [1]5, [2]5, [3]5, [4]5 hanno l’inverso moltiplicativo, mentre Z12 non e un campo inquanto la classe [6]12 non ha inverso moltiplicativo.

Il principale motivo per cui si considerano i polinomi a coefficienti in un campo, e che con essie possibile effettuare la divisione euclidea (quella che fornisce quoziente e resto per intenderci) conproprieta analoghe a quelle viste per la divisione euclidea tra interi. Abbiamo infatti che dati duepolinomi a coefficienti in un campo a(x) e b(x), con b(x) 6= 0, e possibile trovare due polinomi q(x) er(x), detti rispettivamente quoziente e resto, tali che

a(x) = b(x)q(x) + r(x), e grado(r) < grado(b).

Il procedimento per il calcolo di quoziente e resto e stato visto alle scuole superiori (ricordate?). L’ideadi base e quella di ottenere i termini del polinomio quoziente uno alla volta a partire da quello di gradomassimo. Contemporaneamente si calcola una successione di polinomi a0(x) = a(x), a1(x), a2(x), etc.di grado sempre piu piccolo. Il procedimento termina quando si ottiene un polinomio ai(x) di gradominore di grado(b). Tale ai(x) costituisce il resto della divisione mentre il quoziente e dato dallasomma dei termini ottenuti fino a quel momento. Illustriamo questo procedimento con due esempi.

Esempio 41 Consideriamo la divisione fra i due polinomi a coefficienti razionali a(x) = 3x4 + x3 −(3/2)x2 + (1/2)x+ 5 e b(x) = x+ 1. Il termine di grado massimo del quoziente si ottiene dal rapportotra i termini di grado massimo di a0(x) = a(x) e b(x). Nel nostro caso tale rapporto e (3x4)/x = 3x3.Si utilizza poi il termine 3x3 appena calcolato per ottenere il polinomio a1(x) mediante la formula

a1(x) = a0(x)− (3x3)b(x) = −2x3 − (3/2)x2 + (1/2)x+ 5.

Il successivo termine del quoziente si ottiene dal rapporto tra i termini di grado massimo di a1(x) eb(x) e risulta quindi (−2x3)/x = −2x2. Si utilizza poi tale termine per calcolare

a2(x) = a1(x)− (−2x2)b(x) = (1/2)x2 + (1/2)x+ 5.

Il successivo termine del quoziente si ottiene dal rapporto tra i termini di grado massimo di a2(x) eb(x) e risulta quindi (x2/2)/x = (x/2). A questo punto si calcola

a3(x) = a2(x)− (x/2)b(x) = 5.

Essendo grado(a3) < grado(b) il procedimento si interrompe. Il resto della divisione e dato da r(x) =a3(x) = 5, mentre il quoziente e dato dalla somma dei termini ottenuti durante il procedimento erisulta quindi q(x) = 3x3 − 2x2 + (x/2). 2

Esempio 42 Consideriamo ora polinomi in Z11. Per alleggerire la notazione, in seguito omettiamo ilpedice 11 dalle classi di resto (scriviamo ad esempio [3] invece di [3]11). Calcoliamo quoziente e restodella divisione fra a(x) = [3]x4 + [2]x3 + [5]x2 + [1]x+ [7], e b(x) = [2]x2 + [1]x+ [1].

Il termine di grado massimo del quoziente si ottiene facendo il rapporto fra i termini di gradomassimo di a0(x) = a(x) e b(x). Esso risulta quindi (ricordiamo che siamo in Z11)

([3]x4)/([2]x2) = [2]−1[3]x2 = [6][3]x2 = [7]x2.

Si calcola poia1(x) = a0(x)− ([7]x2)b(x) = [6]x3 + [9]x2 + [1]x+ [7].

7.2 Polinomi a coefficienti in un campo 45

Il termine successivo del quoziente si ottiene dal rapporto fra i termini di grado massimo di a1(x) eb(x), che risulta ([6]x3)/([2]x2) = [3]x. Si calcola poi

a2(x) = a1(x)− ([3]x)b(x) = [6]x2 + [9]x+ [7].

Il termine successivo del quoziente si ottiene dal rapporto fra i termini di grado massimo di a2(x) eb(x), che risulta ([6]x2)/([2]x2) = [3]. Calcoliamo infine

a3(x) = a2(x)− ([3])b(x) = [6]x+ [4].

Essendo grado(a3) < grado(b) il procedimento termina fornendo quoziente q(x) = [7]x2 + [3]x+ [3] eresto r(x) = [6]x+ [4]. 2

Osservazione 20 Possiamo notare come il fatto che i coefficienti dei polinomi appartengano adun campo (e quindi tranne lo zero siano invertibili) sia fondamentale per poter eseguire la divisione.Supponiamo infatti di voler eseguire la divisione fra a(x) = x2 + [1]6 e b(x) = [2]6x+ [1]6. Se cerchia-mo di applicare il procedimento visto negli esempi precedenti, notiamo che come prima dovremmocalcolare il rapporto tra x2 e [2]6x. Ma questo non e possibile in quanto la classe [2]6 non ha l’inversomoltiplicativo. In effetti, non e difficile convincersi che non esiste nessuna coppia di polinomi q(x) er(x) tali che a(x) = b(x)q(x) + r(x). 2

Avendo introdotto la divisione euclidea tra polinomi possiamo ottenere molti dei risultati visti nelCapitolo 1 per i numeri interi. Possiamo ad esempio definire il massimo comun divisore tra duepolinomi a(x) e b(x) come il polinomio di grado massimo che divide sia a(x) che b(x). Il massimo comundivisore puo essere calcolato con l’algoritmo di Euclide che, ricordiamo, consiste in una successionedi divisioni euclidee e che quindi siamo in grado di eseguire anche con i polinomi. Per mancanza ditempo pero non approfondiremo questo argomento.

Utilizzando le proprieta della divisione euclidea e possible dimostrare anche il seguente importanteteorema.

Teorema 20 (Teorema fondamentale dell’algebra). Un polinomio non nullo di grado n a coefficientiin un campo ha al piu n radici. 2

Il Teorema 20 ha molte applicazioni, ma per quanto ci riguarda utilizzeremo solamente la conseguenzaespressa dal seguente corollario.

Corollario 3 Siano p(x) e q(x) due polinomi a coefficienti in un campo entrambi di grado minore ouguale a n. Se p(x) e q(x) sono diversi tra loro allora esistono al piu n valori distinti x1, . . . , xn taliche p(xi) = q(xi) per i = 1, . . . n.

Dimostrazione: Consideriamo il polinomio differenza d(x) = p(x) − q(x). Dato che p(x) e q(x)sono distinti, d(x) e un polinomio non nullo di grado al piu n. Per il Teorema (20) esistono al piun valori x1, . . . , xn tali che d(xi) = 0. Il corollario segue immediatamente osservando che essendod(xi) = p(xi) − q(xi) possiamo avere p(xi) = q(xi) soltanto per quei (al piu n) valori xi tali ched(xi) = 0. 2

Introduciamo infine il concetto di polinomio interpolatore. Informalmente il polinomio interpola-tore e un polinomio che “passa per” un insieme assegnato di punti. La definizione formale e il metodoper calcolarlo sono date nel seguente teorema. Come nel resto della sezione assumiamo che tutti ivalori su cui lavoriamo appartengano ad un campo.

Teorema 21 (Polinomio Interpolatore). Date n+ 1 coppie di valori (x0, y0), (x1, y1), . . . , (xn, yn) coni valori xi distinti (cioe xi 6= xj per i 6= j), possiamo trovare un polinomio p(x) di grado minore ouguale ad n tale che

p(x0) = y0, p(x1) = y1, . . . p(xn−1) = yn−1, p(xn) = yn.

Si dice che il polinomio p interpola i punti (x0, y0), . . . , (xn, yn).


Dimostrazione: Per i = 0, 1, . . . , n costruiamo il polinomio:

Li(x) =(x− x0)(x− x1) · · · (x− xi−1)(x− xi+1) · · · (x− xn)

(xi − x0)(xi − x1) · · · (xi − xi−1)(xi − xi+1) · · · (xi − xn).

Osserviamo che Li(x) al numeratore contiene il prodotto di tutti i termini (x− xj) tranne il termine(x−xi). Dato che i termini sono in totale n, il numeratore e un polinomio di grado n. Al denominatoreLi(x) contiene il prodotto di tutti i termini (xi − xj) tranne il termine (xi − xi) (che per fortuna nonc’e, perche se ci fosse renderebbe nullo il denominatore).

Il motivo per cui si considerano i polinomi Li(x), e che essi godono della seguente proprieta:

Li(xi) = 1, e Li(xj) = 0 per xj 6= xi (38)

Ad esempio, se consideriamo il polinomio L1(x) abbiamo che L1(x1) = 1, mentre L1(x0), L1(x2), etc.sono tutti uguali a zero. Per dimostrare la (38) e sufficiente osservare che quando valutiamo Li(x)in xi abbiamo che il numeratore diventa uguale al denominatore e quindi il loro rapporto e 1. Seinvece valutiamo Li(x) in un valore xj 6= xi abbiamo che uno dei termini al numeratore diventa zeroe di conseguenza Li(xj) = 0. Avendo dimostrata questa proprieta dei polinomi Li(x) e immediatoverificare che

p(x) = y0L0(x) + y1L1(x) + y2L2(x) + · · ·+ ynLn(x) (39)

e il polinomio che interpola i punti (xi, yi) cioe per i = 0, 1, . . . , n si ha che p(xi) = yi. Infatti, perla (38) abbiamo

p(xi) = y0L0(xi) + y1L1(xi) + · · ·+ yiLi(xi) + · · ·+ ynLn(xi)

= y0 · 0 + y1 · 0 + · · ·+ yi · 1 + · · ·+ yn · 0= yi

Osserviamo infine che p(x) e la somma di polinomi di grado n quindi ha anch’esso grado al piu n comerichiesto dal teorema. 2

Esempio 43 Consideriamo polinomi in Z11 omettendo per semplicita il pedice 11 dalle classi diresto. Supponiamo di voler costruire il polinomio p(x) tale che p([1]) = [7], p([3]) = [0], p([9]) = [5].Dobbiamo quindi applicare il Teorema 21 con

x0 = [1], y0 = [7], x1 = [3], y1 = [0], x2 = [9], y2 = [5].

Costruiamo i polinomi

L0(x) = (x−[3])(x−[9])([1]−[3])([1]−[9]) = x2+[10]x+[5]

[5] = [9]x2 + [2]x+ [1];

L1(x) = (x−[1])(x−[9])([3]−[1])([3]−[9]) = x2+x+[9]

[10] = [10]x2 + [10]x+ [2];

L2(x) = (x−[1])(x−[3])([9]−[1])([9]−[3]) = x2+[7]x+[3]

[4] = [3]x2 + [10]x+ [9].

E immediato verificare che vale per esempio L0([1]) = [1], L0([3]) = 0, e L0([9]) = [0]. Applicandola (39) otteniamo che il polinomio interpolatore e dato da

p(x) = [7]([9]x2 + [2]x+ [1]) + [0]([10]x2 + [10]x+ [2]) + [5]([3]x2 + [10]x+ [9])

= x2 + [9]x+ [8].

Notiamo per inciso che essendo y1 = [0] potevamo risparmiarci la fatica di calcolare L1(x). 2

Osservazione 21 La formula (39) e detta formula di Lagrange per il calcolo del polinomio interpola-tore. Notiamo che essa e la generalizzazione della formula vista alle scuole superiori per il calcolo dellaretta che passa per due punti. La cosa non deve sorprendere in quanto una retta e semplicemente unpolinomio di grado 1. 2

7.3 Codici a correzione di errore di Reed-Solomon 47

Come vedremo, i codici a correzione di errore sono basati sul fatto che esiste un unico polinomiointerpolatore. Questa proprieta e dimostrata dal seguente teorema.

Teorema 22 Date n + 1 coppie di valori (x0, y0), (x1, y1), . . . , (xn, yn) con i valori xi distinti, esisteun unico polinomio interpolatore p(x) di grado minore o uguale ad n tale che

p(x0) = y0, p(x1) = y1, . . . p(xn−1) = yn−1, p(xn) = yn.

Dimostrazione: Per il Corollario 3 due polinomi di grado minore o uguale a n possono assumere lostesso valore in al massimo n punti. Non possono quindi esistere due polinomi interpolatori diversi inquanto essi dovrebbero coincidere negli n+ 1 punti x0, . . . , xn. 2

7.3 Codici a correzione di errore di Reed-Solomon

In questa sezione mostreremo il funzionamento dei codici di correzione di errore di Reed-Solomon.Mostreremo l’idea alla base di questi codici con un esempio piccolo costruito lavorando in Z11 ediscuteremo poi come l’idea si generalizza per numeri primi piu grandi.

Come detto iniziamo lavorando in Z11. Per alleggerire la notazione, in seguito omettiamo il pedice11 dalle classi di resto. Supponiamo di voler trasmettere un messaggio M1 che consiste di 6 elementidi Z11, ad esempio M1 = 〈[3], [5], [5], [2], [7], [1]〉. Invece di trasmettere semplicemente questi 6 valori,il codice di Reed-Solomon costruisce il polinomio

P1(x) = [3] + [5]x+ [5]x2 + [2]x3 + [7]x4 + [1]x5 (40)

e trasmette la sequenza di valori P1([i]) per i = 1, 2, . . . , 10. Nel nostro caso, dato che P1([1]) = [1],P ([2]) = [6], etc. viene trasmessa la sequenza di valori

S1 = 〈[1], [6], [3], [0], [5], [3], [10], [6], [0], [7]〉. (41)

Notiamo quindi che vengono trasmessi 10 elementi di Z11 invece dei 6 che costituivano il messaggiooriginale. Vediamo ora che trasmettere quattro valori in piu permette al destinatario di ricostruireil messaggio originale anche se uno o due (dei 10) valori trasmessi vengono “corrotti” durante latrasmissione (cioe il destinatario riceve un valore diverso da quello spedito). Questa e infatti l’idea dibase dei codici a correzione di errore: trasmettere piu dati del necessario allo scopo di poter ricostruireil messaggio originale anche in presenza di errori nella trasmissione. Naturalmente ogni schema dicorrezione puo correggere solo un numero limitato di errori (nel nostro esempio fino a due errori): sela trasmissione e cosi disturbata che ogni valore trasmesso viene corrotto nessuno schema di correzionedi errori puo restituirci il messaggio originale.

Tornando al nostro esempio in cui viene trasmessa la sequenza (41), mostriamo per prima cosacome si possa ricostruire il messaggio originale nel caso in cui non ci siano errori di trasmissione. Ildestinatario del messaggio non deve fare altro che risolvere il problema di interpolazione di trovare ilpolinomio p(x) tale che

p([1]) = [1], p([2]) = [6], p([3]) = [3], . . . p([10]) = [7].

Tale polinomio puo essere calcolato usando la formula (39). Dato che per il Teorema 22 esiste un unicopolinomio interpolatore di grado minore o uguale a 9, questo procedimento non potra che restituire ilpolinomio P1(x) dato da (40); e dai coefficienti di questo polinomio il destinatario potra recuperare ilmessaggio originale M1 = 〈[3], [5], [5], [2], [7], [1]〉.

Mostriamo ora che anche nel caso in cui il destinatario riceva una sequenza che differisce da S1 peruno o due valori, sara sempre possibile ricostruire il messaggio originale. Consideriamo un qualsiasialtro messaggioM2 = 〈b0, b1, b2, b3, b4, b5〉, con bi ∈ Z11 per i = 0, . . . , 5. A tale messaggio corrispondeil polinomio

P2(x) = b0 + b1x+ b2x2 + b3x

3 + b4x4 + b5x

5

e la sequenzaS2 = 〈P2([1]), P2([2]), . . . , P2([10])〉.


Lemma 8 Se M1 6=M2 le sequenze S1 e S2 differiscono in almeno 5 posizioni.

Dimostrazione: Dato che M1 6= M2 i polinomi P1 e P2 sono distinti. Dato che hanno entrambigrado al piu 5, per il Corollario 3 essi possono assumere lo stesso valore in al piu 5 punti, cioe esistonoal massimo 5 elementi x1, . . . , x5 ∈ Z11 per cui P1(xi) = P2(xi). Dato che le sequenze S1 ed S2 hannolunghezza 10, esse devono differire in almeno 5 posizioni. 2

Supponiamo ora che il destinatario invece di S1 riceva una sequenza S1 che differisce da S1 in alpiu due posizioni. Il punto fondamentale e che la sequenza S1 differira da una qualsiasi altra sequenzaS2, ottenuta da un messaggioM2 con il procedimento appena visto, in almeno 3 posizioni. Infatti, peril Lemma 8 S2 differisce da S1 in almeno 5 posizioni: ogni errore di trasmissione puo “avvicinare” S1

a S2, ma dato che gli errori sono al piu due, S1 differira da S2 in almeno 3 posizioni. Di conseguenza,un possibile procedimento per ricostruire il messaggio originale e il seguente:

1. Si generano tutti i possibili messaggi M = 〈b0, b1, b2, b3, b4, b5〉;

2. Per ogni messaggio M si costruisce la corrispondente sequenza di 10 elementi e la si confrontacon S1

3. Il messaggio originale e quello che genera un sequenza che differisce da S1 in al piu due posizioni.Se nessuna sequenza differisce da S1 in al piu due posizioni vuol dire che durante la trasmissionesi sono verificati piu di due errori.

Questo procedimento e corretto, ma e molto inefficiente. Per rendersene conto basta osservare che an-che nel nostro esempio “piccolo” ci sono 116 = 1.771.561 possibili messaggi da provare. Fortunatamenteesiste anche un metodo piu efficiente per ricostruire il messaggio originale basato sull’interpolazione esull’algoritmo di Euclide esteso. Per motivi di tempo non riusciremo a descrivere questo metodo. Cilimitiamo quindi a mostrare il funzionamento e le proprieta dei codici di Reed-Solomon per un primop qualsiasi.

Sia p un primo qualsiasi e indichiamo con [0], [1], . . . , [p − 1] gli elementi di Zp. Supponiamo divoler trasmettere un messaggioM1 che consiste di k elementi di Zp,M1 = 〈a0, a1, . . . ak−1〉 con k < p.Il codice di Reed-Solomon costruisce il polinomio di grado k − 1

P1(x) = a0 + a1x+ a2x2 + · · ·+ ak−1x

k−1

e trasmette la sequenza di p− 1 elementi

S1 = 〈P1([1]), P1([2]), . . . , P1([p− 1])〉.

Abbiamo quindi che vengono trasmessi p−1 elementi di Zp invece dei k che costituiscono il messaggio.Per capire quale sia il vantaggio di trasmettere d = p−1−k elementi piu del necessario, consideriamoun secondo messaggio M2 = 〈b0, b1, . . . , bk−1〉, il corrispondente polinomio P2(x) = b0 + b1x + · · · +bk−1x

k−1, e la sequenza S2 = 〈P2([1]), . . . , P2([p− 1])〉. Il seguente lemma generalizza il Lemma 8.

Lemma 9 Se M1 6=M2 le sequenze S1 e S2 differiscono in almeno p− k posizioni.

Dimostrazione: Dato che M1 6= M2 i polinomi P1 e P2 sono distinti. Dato che hanno entrambigrado al piu k− 1, per il Corollario 3 essi possono assumere lo stesso valore in al piu k− 1 punti, cioeesistono al massimo k − 1 elementi x1, . . . , xk−1 ∈ Zp per cui P1(xi) = P2(xi). Dato che le sequenzeS1 ed S2 hanno lunghezza p− 1, esse devono differire in almeno p− k posizioni. 2

Ragionando come nel caso p = 11, siamo in grado di dimostrare il seguente teorema che ci fornisce ilmassimo numero di errori che possono essere corretti da un codice di Reed-Solomon su Zp.

Teorema 23 Se vengono trasmessi d = p− 1− k valori piu del necessario, i codici di Reed-Solomonpermettono di correggere fino a d/2 errori di trasmissione.

7.3 Codici a correzione di errore di Reed-Solomon 49

Dimostrazione: Consideriamo il messaggio originale M1 e un qualsiasi altro messaggio M2 6=M1.Per il Lemma 9 le sequenze ad essi associate S1 e S2 differiscono in almeno d + 1 = p − k posizioni.Se si verificano al massimo d/2 errori durante la trasmissione la sequenza S1 sara trasformata in unanuova sequenza S1 che differisce da S2 in almeno d+ 1− (d/2) = (d/2) + 1 posizioni, in quanto ognierrore puo far diminuire di 1 il numero di differenze tra S1 a S2. Dato pero che S1 differisce da S1 inal piu d/2 posizioni abbiamo che data la sequenza S1 il destinatario e in sempre grado di identificareS1 (e quindi M1) in quanto S1 e l’unica sequenza che differisce da S1 in al piu d/2 posizioni. 2

Esempio 44 Supponiamo che p = 251 e k = 230. Invece di trasmettere un messaggio di lunghezza230 il codice di Reed-Solomon ne trasmette uno di lunghezza 250. In questo caso abbiamo d = 20,quindi il destinatario puo ricostruire il messaggio originale se si verificano fino a 10 errori. Infatti,se M1 6= M2 le sequenze corrispondenti S1 ed S2 differiscono in almeno 21 posizioni (Lemma 9).Di conseguenza la sequenza con errori S1 differisce da S1 in al massimo 10 posizioni e differisce daqualsiasi altra sequenza S2 in almeno 11 posizioni. 2

Esercizio 37 Dovete spedire un lungo messaggio che consiste in una sequenza di interi compresitra 0 e 999. Il canale di comunicazione che utilizzate garantisce che su 10 valori spediti almeno 7vengono ricevuti correttamente. Descrivere un codice di Reed-Solomon che permette al destinatariodi ricostruire correttamente il messaggio originale.

Soluzione. Prendiamo p = 1009 che e il piu piccolo primo successivo a 1000. Il nostro messaggio dovraessere spezzato in blocchi di k valori e su ogni blocco si applica un codice di Reed-Solomon. Il problemae di determinare k in modo che tutti gli eventuali errori di trasmissione vengano corretti. Ricordiamoche dati k valori del messaggio originale un codice di Reed-Solomon ne trasmette p− 1 = 1008. Per lecaratteristiche del canale di comunicazione sappiamo che su 1008 valori trasmessi gli errori saranno almassimo 3

101008 ≤ 303. Per il Teorema 23, da una sequenza di 1008 valori siamo in grado di ricostruirei k valori del messaggio originale se il numero di errori commessi e minore o uguale a (1008 − k)/2.Imponendo che sia 303 ≤ (1008− k)/2 si ottiene k ≤ 402. La soluzione consiste quindi nello spezzareil messaggio originale in blocchi di 402 valori e applicare il codice di Reed-Solomon con p = 1009 adognuno di questi blocchi.

Come controprova osserviamo che il codice con parametri p = 1009 e k = 402 per il Teorema 23puo correggere fino a 303 errori che si verificano in ogni sequenza di 1008 valori trasmessa dal codice.Ma dato che il nostro canale commette al massimo 3 errori ogni 10 valori trasmessi, il numero di errorisu ogni sequenza lunga 1008 sara al massimo 303 e quindi saremo sempre in grado di ricostruire i 402valori del messaggio. 2

50 8 ESERCIZI DI RIEPILOGO

8 Esercizi di riepilogo

Esercizio 38 Avete acquistato 72 bottiglie di succo di papaya: nello scontrino il prezzo totale apparecome X8.5Y euro dove X e Y sono due cifre illeggibili. Quanto e costata ogni singola bottiglia?

Soluzione. Il prezzo (espresso in centesimi) e il numero di quattro cifre X85Y . Tale numero deveessere divisibile per 72, quindi deve essere divisibile per 8 e per 9. Affinche X85Y sia un multiplo di 8,il numero composto dalle ultime tre cifre (cioe 85Y ) deve essere multiplo di 8 (vedi Osservazione 7).Questo e possibile solo per Y = 6 perche tra i numeri fra 850 e 859 l’unico multiplo di 8 e 856. AffincheX856 sia multiplo di 9, deve essere X + 8 + 5 + 6 = X + 19 multiplo di 9 (vedi Teorema 7) e quindiX = 8. Il prezzo pagato e stato quindi 88.56 euro e il costo di ogni singola bottiglia 88.56/72 = 1.23euro. 2

Esercizio 39 Quali sono le ultime 2 cifre di 6789123?

Soluzione. Le ultime due cifre di un numero intero positivo sono date dal resto della divisione per 100.Quindi dobbiamo calcolare 6789123 mod 100. Essendo ϕ(100) = 40, per l’Osservazione 10 abbiamo

6789123 mod 100 = 67893 mod 100 = 893 mod 100 = 69.

2

Esercizio 40 Dire se il numero in base 16 (FFFFCF3)16 e divisibile per 15.

Soluzione. Per l’Osservazione 8 abbiamo che un numero in base 16 e divisibile per 15 se e solo se lasomma delle sue cifre e divisibile per 15. Ricordando che F = 15 e C = 12 abbiamo che

15 + 15 + 15 + 15 + 12 + 15 + 3 mod 15 = 0

quindi il numero e divisibile per 15. 2

Esercizio 41 Di un numero intero positivo n sappiamo che diviso per 8 da resto 7 e diviso per 125da resto 19. Quali sono le ultime 3 cifre di n?

Soluzione. Le ultime tre cifre di n sono date da n mod 1000. Il testo dell’esercizio ci dice che valgonole relazioni: {

n mod 8 = 7n mod 125 = 19.

(42)

Per il teorema cinese del resto la soluzione di questo sistema e una classe di resto modulomcm(8, 125) =1000 quindi per risolvere l’esercizio e sufficiente risolvere il sistema (42). Svolgendo i conti nella manierausuale si ottiene n ≡1000 519 e quindi la soluzione dell’esercizio sono le tre cifre 519. 2

Esercizio 42 Il pianeta Thoran ha 3 soli e 3 lune. La prima luna eclissa il primo sole ogni 57 giorni eil secondo sole ogni 42 giorni. La seconda luna eclissa il secondo sole ogni 19 giorni e il terzo sole ogni16 giorni. La terza luna eclissa il primo sole ogni 52 giorni. Oggi si e verificata l’eclisse contemporaneadi tutti e 3 i soli. Tra quanti giorni questo fenomeno si ripetera?

Soluzione. L’eclisse contemporanea dei tre soli si puo verificare solamente quando la terza luna eclissail primo sole, la seconda luna eclissa il terzo sole, e la prima luna eclissa il secondo sole. La terzaluna eclissera il primo sole tra 52, 104, 156, . . . , giorni, cioe tra un numero di giorni n con n ≡52 0.Analogamente la seconda luna eclissera il primo sole tra un numero di giorni n con n ≡16 0. Infine, laprima luna eclissera il secondo sole tra un numero di giorni n ≡42 0. Possiamo quindi concludere chel’eclissi contemporanea dei tre soli si verifichera tra un numero di giorni n soluzione del sistema:

n ≡52 0n ≡16 0n ≡42 0

.

Osserviamo che n0 = 0 e una soluzione particolare del sistema. Per il teorema cinese del resto lasoluzione generale e data da n ≡ 0 modulo mcm(52, 16, 42) = 4368. La prossima eclissi totale siverifichera quindi tra 4368 giorni.

51

Esercizio 43 Di un intero n sappiamo che e compreso fra 1000 e 3000; inoltre sappiamo che quandoe scritto in binario le sue ultime cifre sono 00110 e quando e scritto in base 3 le sue ultime cifre sono1021. Quanto vale n?

Soluzione. Sia n = (dk−1dk−2 · · · d500110)2 la rappresentazione binaria di n. Abbiamo allora

n = dk−1 · 2k−1 + dk−2 · 2k−2 + · · ·+ d5 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20

= (dk−12k−6 + dk−22k−7 + · · ·+ d5)25 + 22 + 21

= λ32 + 6.

cioe n mod 32 = 6. Analogamente, ragionando con la rappresentazione di m in base 3 si ottiene:

n = η34 + 1 · 33 + 0 · 32 + 2 · 31 + 1 · 30.

cioe n mod 81 = 34. Abbiamo quindi che n soddisfa al sistema{n ≡32 6n ≡81 34.

(43)

Utilizzando le solite tecniche otteniamo che la soluzione del sistema (43) e n ≡2592 358, quindi n ha laforma n = 358 + 2592k con k ∈ Z. Tra i numeri di questa forma l’unico compreso fra 1000 e 3000 equello che si ottiene per k = 1, quindi l’intero n cercato e n = 2950. 2

Esercizio 44 Sappiamo che dei messaggi sono trasmessi con il seguente meccanismo. Per prima cosale lettere vengono trasformate in numeri usando la regola spazio → 0, A → 1, B → 2, . . . , Z → 26.Successivamente, ogni valore x viene trasformato con la formula x → ax + b mod 27 dove a e b sonodue costanti che rappresentano la chiave del sistema crittografico. Trovare a e b sapendo che la parolaSI viene trasformata nella coppia di valori (13, 11).

Soluzione. Dato che S → 19, I → 9 i dati del problema ci dicono che valgono le relazioni:{19a+ b ≡27 139a+ b ≡27 11.

(44)

Sottraendo la seconda equazione dalla prima si ottiene 10a ≡27 2. Possiamo quindi ottenere a risolven-do l’equazione: a [10]27 = [2]27. Dato che [10]−1

27 = [19]27 otteniamo a = [38]27 = [11]27. Sostituendoa nella prima equazione otteniamo b = [13]27 − [19]27[11]27 da cui b = [20]27. La chiave e data quindidai valori a = 11, b = 20. 2

Esercizio 45 In un sistema di crittografia RSA, la chiave pubblica consiste nel modulo n = 11459209 edell’esponente di codifica e = 1147. Inoltre scoprite che i due primi che costituiscono la fattorizzazionedel modulo sono entrambi maggiori di 1000 e uno di essi scritto in binario contiene solamente la cifra1. Calcolare l’esponente di decodifica d.

Soluzione. I numeri che scritti in binario contengono solamente la cifra 1 sono quelli della forma 2k−1.La condizione che i primi siano maggiori di 1000 implica che k deve essere maggiore di 10. Procedendoper tentativi con k = 10, 11, . . ., si trova che 213 − 1 = 8191 divide n. Di conseguenza abbiamop = 8191, q = 1399. Ne segue che ϕ(n) = (p − 1)(q − 1) = 11449620, e l’esponente di decodifica siottiene applicando l’algoritmo di Euclide esteso alla coppia (11449620, 1147) che fornisce il risultatod = 5380423. 2

Appunti di Matematica Discreta - people.unipmn.itpeople.unipmn.it/manzini/matdis/matdis.pdf · 1.2...

Documents

Transcript of Appunti di Matematica Discreta - people.unipmn.itpeople.unipmn.it/manzini/matdis/matdis.pdf · 1.2...