Use o Algoritmo da Exponenciação Binária para encontrar
Passo 1
Beleza, o que a gente tem aqui é um exercício de Exponenciação Binária (ou “fast exponentiation”) em aritmética modular. O enunciado pede pra calcular
Qual é o conteúdo?
- Trabalhar com potências grandes, mas fazendo tudo mod alguma coisa (aqui 503 e 1537).
- Usar o Algoritmo da Exponenciação Binária: ao invés de multiplicar 53 vezes “19×19×…”, a gente vai “dobrar” potências e usar os bits do expoente.
O que vamos precisar:
- Saber converter o expoente em binário.
- Fazer “squarings” (elevar ao quadrado) repetidos, sempre reduzindo módulo N.
- Acumular o resultado só quando o bit do expoente for 1.
Passo 2
Teoria na prática – Exponenciação Binária:
- Representa o expoente em binário, do bit menos significativo (LSB) ao mais (MSB).
- Começa com resultado
e base . - Para cada bit de
: - Se o bit for 1, faz
. - Em todo caso, faz
. - Shift do expoente (divide por 2).
No fim,é .
- Se o bit for 1, faz
Passo 3
Calcular
- Expoente:
(ou seja, bits nas posições ). - Vamos anotar potências de 19 ao quadrado, reduzidas em cada passo:
- Agora multiplico só as potências cujos bits de 53 valem 1 (32,16,4,1):
Fazendo passo a passo (tudo ):
Passo 4
Calcular
- Expoente:
(bits em ). - Potências de 141 ao quadrado (mód 1537):
- Multiplico as potências onde o bit é 1 (32,8,4,2,1):