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 — Sviluppatore front-end e redattore Tech presso OneKitly
Performance web · Formati di file
Verificato su 2 fonti
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.
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.
| Espressione | Cifre se scritto per intero | Risultato |
|---|---|---|
| 7²⁵⁶ mod 13 | 217 | 9 |
| 2¹⁰⁰⁰ mod 1.000.000.007 | 302 | 688.423.210 |
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?