Conteúdo principal

Exponenciação modular rápida

Google Sala de Aula

Como podemos calcular A^B mod C rapidamente se if B é uma potência de 2 ?

Usando as regras de multiplicação modular:

ou seja, A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

Podemos usar isto para calcular 7 ^ 256 mod 13 rapidamente

7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13

Podemos substituir nosso resultado anterior por 7 ^ 1 mod 13 nesta equação.

7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10

7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13

Podemos substituir nosso resultado anterior por 7 ^ 2 mod 13 nesta equação.

7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9

7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13

Podemos substituir nosso resultado anterior por 7 ^ 4 mod 13 nesta equação.

7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3

Continuamos dessa forma, substituindo os resultados anteriores em nossas equações.

... depois 5 repetições, temos:

7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9

Isto nos dá um método para calcular A^B mod C rapidamente desde que B seja uma potência de 2.

Mesmo assim, nós precisamos de um método rápido para exponenciação modular quando B não é uma potência de 2.

Como nós podemos calcular A^B mod C rapidamente para qualquer B ?

Passo 1: Divida B em potências de 2 escrevendo-o em binário

Comece com o dígito mais à direita, sendo k = 0 e para cada dígito:

Se o dígito for 1, precisaremos de uma parte para 2 ^ k, caso contrário não precisaremos
Some 1 em k e mova para a esquerda para o próximo dígito

Passo 2: Calcule mod C das potências de dois ≤ B

5^1 mod 19 = 5

5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6

5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17

5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4

5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16

5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9

5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5

Etapa 3: Use as propriedades de multiplicação modular para combinar os valores calculados de mod C

5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
  5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
  5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
  5^117 mod 19 = 61200 mod 19 = 1
  5^117 mod 19 = 1

Notas:

Existem outras técnicas de otimização, mas estão fora do escopo deste artigo. Deve-se notar que ao realizamos a exponenciação modular em criptografia, não é incomum usar expoentes de B > 1000 bits.

Quer participar da conversa?

Entrar

Classificar por:

Ana
Publicado há há 5 anos. Link direto para a postagem “Quero saber como acho os ...” de Ana
Quero saber como acho os 12 últimos dígitos da expressão 2^17179869184
Botão para a página de cadastroBotão para a página de cadastro
(1 voto)
Resposta

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Computer science theory