Calcolatore Esponenziazione Modulare

Calcolatore Esponenziazione Modulare

Il Calcolatore di Esponenziazione Modulare calcola \(a^b \bmod n\) — elevando una base \(a\) a un esponente \(b\) e calcolando il resto della divisione per il modulo \(n\). Utilizza l'algoritmo di esponenziazione binaria (chiamato anche fast power o elevamento a potenza al quadrato), che riduce l'operazione da \(O(b)\) moltiplicazioni a sole \(O(\log b)\). Questo è lo stesso algoritmo utilizzato nelle implementazioni crittografiche del mondo reale come RSA, Diffie-Hellman ed ElGamal.

Applicazioni dell'Esponenziazione Modulare

Come Funziona l'Algoritmo di Esponenziazione Binaria

L'intuizione chiave è che possiamo decomporre qualsiasi esponente in una somma di potenze di 2 usando la sua rappresentazione binaria. Ad esempio, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), quindi \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

L'algoritmo elabora le cifre binarie dell'esponente da sinistra a destra:

Pseudocodice

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // il bit è 1
            result = (result × base) mod mod
        exp = exp >> 1        // scorrimento a destra (divide per 2)
        base = (base × base) mod mod
    return result

Formule Chiave

Come Usare il Calcolatore di Esponenziazione Modulare

1. Inserisci la base (a): Questo è il numero che vuoi elevare a potenza. Può essere positivo o negativo. Ad esempio, inserisci 7 per calcolare 7^256 mod 13.
2. Inserisci l'esponente (b): Deve essere un numero intero non negativo. Rappresenta la potenza. Per le applicazioni crittografiche, questo può essere molto grande (il calcolatore supporta fino a 10^18).
3. Inserisci il modulo (n): Deve essere un numero intero positivo. È il numero per cui dividi per ottenere il resto. In RSA, questo è solitamente il prodotto di due grandi numeri primi.
4. Clicca su Calcola: Il calcolatore computa a^b mod n usando l'esponenziazione binaria e mostra il risultato istantaneamente.
5. Guarda l'animazione: Premi Riproduci per osservare l'algoritmo di esponenziazione binaria in esecuzione passo dopo passo. Ogni bit dell'esponente viene elaborato in sequenza, mostrando se l'algoritmo eleva al quadrato o eleva al quadrato e moltiplica.
6. Controlla la traccia: La tabella passo-passo mostra ogni calcolo intermedio e il confronto dell'efficienza mostra quanto sia più veloce l'esponenziazione binaria rispetto alla moltiplicazione ripetuta ingenua.

Perché l'Esponenziazione Binaria è Veloce

Considera di calcolare \(2^{1000} \bmod 13\). L'approccio ingenuo richiede 999 moltiplicazioni. L'esponenziazione binaria converte 1000 in binario (1111101000), che ha 10 bit. Necessita al massimo di 9 elevamenti al quadrato più alcune moltiplicazioni per ogni bit '1' — circa 15 operazioni in totale. Si tratta di circa il 98,5% di operazioni in meno. Per esponenti su scala crittografica con centinaia di cifre, la differenza è astronomica: il metodo binario richiede migliaia di operazioni dove quello ingenuo richiederebbe più operazioni di quanti siano gli atomi nell'universo.

FAQ

Operazioni matematiche avanzate:

• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Semplificatore di Algebra Booleana Nuovo
• Calcolatore del Teorema Centrale del Limite
• Calcolatore del Teorema Cinese del Resto
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Frazioni Continue
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore di Entropia
• Calcolatore della funzione di errore Popolare
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• Calcolatore di Esponenti (Alta Precisione)
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatrice del Fattoriale Popolare
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore di Colorazione di Grafi Nuovo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore del tempo di dimezzamento
• Verificatore di Cammino Hamiltoniano Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore dell'Albero Ricoprente Minimo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore del Principio dei Cassetti
• Verificatore di Grafo Planare Nuovo
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatore Radice Primitiva
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatore di Anelli e Campi Nuovo
• Calcolatore di Arrotondamento Popolare
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche
• Calcolatore di Teoria degli Insiemi
• Calcolatore di Cifre Significative Nuovo
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore di Numeri di Stirling
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Calcolatore di Ordinamento Topologico Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Generatore di Tabella di Verità
• Generatore di Diagramma di Venn (3 Insiemi)
• Calcolatrice numeri grandi Nuovo