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) |
Consigli
- 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.
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.