O número 2^100 é 1267650600228229401496703205376, trinta e um dígitos, e a tela o imprime como 1.2676506002282⋅10+30. Peça 2^100 mod 7 na mesma janela e a resposta é 0. Peça 2^4 mod 7 e é 2, que é a correta: 2^3 = 8 ≡ 1 (mod 7), então 2^99 ≡ 1 e 2^100 ≡ 2, ou equivalentemente 2^6 ≡ 1 e 100 mod 6 = 4 reduzem toda a questão a 2^4 mod 7.
A potência não tem nada de errado; o resto tem. Um double guarda cinquenta e três bits, então o valor representável mais próximo de 2^100/7 se desvia em torno de 10^13, e um resto calculado como a − 7·floor(a/7) herda um erro muito maior que o módulo. O método correto nunca deixa o número crescer: reduzir primeiro e elevar depois, que é exatamente o que a exponenciação modular faz em toda biblioteca criptográfica, e a razão pela qual o RSA pode trabalhar com números de mil bits em hardware que guarda cinquenta e três. É o mesmo teto que faz de 2^53 o último contador inteiro exato.
Resposta
0
Como ler
2^100 mod 7 na área de trabalho: a resposta da máquina, não a da aritmética. O segundo link é 2^6 mod 7 = 1, o período; o terceiro é a questão reduzida 2^4 mod 7 = 2, que é o valor verdadeiro.
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
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.