Calcolatore Esponenziazione Modulare

Calcola l'esponenziazione modulare a^b mod n in modo efficiente utilizzando l'algoritmo di esponenziazione binaria (esponenziazione veloce). Inserisci la base, l'esponente e il modulo per ottenere risultati istantanei con una scomposizione passo dopo passo del metodo "square-and-multiply", la visualizzazione della decomposizione binaria e il contesto crittografico.

Embed Calcolatore Esponenziazione Modulare Widget

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

🔐

Cifratura RSA

Cifra e decifra messaggi usando l'esponenziazione modulare con grandi prodotti di numeri primi

🤝

Diffie-Hellman

Protocollo di scambio di chiavi che calcola g^a mod p per segreti condivisi sicuri

✍

Firme Digitali

DSA, ECDSA e EdDSA si basano tutti sull'esponenziazione modulare

🧪

Test di Primalità

I test di Fermat e Miller-Rabin usano a^(n-1) mod n per verificare la primalità

🏆

Programmazione Competitiva

L'aritmetica modulare con fast power è essenziale per i problemi di gara

🔗

Blockchain

La proof-of-work e l'hashing crittografico si basano sull'aritmetica 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:

Passaggio 1: Converti l'esponente \(b\) in binario.

Passaggio 2: Inizializza il risultato = 1 (o = base se il primo bit è 1).

Passaggio 3: Per ogni bit successivo: Eleva al Quadrato il risultato (mod n). Se il bit è 1, moltiplica anche per la base (mod n).

Passaggio 4: Dopo che tutti i bit sono stati elaborati, il risultato è \(a^b \bmod n\).

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

Proprietà	Formula	Descrizione
Esponenziazione Modulare	\(a^b \bmod n\)	Resto di a^b diviso n
Piccolo Teorema di Fermat	\(a^{p-1} \equiv 1 \pmod{p}\)	Per p primo e mcd(a,p)=1
Teorema di Eulero	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Per mcd(a,n)=1, dove φ è la funzione totiente di Eulero
Complessità Metodo Binario	\(O(\log b)\) moltiplicazioni	Al massimo 2·log₂(b) moltiplicazioni modulari
Cifratura RSA	\(c = m^e \bmod n\)	Cifra il messaggio m con la chiave pubblica (e, n)
Decifratura RSA	\(m = c^d \bmod n\)	Decifra il crittogramma c con la chiave privata d

Come Usare il Calcolatore di Esponenziazione Modulare

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.
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).
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.
Clicca su Calcola: Il calcolatore computa a^b mod n usando l'esponenziazione binaria e mostra il risultato istantaneamente.
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.
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

Cos'è l'esponenziazione modulare?

L'esponenziazione modulare calcola (a^b) mod n — eleva una base a un esponente, quindi prende il resto della divisione per un modulo. È l'operazione principale nella crittografia a chiave pubblica (RSA, Diffie-Hellman, ElGamal) ed è ampiamente utilizzata nella teoria dei numeri, nella programmazione competitiva e nell'informatica. Il metodo dell'esponenziazione binaria calcola questo in modo efficiente in O(log b) moltiplicazioni.

Come funziona l'esponenziazione binaria (elevamento a potenza al quadrato)?

L'esponenziazione binaria converte l'esponente nella sua rappresentazione binaria, quindi elabora ogni bit da sinistra a destra (o da destra a sinistra). Per ogni bit, eleva al quadrato il risultato corrente modulo n. Se il bit è 1, moltiplica ulteriormente il risultato per la base modulo n. Ciò riduce il numero di moltiplicazioni da b−1 (metodo ingenuo) a un massimo di 2×log₂(b), rendendo possibile il calcolo con esponenti enormi.

Perché l'esponenziazione modulare è importante nella crittografia?

La cifratura RSA calcola c = m^e mod n per la cifratura e m = c^d mod n per la decifratura, dove n è il prodotto di due grandi numeri primi e gli esponenti possono essere lunghi centinaia di cifre. Senza la veloce esponenziazione modulare, queste operazioni sarebbero computazionalmente impossibili. La sicurezza si basa sul fatto che l'operazione inversa (calcolo del logaritmo discreto) è ritenuta computazionalmente impraticabile.

La base può essere negativa?

Sì, le basi negative sono completamente supportate. Il calcolatore riduce prima la base modulo n (utilizzando l'aritmetica modulare di Python, che restituisce sempre un risultato non negativo per n positivo). Ad esempio, (−3)^2 mod 7 = 9 mod 7 = 2. Non si verificano mai risultati negativi perché la riduzione modulare produce sempre un valore nell'intervallo [0, n−1].

Cosa succede quando il modulo è 1?

Qualsiasi numero intero modulo 1 è uguale a 0. Questo perché dividendo qualsiasi intero per 1 si ottiene l'intero stesso con un resto di 0. Quindi a^b mod 1 = 0 per tutti i valori di a e b. Il calcolatore gestisce questo come un caso speciale.

Cita questo contenuto, pagina o strumento come:

"Calcolatore Esponenziazione Modulare" su https://MiniWebtool.com/it/calcolatore-esponenziazione-modulare/ di MiniWebtool, https://MiniWebtool.com/

dal team miniwebtool. Aggiornato: 2026-04-16

API per sviluppatori disponibile: Esegui questo strumento dalla tua app, automazione o agente con una richiesta HTTP JSON. Vedi documentazione API

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Calcolatore Esponenziazione Modulare

Calcolatore Esponenziazione Modulare

Applicazioni dell'Esponenziazione Modulare

Come Funziona l'Algoritmo di Esponenziazione Binaria

Pseudocodice

Formule Chiave

Come Usare il Calcolatore di Esponenziazione Modulare

Perché l'Esponenziazione Binaria è Veloce

FAQ

Operazioni matematiche avanzate:

Strumenti in primo piano: