Inverso moltiplicativo modulo n

L'inverso moltiplicativo di un intero modulo n è il residuo inverse che soddisfa intero per inverse congruente a uno modulo n. Tale inverse esiste se e solo se l'intero e il modulo sono coprimi — il loro massimo comune divisore vale uno. Tutorial di crittografia, passi di chiave privata RSA, divisione modulare nella programmazione competitiva e calcoli su gruppi ciclici richiedono questa operazione, ma molti linguaggi espongono solo un GCD binario e lasciano a Lei i coefficienti di Bézout.

Cos'è un inverso moltiplicativo modulo n e quando esiste

Nell'aritmetica ordinaria ogni numero non nullo ha un inverso moltiplicativo: dividendolo si ottiene uno. Nell'aritmetica modulare la stessa idea diventa una congruenza. Si dice che inverse è un inverso moltiplicativo di un intero modulo n quando l'intero per inverse lascia resto uno diviso per il modulo.

Poiché i residui si avvolgono ogni n passi, non ogni intero ha un tale inverse. L'ostacolo è aritmetico, non di virgola mobile: se d è il gcd dell'intero e del modulo e d è maggiore di uno, allora l'intero per qualsiasi candidato è multiplo di d, quindi il prodotto non può mai essere congruente a uno, che non è multiplo di d.

Viceversa, l'identità di Bézout garantisce interi x e y con intero per x più modulo per y uguale a uno esattamente quando quel gcd è uno, e ridurre x modulo n produce l'inverse. Gli ingegneri incontrano questa condizione dividendo in un anello finito, scegliendo esponenti di decifratura RSA che invertono l'esponente pubblico modulo phi di N, annullando moltiplicazioni modulari in pipeline di hash o risolvendo congruenze lineari in programmazione competitiva.

Restituire un errore esplicito quando la coppia non è coprima è più utile di un fallimento silenzioso: il client scopre che non esiste inverse e può ramificare sul gcd invece di indovinare quale libreria ha restituito un residuo sbagliato. La calcolatrice tratta perciò una coppia non coprima come ingresso non valido, invece di inventare un inverse fittizio che romperebbe ogni controllo successivo della congruenza definitoria.

Come questa calcolatrice esegue l'algoritmo di Euclide esteso

L'implementazione prima riduce l'intero nella classe di residuo non negativa residue da zero a n meno uno, poi applica l'algoritmo di Euclide esteso alla coppia residue e modulus. Ogni passo registra il quoziente intero e aggiorna i coefficienti di Bézout così che al termine il coefficiente di residue moltiplica residue più un coefficiente del modulo uguale al gcd. Se il gcd è uno, il coefficiente di residue è ridotto nell'intervallo da zero a n meno uno e restituito come inverse.

I valori assoluti sono limitati a un bilione affinché ogni raddoppio intermedio del prodotto modulare resti nel range di interi sicuri di JavaScript. Gli interi negativi sono accettati e ridotti prima del ciclo euclideo, così un ingresso di meno tre modulo undici è trattato come residue otto e invertito in quella classe.

Uso pratico, limiti, prezzi e consegna

Usi lo strumento del browser quando desidera un inverse rapido leggendo una nota di cripto, controllando una congruenza per i compiti o debuggando un passo di moltiplicazione modulare. Gli input accettati sono interi con valore assoluto al massimo un bilione e moduli da due a un bilione. I risultati sono deterministici: la stessa coppia produce sempre lo stesso inverse e lo stesso campo check.

Tenga la coppia entro i limiti pubblicati, tratti l'errore di non coprimalità come esito di prima classe nei Suoi test e ottiene un inverse riproducibile per compiti, plugin LMS e worker al bordo senza erigere un sistema di algebra computazionale proprio.