Sete elevado a 256 tem 217 algarismos e não se escreve nenhum
Publicado a 27/10/2026 · 3 min de leitura · Calculadoras do dia a dia
Daniel Okonkwo — Programador front-end e redator de Tecnologia na OneKitly
Desempenho web · Formatos de ficheiro
Verificado a partir de 2 fontes
Sete elevado a 256 é um número de 217 algarismos, e achar o seu resto na divisão por treze não exige nenhum. O truque é que o resto se pode tomar em cada passo: eleva sete ao quadrado para obter 49, reduz a 10, eleva ao quadrado para obter 100, reduz a 9, e continua — oito elevações ao todo, porque 256 é dois elevado a oito, e a resposta é 9. O mesmo método trata 2¹⁰⁰⁰ módulo 1.000.000.007 e devolve 688.423.210 enquanto o valor honesto tem 302 algarismos. Nenhum número intermédio excede nunca o quadrado do módulo, e é isso que torna o cálculo possível numa máquina com inteiros de tamanho fixo.
7²⁵⁶ mod 13 é 9, e 2¹⁰⁰⁰ mod 1.000.000.007 é 688.423.210. Ambos saem de oito ou dez elevações ao quadrado, sem que nenhum número do cálculo exceda o quadrado do módulo.
Oito multiplicações em vez de duzentas e cinquenta e cinco
Calcular uma potência por multiplicações repetidas custa um passo por unidade de expoente. Elevar ao quadrado duplica o expoente de cada vez, pelo que chegar a 256 leva oito passos e não 255, e chegar a um expoente de trezentos algarismos leva cerca de mil. Um expoente que não é potência de dois trata-se escrevendo-o em binário e elevando ao quadrado em cada bit, multiplicando pela base onde o bit vale um — daí o método se descrever muitas vezes como ler os algarismos binários do expoente de uma ponta à outra. O custo é proporcional ao número de bits do expoente, não ao expoente em si.
Porque esses oito passos levam um tempo constante
Cada valor intermédio é reduzido de imediato, pelo que fica abaixo do módulo e o seu quadrado cabe no dobro da largura do módulo. Esse limite explica que o trabalho por passo não cresça com o expoente, e que uma implementação possa dimensionar a sua aritmética de uma vez e não voltar ao assunto. Explica também o fracasso retumbante da alternativa ingénua: calcular primeiro o número de 217 algarismos e reduzir no fim é matematicamente correto e exige aritmética de precisão arbitrária, várias centenas de bytes por valor e muito mais tempo do que todo o cálculo modular.
| Expressão | Algarismos se escrito por inteiro | Resultado |
|---|---|---|
| 7²⁵⁶ mod 13 | 217 | 9 |
| 2¹⁰⁰⁰ mod 1.000.000.007 | 302 | 688.423.210 |
Perguntas frequentes
- Porque se usa tantas vezes 1.000.000.007 como módulo?
- Porque é primo, mesmo abaixo de mil milhões, e o seu quadrado cabe num inteiro de sessenta e quatro bits. Ser primo significa que todo o valor não nulo tem inverso multiplicativo: a divisão funciona e nada degenera. Estar mesmo abaixo de mil milhões mantém os resultados legíveis e torna raras as colisões num uso do tipo dispersão. Que o seu quadrado caiba numa palavra de máquina permite multiplicar dois valores reduzidos sem transbordo e sem aritmética de precisão arbitrária. Essas três propriedades juntas explicam sozinhas a frequência deste número nos enunciados de programação competitiva.
- O tempo de cálculo deixa fugir alguma coisa?
- Pode, e é uma classe de ataque real, não uma inquietação teórica. A versão ingénua só multiplica onde um bit do expoente vale um, pelo que o tempo de execução depende de quantos bits estão a um — e quando o expoente é uma chave privada, isso é informação a sair da máquina pelo relógio. As implementações sérias realizam portanto a multiplicação sem condição e descartam o resultado quando o bit é zero, pagando um custo constante para tornar o tempo independente do segredo. A mesma disciplina aparece onde quer que uma bifurcação dependa de dados privados.
Artigos que podem interessar-lhe
Todos os guias →Ferramentas relacionadas
Fontes
Detetaste um erro neste artigo?