Il numero 2^100 è 1267650600228229401496703205376, trentuno cifre, e lo schermo lo stampa come 1.2676506002282⋅10+30. Chiedi 2^100 mod 7 nella stessa finestra e la risposta è 0. Chiedi 2^4 mod 7 ed è 2, che è quella corretta: 2^3 = 8 ≡ 1 (mod 7), quindi 2^99 ≡ 1 e 2^100 ≡ 2, o equivalentemente 2^6 ≡ 1 e 100 mod 6 = 4 riducono l'intera questione a 2^4 mod 7.
Nulla nella potenza è sbagliato; è il resto a esserlo. Un double memorizza cinquantatré bit, quindi il valore rappresentabile più vicino a 2^100/7 è sbagliato di circa 10^13, e un resto calcolato come a − 7·floor(a/7) eredita un errore molto più grande del modulo. Il metodo corretto non lascia mai crescere il numero: riduci prima, poi eleva, che è esattamente ciò che fa l'esponenziazione modulare in ogni libreria crittografica, e il motivo per cui RSA può lavorare con numeri da mille bit su hardware che ne memorizza cinquantatré. È lo stesso soffitto che rende 2^53 l'ultimo contatore intero esatto.
Risposta
0
Come leggerla
2^100 mod 7 sul banco di lavoro: la risposta della macchina, non quella aritmetica. Il secondo link è 2^6 mod 7 = 1, il periodo; il terzo è la domanda ridotta 2^4 mod 7 = 2, che è il valore vero.
Fonte
2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient
Svolgilo nella calcolatrice
Questi link aprono la calcolatrice giusta con i numeri di questo problema già digitati. La riga sopra è ciò che lo schermo dovrebbe mostrare — verifica tu stesso.