Teoria dei numeri e aritmetica modulare: esercizi con soluzioni passo passo
Detto anche: aritmetica modulare
Esercizi gratuiti su Teoria dei numeri e aritmetica modulare con schemi, suggerimenti e soluzioni svolte complete. Valori nuovi ogni volta, su tre livelli: MCD e resti, inversi e congruenze, potenze modulari e RSA.
Esercizio gratuitoFacile
Trova 942 mod 11, il resto r con 0 ≤ r < 11.
a = 942n = 11
Risposta esatta: un numero intero, senza arrotondamenti.
Come risolvere gli esercizi di Teoria dei numeri e aritmetica modulare
Riduci prima ogni numero modulo n; i resti sono compresi tra 0 e n − 1.
Per un MCD, dividi ripetutamente con l’algoritmo di Euclide; l’ultimo resto diverso da zero è il MCD.
Per un inverso, esegui l’algoritmo esteso e tieni il coefficiente di a; aggiungi n se è negativo.
Risolvi a·x ≡ b moltiplicando per a⁻¹; combina due congruenze scrivendo x = r₁ + m₁k.
Per le potenze, scrivi l’esponente in binario ed eleva al quadrato ripetutamente; in RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
Errori comuni
Dare un resto negativo per un numero negativo.
Fermare l’algoritmo di Euclide al primo resto.
Lasciare negativo l’inverso invece di sommare n.
Prendere l’esponente RSA d modulo n invece che modulo φ(n).
Ridurre l’esponente modulo p invece che modulo p − 1 con il teorema di Fermat.
Formule chiave
Divisione con resto
a = q·n + r, 0 ≤ r < n
Euclide
gcd(a, b) = gcd(b, a mod b)
Minimo comune multiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruenza lineare
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funzione φ di Eulero
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Impara Teoria dei numeri e aritmetica modulare da zero
1Resti e congruenze
Dividendo a per n si ottengono un quoziente q e un resto r: a = q·n + r con 0 ≤ r < n. Il resto si scrive a mod n. Per un numero negativo anche q è negativo: −3 = −1·7 + 4, quindi −3 mod 7 = 4.
Due numeri sono congrui modulo n, a ≡ b (mod n), quando lasciano lo stesso resto, cioè quando n divide a − b.
I resti si possono ridurre a ogni passaggio, il che mantiene piccoli i numeri:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, e lo stesso per a·b
Per esempio 47·58 mod 9: 47 ≡ 2 e 58 ≡ 4, quindi 47·58 ≡ 8 (mod 9).
Autoverifica Quanto vale −17 mod 5?
2
3
−2
−3
Risposta: 3. −17 = −4·5 + 3, quindi il resto è 3. La risposta 2 è 17 mod 5; un resto non è mai negativo.
2Algoritmo di Euclide
Il massimo comun divisore MCD(a, b) è il numero più grande che divide entrambi. L’algoritmo di Euclide usa MCD(a, b) = MCD(b, a mod b):
Dividi: a = q·b + r.
Sostituisci (a, b) con (b, r).
Ripeti finché il resto è 0. L’ultimo resto diverso da zero è il MCD.
Il minimo comune multiplo ne segue: mcm(a, b) = a·b / MCD(a, b).
Autoverifica Quanto vale MCD(84, 36)?
12
252
4
6
Risposta: 12. 84 = 2·36 + 12 e 36 = 3·12 + 0, quindi il MCD è 12. 252 è il minimo comune multiplo, 84·36/12.
3Inversi e algoritmo esteso
L’inverso di a modulo n è il numero x con a·x ≡ 1 (mod n). Esiste esattamente quando MCD(a, n) = 1.
L’algoritmo di Euclide esteso esegue Euclide su (n, a) e tiene un coefficiente t per ogni resto, in modo che ogni resto r ≡ t·a (mod n). Parti con t = 0 per n e t = 1 per a; ogni nuovo t è il t di due righe sopra meno q per il t della riga precedente. Quando compare il resto 1, il suo t è l’inverso.
Con l’inverso, una congruenza a·x ≡ b (mod n) si risolve con x ≡ a⁻¹·b. Quando d = MCD(a, n) è maggiore di 1, ci sono d soluzioni se d divide b, e nessuna altrimenti.
Due congruenze con moduli coprimi, x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂), hanno esattamente una soluzione modulo m₁·m₂ (teorema cinese del resto). Scrivi x = r₁ + m₁k e risolvi per k.
Il quadrato ripetuto calcola rapidamente aᵏ mod n: scrivi k in binario, trova a, a², a⁴, a⁸, … mod n elevando al quadrato e riducendo, e moltiplica le potenze il cui bit è 1.
Piccolo teorema di Fermat: per un primo p che non divide a, aᵖ⁻¹ ≡ 1 (mod p). Quindi l’esponente si può ridurre modulo p − 1.
RSA costruisce una chiave a partire da due primi p e q:
n = p·q e φ(n) = (p − 1)(q − 1).
Scegli e con MCD(e, φ(n)) = 1; (n, e) è la chiave pubblica.
Calcola d = e⁻¹ mod φ(n): la chiave privata.
Cifra c = mᵉ mod n; decifra m = cᵈ mod n.
La φ di Eulero φ(n) conta i numeri da 1 a n coprimi con n: φ(p) = p − 1 per un primo, φ(pᵏ) = pᵏ − pᵏ⁻¹, e φ è moltiplicativa per fattori coprimi.
Autoverifica Una chiave RSA usa p = 5, q = 11 ed e = 3. Quanto vale d?
13
27
37
3
Risposta: 27. φ(n) = 4·10 = 40, e 3·27 = 81 = 2·40 + 1, quindi d = 27. L’inverso di 3 modulo n = 55 sarebbe 37, ma d si prende modulo φ(n).
5Errori comuni
Dare un resto negativo per un numero negativo: −17 mod 5 è 3, non −2.
Fermare Euclide al primo resto invece che all’ultimo diverso da zero.
Dimenticare di sommare n a un coefficiente negativo dell’algoritmo esteso.
Calcolare l’esponente RSA d modulo n invece che modulo φ(n).
Ridurre un esponente modulo p invece che modulo p − 1 con il teorema di Fermat.
6Come sono fatte le domande d’esame
Facile: MCD e resti. Esegui l’algoritmo di Euclide per un MCD o un mcm, trovi i resti di numeri negativi e riduci somme e prodotti modulo n.
Medio: inversi e congruenze. Trovi inversi modulari con l’algoritmo esteso, risolvi congruenze lineari, combini due congruenze con il teorema cinese del resto e calcoli la φ(n) di Eulero.
Difficile: potenze modulari e RSA. Usi il quadrato ripetuto e il teorema di Fermat, risolvi congruenze con più soluzioni e trovi esponenti privati RSA, testi cifrati e messaggi decifrati.
Trova (914·953) mod 11 senza svolgere i prodotti dei numeri grandi: riduci prima.
n = 11
Calcola (914·953) mod 11
Mostra i suggerimenti
(x·y) mod n = ((x mod n)·(y mod n)) mod n, e lo stesso vale per le somme.
914 mod 11 = 1, 953 mod 11 = 7.
Riduci modulo 11 il prodotto dei resti.
Mostra la risposta e la soluzione passo passo
Divisibilità e resti: a mod n è il resto r con 0 ≤ r < n e a = q·n + r, anche quando a è negativo. L’algoritmo di Euclide trova MCD(a, b) ripetendo a = q·b + r e sostituendo (a, b) con (b, r); l’ultimo resto diverso da zero è il MCD. Poi mcm(a, b) = a·b/MCD(a, b). I resti si possono ridurre a ogni passaggio: (a + b) mod n e (a·b) mod n dipendono solo da a mod n e b mod n.
Riduci ogni numero
914 ≡ 1, 953 ≡ 7 (mod 11)
Combina
1·7 = 7 ≡ 7 (mod 11)
Risposta
(914·953) mod 11 = 7
Esempio 2Media
Trova la funzione φ di Eulero φ(637), il numero di interi da 1 a 637 coprimi con 637.
n = 637 = 72·13
Calcola φ(637)
Mostra i suggerimenti
Scomponi n in fattori primi: 637 = 72·13.
φ è moltiplicativa per fattori coprimi, e φ(pᵏ) = pᵏ − pᵏ⁻¹.
φ(n) = n·∏(1 − 1/p).
Mostra la risposta e la soluzione passo passo
Inversi e congruenze: a ha un inverso modulo n esattamente quando MCD(a, n) = 1. L’algoritmo di Euclide esteso scrive 1 = s·n + t·a, e allora a⁻¹ ≡ t (mod n). Una congruenza a·x ≡ b (mod n) con MCD(a, n) = 1 ha la soluzione x ≡ a⁻¹·b. Due congruenze x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂) con moduli coprimi hanno una soluzione modulo m₁·m₂ (teorema cinese del resto). La φ di Eulero φ(n) conta i numeri da 1 a n coprimi con n: φ(n) = n·∏(1 − 1/p).
Fattori primi
637 = 72·13
Funzione φ
φ(637) = φ(49)·φ(13) = 42·12 = 504
Risposta
φ(637) = 504
Esempio 3Difficile
Una chiave RSA usa p = 13, q = 37 ed e = 23. Decifra il testo cifrato c = 225: trova il messaggio m.
p = 13q = 37e = 23c = 225
Calcola m
Mostra i suggerimenti
n = 481, φ(n) = 432.
d = e⁻¹ mod φ(n) = 263.
m = cd mod n = 225263 mod 481: usa il quadrato ripetuto.
Mostra la risposta e la soluzione passo passo
Potenze modulari e RSA: calcola aᵏ mod n con il quadrato ripetuto: scrivi k in binario, eleva al quadrato, riduci a ogni passaggio e moltiplica le potenze il cui bit è 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) per un primo p che non divide a, quindi l’esponente si può ridurre modulo p − 1. RSA: scegli i primi p e q, n = p·q e φ(n) = (p − 1)(q − 1); l’esponente pubblico e è coprimo con φ(n), e l’esponente privato è d = e⁻¹ mod φ(n). Cifra con c = mᵉ mod n e decifra con m = cᵈ mod n.
Esponente privato
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
Decifra con il quadrato ripetuto
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
Messaggio
m = 361
verifica: 36123 mod 481 = 225
Risposta
m = 361
Domande e risposte
Teoria dei numeri e aritmetica modulare: di cosa si tratta?
Dividendo a per n si ottengono un quoziente q e un resto r: a = q·n + r con 0 ≤ r < n. Il resto si scrive a mod n. Per un numero negativo anche q è negativo: −3 = −1·7 + 4, quindi −3 mod 7 = 4.
Due numeri sono congrui modulo n, a ≡ b (mod n), quando lasciano lo stesso resto, cioè quando n divide a − b.
Teoria dei numeri e aritmetica modulare: come si risolvono gli esercizi passo per passo?
Riduci prima ogni numero modulo n; i resti sono compresi tra 0 e n − 1.
Per un MCD, dividi ripetutamente con l’algoritmo di Euclide; l’ultimo resto diverso da zero è il MCD.
Per un inverso, esegui l’algoritmo esteso e tieni il coefficiente di a; aggiungi n se è negativo.
Risolvi a·x ≡ b moltiplicando per a⁻¹; combina due congruenze scrivendo x = r₁ + m₁k.
Per le potenze, scrivi l’esponente in binario ed eleva al quadrato ripetutamente; in RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
Teoria dei numeri e aritmetica modulare: quali sono gli errori più comuni?
Dare un resto negativo per un numero negativo.
Fermare l’algoritmo di Euclide al primo resto.
Lasciare negativo l’inverso invece di sommare n.
Prendere l’esponente RSA d modulo n invece che modulo φ(n).
Ridurre l’esponente modulo p invece che modulo p − 1 con il teorema di Fermat.
Teoria dei numeri e aritmetica modulare: che cosa si esercita?
Facile: MCD e resti
Media: inversi e congruenze
Difficile: potenze modulari e RSA
Ogni esercizio ha valori nuovi, così impari il metodo invece di una risposta. Bloccato? Apri prima un piccolo suggerimento e la spiegazione completa solo quando ti serve.
Come funziona l’esercitazione
Ogni esercizio ha valori nuovi, così impari il metodo invece di una risposta.
Bloccato? Apri prima un piccolo suggerimento e la spiegazione completa solo quando ti serve.
I tuoi progressi, i tuoi errori e gli esercizi salvati restano memorizzati, così puoi ripassare prima dell’esame.