Vai al contenuto
OneKitly

Sette alla 256 ha 217 cifre e non se ne scrive nessuna

Pubblicato il 27/10/2026 · 3 min di lettura · Calcolatrici quotidiane

Daniel Okonkwo

Daniel Okonkwo — Sviluppatore front-end e redattore Tech presso OneKitly

Performance web · Formati di file

Verificato su 2 fonti

Vedi il profilo →
In breve

Sette elevato alla 256 è un numero di 217 cifre, e trovarne il resto nella divisione per tredici non ne richiede nessuna. Il trucco è che il resto si può prendere a ogni passo: eleva sette al quadrato ottenendo 49, riduci a 10, eleva al quadrato ottenendo 100, riduci a 9, e prosegui — otto elevazioni in tutto, perché 256 è due alla ottava, e la risposta è 9. Lo stesso metodo tratta 2¹⁰⁰⁰ modulo 1.000.000.007 e restituisce 688.423.210 mentre il valore onesto ha 302 cifre. Nessun numero intermedio supera mai il quadrato del modulo, ed è ciò che rende il calcolo possibile su una macchina con interi di dimensione fissa.

Pubblicità

7²⁵⁶ mod 13 fa 9, e 2¹⁰⁰⁰ mod 1.000.000.007 fa 688.423.210. Entrambi escono da otto o dieci elevazioni al quadrato, senza che alcun numero del calcolo superi il quadrato del modulo.

Otto moltiplicazioni invece di duecentocinquantacinque

Calcolare una potenza per moltiplicazioni ripetute costa un passo per unità di esponente. Elevare al quadrato raddoppia l'esponente ogni volta, quindi arrivare a 256 richiede otto passi e non 255, e arrivare a un esponente di trecento cifre ne richiede circa mille. Un esponente che non è potenza di due si tratta scrivendolo in binario ed elevando al quadrato a ogni bit, moltiplicando per la base dove il bit vale uno — da cui la descrizione comune del metodo come lettura delle cifre binarie dell'esponente da un capo all'altro. Il costo è proporzionale al numero di bit dell'esponente, non all'esponente stesso.

Perché quegli otto passi richiedono un tempo costante

Ogni valore intermedio è ridotto subito, quindi resta sotto il modulo e il suo quadrato sta nel doppio della larghezza del modulo. Quel limite spiega perché il lavoro per passo non cresca con l'esponente, e perché un'implementazione possa dimensionare la propria aritmetica una volta e non tornarci più. Spiega anche il fallimento clamoroso dell'alternativa ingenua: calcolare prima il numero a 217 cifre e ridurre alla fine è matematicamente corretto e richiede aritmetica a precisione arbitraria, diverse centinaia di byte per valore e molto più tempo dell'intero calcolo modulare.

Cosa evita la scorciatoia
EspressioneCifre se scritto per interoRisultato
7²⁵⁶ mod 132179
2¹⁰⁰⁰ mod 1.000.000.007302688.423.210
Calcolatore di esponenziazione modulareCalcola aᵇ mod n in modo efficiente con esponenziazione rapida (elevamento al quadrato) e interi grandi: anche potenze enormi si riducono in una frazione di secondo. Normalizza prima una base negativa o troppo grande nell'intervallo 0…n−1 e gestisce esponenti negativi quando la base è invertibile modulo n. È l'operazione centrale di RSA, Diffie–Hellman e dei test di primalità.Prova lo strumento →
Pubblicità

Domande frequenti

Perché 1.000.000.007 si usa così spesso come modulo?
Perché è primo, appena sotto il miliardo, e il suo quadrato sta in un intero a sessantaquattro bit. Essere primo significa che ogni valore non nullo ha un inverso moltiplicativo: la divisione funziona e nulla degenera. Stare appena sotto il miliardo mantiene leggibili i risultati e rende rare le collisioni in un uso di tipo hash. Che il suo quadrato stia in una parola macchina consente di moltiplicare due valori ridotti senza traboccamento e senza aritmetica a precisione arbitraria. Quelle tre proprietà insieme spiegano da sole la frequenza di questo numero negli enunciati di programmazione competitiva.
Il tempo di calcolo lascia trapelare qualcosa?
Può, ed è una classe di attacco reale, non una preoccupazione teorica. La versione ingenua moltiplica solo dove un bit dell'esponente vale uno, quindi il tempo di esecuzione dipende da quanti bit sono a uno — e quando l'esponente è una chiave privata, quella è informazione che lascia la macchina attraverso l'orologio. Le implementazioni serie eseguono perciò la moltiplicazione senza condizione e scartano il risultato quando il bit è zero, pagando un costo costante per rendere il tempo indipendente dal segreto. La stessa disciplina compare ovunque una diramazione dipenda da dati privati.

Articoli che potrebbero interessarti

Tutte le guide →

Strumenti correlati

Fonti

Hai notato un errore in questo articolo?