El número 2^100 es 1267650600228229401496703205376, treinta y un dígitos, y la pantalla lo imprime como 1.2676506002282⋅10+30. Pide 2^100 mod 7 en la misma ventana y la respuesta es 0. Pide 2^4 mod 7 y es 2, que es la correcta: 2^3 = 8 ≡ 1 (mod 7), así que 2^99 ≡ 1 y 2^100 ≡ 2, o equivalentemente 2^6 ≡ 1 y 100 mod 6 = 4 reducen toda la cuestión a 2^4 mod 7.
La potencia no tiene nada de malo; el resto sí. Un double guarda cincuenta y tres bits, así que el valor representable más cercano a 2^100/7 se desvía en torno a 10^13, y un resto calculado como a − 7·floor(a/7) hereda un error mucho mayor que el módulo. El método correcto nunca deja crecer el número: reducir primero y elevar después, que es exactamente lo que hace la exponenciación modular en toda biblioteca criptográfica, y la razón por la que RSA puede trabajar con números de mil bits en hardware que guarda cincuenta y tres. Es el mismo techo que hace de 2^53 el último contador entero exacto.
Respuesta
0
Cómo leerla
2^100 mod 7 en el banco de trabajo: la respuesta de la máquina, no la de la aritmética. El segundo enlace es 2^6 mod 7 = 1, el período; el tercero es la cuestión reducida 2^4 mod 7 = 2, que es el valor verdadero.
Fuente
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
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.