Risolutore teorema cinese del resto

Il risolutore del teorema cinese del resto prende un sistema di congruenze simultanee — x congruo a ciascun resto a_i modulo ciascun modulo n_i — e restituisce la classe di soluzione unica quando esiste. Fornisci array paralleli di resti e moduli; il motore li combina con CRT successivo, verifica la coerenza quando i moduli condividono fattori, e riporta sia il rappresentante x tra zero e modulo meno uno sia il modulo della classe di soluzione (il prodotto degli n_i quando sono coprimi a coppie, altrimenti il loro minimo comune multiplo).

Cosa restituisce il teorema cinese del resto e quando i sistemi falliscono

La famosa tripletta da classe — x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 — dà x ≡ 23 mod 105. Questo strumento accetta anche la forma generale: i moduli non devono essere per forza coprimi a coppie. Classicamente, se i moduli sono coprimi a coppie, esiste esattamente una classe di resto modulo il prodotto degli n_i che soddisfa ogni congruenza contemporaneamente. In quel caso una soluzione esiste se e solo se ogni coppia di resti concorda modulo l'MCD dei moduli corrispondenti, e la soluzione è unica modulo il minimo comune multiplo di tutti gli n_i. Quando i resti sono in disaccordo, la richiesta fallisce con invalid_input e un messaggio che nomina l'incoerenza invece di inventare un x falso. La risposta JSON in caso di successo include x, modulus (il modulo CRT della classe di soluzione), product (il prodotto grezzo dei moduli in input), i resti ridotti tra zero e n_i meno uno, una copia dei moduli e count. Array mancanti, lunghezze diverse, moduli non positivi, valori non interi e valori fuori dall'intervallo di interi sicuri falliscono anch'essi con invalid_input, così una cella sbagliata di un foglio di calcolo non diventa mai una risposta errata in silenzio.

Come vengono letti resti e moduli e come il CRT successivo resta esatto

Ogni modulo deve essere un intero positivo sicuro. I resti possono essere negativi e vengono ridotti nell'intervallo canonico prima della fusione. Internamente il motore parte dalla prima congruenza e fonde ripetutamente la successiva: dato x ≡ x0 mod m e x ≡ a mod n, calcola g uguale all'MCD di m e n, respinge il sistema se a meno x0 non è divisibile per g, poi costruisce la soluzione aggiornata con un inverso modulare di m su g modulo n su g e moltiplica il modulo per n su g per ottenere il nuovo mcm. Tutte le moltiplicazioni sono protette così che il prodotto e il modulo CRT intermedio restino entro gli interi sicuri di JavaScript; prodotti sovradimensionati falliscono chiaramente invece di andare in overflow. I campi preferiti sono remainders e moduli come array JSON di interi di uguale lunghezza. Gli alias a, ai e residues corrispondono a remainders; n, ni e mods corrispondono a moduli, così che moduli, stringhe di query e notebook legacy possano riusare un unico contratto. Ogni voce può essere un intero JSON o una stringa decimale con un segno iniziale opzionale; frazioni, notazione scientifica e spazi incorporati vengono respinti.

Dove compaiono i sistemi CRT nello studio, nell'intuizione crittografica e nel codice

Gli sviluppatori usano lo stesso contratto per validare ricostruzioni modulari in dimostrazioni educative di RSA, per costruire vettori di test deterministici per librerie di aritmetica modulare, e per verificare che una pipeline di resti si sollevi ancora a una singola classe dopo un cambio di schema. In questa pagina il lavoro gira interamente nel tuo browser; tramite l'API ogni risoluzione riuscita costa $0.002, la validazione fallita non viene addebitata e nulla viene conservato dopo la restituzione della risposta.