Calcolatrice del teorema cinese del resto — sistemi di congruenze
Calcolatrice che risolve con il teorema cinese del resto i sistemi di congruenze del tipo x congruo ad a modulo n. Verifica automaticamente che i moduli siano coprimi e ricava la soluzione intera non negativa minima e la soluzione generale.
Esempio di calcolo: il problema del numero ignoto nel classico trattato cinese
Il problema classico riportato in un trattato di aritmetica cinese del terzo o quinto secolo, considerato l'origine del teorema cinese del resto: «qual è il numero che diviso per tre dà resto due, diviso per cinque dà resto tre e diviso per sette dà resto due?». La risposta è ventitré, modulo centocinque.
| Prima condizione | x ≡ 2 (mod 3) |
|---|---|
| Seconda condizione | x ≡ 3 (mod 5) |
| Terza condizione | x ≡ 2 (mod 7) |
| Soluzione | x ≡ 23 (mod 105) |
Che cos’è il teorema cinese del resto
Il teorema cinese del resto risolve sistemi di congruenze del tipo **«quale numero lascia 2 dividendolo per 3, 3 per 5 e 2 per 7?»**. Se i moduli sono tutti coprimi, esiste esattamente una soluzione entro l’intervallo che il loro prodotto fissa. Questo strumento prende fino a cinque congruenze e restituisce la minima soluzione non negativa insieme a quella generale.
**Si tratta soltanto la forma classica: quella in cui tutti i moduli sono coprimi.** Se due di essi condividono un divisore maggiore di uno, il sistema non si risolve per questa via e un messaggio lo avverte; il teorema generalizzato per moduli non coprimi resta fuori dall’ambito. **I moduli devono essere interi da 2 in su**, e i resti si normalizzano da sé nell’intervallo da zero fino a meno del loro modulo, sicché si ammettono valori pari o superiori al modulo, e anche negativi. L’aritmetica corre su interi a precisione arbitraria: nessun limite di cifre.
Come si usa il calcolatore
- Inserisca il resto e il modulo Per ciascuna congruenza indichi il resto a e il modulo n. Stanno per x ≡ a (mod n).
- Aggiunga altre congruenze Con «aggiungi congruenza» ne allinei fino a cinque. Quante più siano, tanto più ampio l’intervallo — il prodotto dei moduli — su cui la soluzione resta unica.
- Risolva Prema risolvi e ottiene la minima soluzione non negativa insieme alla soluzione generale modulo il prodotto dei moduli.
- Segua lo svolgimento Per ciascuna congruenza si elencano Nᵢ (il prodotto dei moduli privato del proprio) e Mᵢ (l’inverso di Nᵢ). Servono a riscontrare una soluzione ottenuta a mano.
- Si esigono moduli coprimi Un messaggio che dica i moduli non coprimi significa che due condividono un divisore — 4 e 6, per esempio. Riveda la combinazione.
Consigli per sfruttarlo al meglio
- Se i moduli non sono coprimi fra loro compare un errore. I moduli quattro e sei, per esempio, hanno massimo comune divisore due e questa calcolatrice non li risolve: occorrerebbe la forma generalizzata del teorema.
- Anche se il resto è maggiore o uguale al modulo, oppure negativo, il valore è normalizzato automaticamente prima del calcolo: potete inserirlo così com'è.
- Si possono aggiungere da due a cinque congruenze. Con tre o più condizioni si affrontano anche problemi come la ricerca di un numero che soddisfi contemporaneamente più vincoli periodici.
- La soluzione generale è mostrata nella forma della congruenza modulo il prodotto dei moduli: qualunque numero ottenuto sommando un multiplo intero di quel prodotto soddisfa tutte le condizioni.
Dove il teorema è utile
Esercizi di teoria dei numeri e preparazione agli esami
Serve a riscontrare una risposta ottenuta a mano. Comparendo anche Nᵢ e Mᵢ, si circoscrive il punto in cui si è insinuato un errore.
Studiare algoritmi crittografici
L’ottimizzazione CRT che accelera la decifratura RSA applica direttamente questo teorema. Il meccanismo si segue nei numeri.
Trovare quando i cicli coincidono
Gli istanti in cui eventi di periodi diversi cadono insieme si scrivono come sistema di congruenze.
Rifare il problema classico
Il «numero ignoto» del Sunzi Suanjing — che lascia 2 per 3, 3 per 5 e 2 per 7 — è 23 modulo 105. Lo inserisca così com’è e verifichi.
Quando vuole gli strumenti affini di teoria dei numeri
Per inversi e congruenze in sé veda l’aritmetica modulare; per i massimi comuni divisori, MCD e mcm; per la scomposizione, la scomposizione in fattori primi.
Termini sul teorema cinese del resto
- Teorema cinese del resto
- Il teorema che afferma come un sistema di congruenze a moduli coprimi possieda una soluzione unica modulo il loro prodotto.
- Congruenza
- Un’espressione della forma x ≡ a (mod n), che dice come il resto di x diviso per n sia uguale ad a.
- Modulo
- Il numero per cui si divide. Qui limitato agli interi da 2 in su.
- Coprimi
- Due interi il cui massimo comun divisore è 1. Il teorema classico esige che due qualunque dei moduli lo siano.
- Coprimi a due a due
- Di tre o più numeri: che due qualunque presi fra essi siano coprimi. Un insieme può avere 1 per massimo comun divisore senza esserlo a due a due.
- Inverso modulare
- La x che soddisfa a·x ≡ 1 (mod n). Nel teorema compare nel momento di trovare Mᵢ, l’inverso di Nᵢ.
- Algoritmo di Euclide esteso
- L’algoritmo che rende i coefficienti di Bézout insieme al massimo comun divisore. È esso a calcolare un inverso modulare.
- Soluzione generale
- La minima soluzione non negativa, accresciuta di ogni multiplo intero del prodotto dei moduli, scritta nella forma x ≡ 23 (mod 105).
Domande frequenti
A proposito — da un trattato del terzo secolo all'accelerazione della crittografia RSA
L'origine del teorema cinese del resto risale al problema del numero ignoto riportato in un trattato di aritmetica cinese composto fra il terzo e il quinto secolo. La domanda — quanti siano i numeri che divisi per tre danno resto due, divisi per cinque danno resto tre e divisi per sette danno resto due — mostrava già in sostanza la stessa idea del teorema odierno: risalire a un numero a partire dai resti di più divisioni.
Uno degli impieghi pratici oggi più rilevanti è l'accelerazione della decifrazione nella crittografia RSA. La decifrazione consiste nell'elevare un numero enorme alla chiave privata e prenderne il resto rispetto a un modulo; anziché usare direttamente il numero composto, prodotto di due grandi numeri primi, si calcola separatamente modulo ciascuno dei due fattori e si ricombinano i risultati con il teorema, ottenendo in teoria un'accelerazione fino a circa quattro volte. È la tecnica nota come RSA con teorema cinese del resto, realizzata in molte librerie crittografiche.
Questo strumento prevede la forma classica del teorema, con moduli tutti coprimi fra loro. Quando i moduli hanno divisori comuni, come quattro e sei, una soluzione può ugualmente esistere a certe condizioni, ma la verifica e il calcolo richiedono l'algoritmo generalizzato, che esula dal presente strumento.