Risolutore del teorema cinese del resto
Conta un mucchio di cose a tre a tre e ne avanzano 2, a cinque a cinque ne avanzano 3, a sette a sette ne avanzano 2: sono 23, oppure 128, oppure 233, una risposta ogni 105. È il problema del Sunzi Suanjing che ha dato il nome al teorema cinese del resto. Scrivi qualsiasi sistema di congruenze x ≡ a (mod n), con tante equazioni e numeri grandi quanto vuoi, e guarda la risposta, il procedimento con i tuoi numeri e un'immagine del perché funziona. Quando le equazioni non possono valere tutte, il risolutore indica le due che si contraddicono e mostra perché. Scrivi le equazioni x ≡ a (mod n), una per riga: a è il resto e n il modulo. Aggiungi una riga con Aggiungi equazione, o premendo Invio nell'ultimo modulo, e toglila con ×. Funzionano numeri interi fino a 200 cifre, e a può essere negativo. Oppure scegli un esempio svolto. I riquadri mostrano la soluzione più piccola e ogni quanto si ripete; sotto ci sono le prime soluzioni positive e una verifica di ogni equazione. L'immagine segna i numeri che soddisfano ogni equazione, e la colonna in cui ogni riga ha un segno è la soluzione; la tabella dei resti mostra due equazioni insieme. Il procedimento è scritto con i tuoi numeri, con la costruzione classica o per sostituzione.
Come funziona
- Scrivi le equazioni x ≡ a (mod n), una per riga, oppure scegli un esempio svolto come il problema di Sunzi, il cesto di uova o il periodo giuliano.
- Leggi la soluzione più piccola, il modulo con cui si ripete e le prime soluzioni positive, ognuna verificata su ogni equazione.
- Segui il procedimento passo per passo, con la costruzione o per sostituzione, e passa l'immagine dalla retta numerica alla tabella dei resti.
Come funziona la costruzione
Quando nessuna coppia di moduli ha un fattore comune, la soluzione si può costruire direttamente. Moltiplica i moduli: per il problema di Sunzi N = 3 × 5 × 7 = 105. Per ogni equazione prendi Nᵢ = N / nᵢ, un multiplo di ogni altro modulo: 35, 21 e 15. Poi trova l'inverso yᵢ di Nᵢ mod nᵢ con l'algoritmo di Euclide esteso: 35 diviso per 3 dà resto 2, e 2 × 2 = 4 ≡ 1 (mod 3), quindi y₁ = 2; 21 e 15 danno resto 1, quindi i loro inversi sono 1. Ora x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, e 233 mod 105 = 23. Ogni termine soddisfa la propria equazione ed è un multiplo degli altri moduli, quindi la somma le soddisfa tutte.
Quando i moduli hanno un fattore comune
Anche un sistema i cui moduli hanno fattori comuni può avere una soluzione. Due equazioni x ≡ a (mod m) e x ≡ b (mod n) possono valere insieme esattamente quando a − b è un multiplo di gcd(m, n), e allora la soluzione si ripete ogni lcm(m, n) invece che ogni m × n. Due autobus che partono ai minuti 5 e 11, ogni 12 e ogni 18 minuti, si incontrano al minuto 29 e poi ogni 36 minuti, perché 11 − 5 = 6 è un multiplo di gcd(12, 18) = 6. Ma x ≡ 1 (mod 4) e x ≡ 4 (mod 6) non possono mai valere insieme: la prima rende x dispari, la seconda pari. Un sistema intero ha una soluzione esattamente quando ogni coppia delle sue equazioni ne ha una, ed è così che il risolutore trova le due che si contraddicono.
Domande frequenti
Che cosa dice il teorema cinese del resto?
Se nessuna coppia dei moduli n₁, n₂, … ha un fattore comune, allora per qualsiasi resto a₁, a₂, … esiste esattamente un x da 0 a N − 1 con x ≡ aᵢ (mod nᵢ) per ogni i, dove N è il prodotto dei moduli. Ogni altra soluzione differisce da questa per un multiplo di N: per il problema di Sunzi le soluzioni sono 23, 128, 233 e così via, una ogni 105.
Perché si chiama cinese?
Il più antico problema noto di questo tipo si trova nel Sunzi Suanjing, un libro di aritmetica cinese scritto tra il III e il V secolo: contate a tre, a cinque e a sette, delle cose danno resti 2, 3 e 2. Qin Jiushao diede un metodo generale per questi problemi nel 1247, e Carl Friedrich Gauss enunciò il teorema nella sua forma moderna nel 1801.
E se i moduli non sono coprimi?
Allora può non esserci alcuna soluzione, e quando c'è si ripete ogni minimo comune multiplo dei moduli invece che ogni prodotto. Due equazioni sono compatibili quando i loro resti coincidono modulo il gcd dei loro moduli. L'indovinello delle uova usa 2, 3, 4, 5, 6 e 7, che hanno fattori comuni, eppure ha una soluzione: 301, che si ripete ogni 420.
Come usa RSA il teorema cinese del resto?
Decifrare un messaggio RSA significa calcolare c^d mod n, dove n = p × q. È più veloce calcolare c^d mod p e c^d mod q separatamente, con l'esponente ridotto mod p − 1 e q − 1, e unire i due risultati con il teorema. Con numeri lunghi la metà, ciascuna delle due potenze richiede circa un ottavo del lavoro, quindi la decifratura è circa quattro volte più veloce, e la maggior parte dei software RSA fa così.
Quanto possono essere grandi i numeri?
Fino a 20 equazioni, con numeri fino a 200 cifre ciascuno. Il risolutore lavora con numeri interi esatti nel tuo browser, quindi la risposta è esatta per quanto lunga sia, e nulla viene inviato da nessuna parte.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor