Use o Algoritmo da Exponenciação Binária para encontrar
19^53(bmod 503) e 141^47(bmod 1537)

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
19^53bmod 503 e 141^47bmod 1537
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:
  1. Saber converter o expoente em binário.
  2. Fazer “squarings” (elevar ao quadrado) repetidos, sempre reduzindo módulo N.
  3. Acumular o resultado só quando o bit do expoente for 1.

Passo 2

Teoria na prática – Exponenciação Binária:
  1. Representa o expoente em binário, do bit menos significativo (LSB) ao mais (MSB).
  2. Começa com resultado e base .
  3. Para cada bit de :
    • Se o bit for 1, faz .
    • Em todo caso, faz .
    • Shift do expoente (divide por 2).
      No fim, é .

Passo 3

Calcular 19^1 &equiv 19 pmod503, 19^2 &equiv 19^2 = 361 pmod503, 19^4 &equiv 361^2 = 130321 equiv 44 pmod503, 19^8 &equiv 44^2 = 1936 equiv 427 pmod503, 19^16 &equiv 427^2 = 182329 equiv 243 pmod503, 19^32 &equiv 243^2 = 59049 equiv 198 pmod503
  1. Expoente: 19^53bmod 503 ;=; 19^32times19^16times19^4times19^1 bmod 503 (ou seja, bits nas posições 198times243 &equiv 329, 329times44 &equiv 392, 392times19 &equiv 406 ).
  2. Vamos anotar potências de 19 ao quadrado, reduzidas em cada passo:
  3. Agora multiplico só as potências cujos bits de 53 valem 1 (32,16,4,1): Fazendo passo a passo (tudo ):

Passo 4

Calcular 141^1 &equiv 141, 141^2 &equiv 19881 equiv 1437, 141^4 &equiv 1437^2 equiv 778, 141^8 &equiv 778^2 equiv 1243, 141^16 &equiv 1243^2 equiv 364, 141^32 &equiv 364^2 equiv 314
  1. Expoente: 314times1243 &equiv 1441, 1441times778 &equiv 625, 625times1437 &equiv 517, 517times141 &equiv 658 (bits em ).
  2. Potências de 141 ao quadrado (mód 1537):
  3. Multiplico as potências onde o bit é 1 (32,8,4,2,1):

Resposta

19^53 bmod 503 = 406, 141^47 bmod 1537 = 658

Exercícios relacionados