Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 5: Aritmética modular- O que é aritmética modular?
- Operador módulo
- Desafio de Módulo
- Módulo de congruência
- Relação de congruência
- Relações equivalentes
- O teorema do resto do quociente
- Adição e subtração modular
- Adição modular
- Desafio de Módulo (Adição e Subtração)
- Multiplicação modular
- Multiplicação modular
- Exponenciação modular
- Exponenciação modular rápida
- Exponenciação Modular Rápida
- Inversas modulares
- O Algoritmo Euclidiano
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Exponenciação modular
Finalmente, vamos explorar a propriedade da exponenciação:
A^B mod C = ( (A mod C)^B ) mod C
Muitas vezes queremos calcular A^B mod C para grandes valores de B.
Infelizmente, A^B torna-se muito grande até mesmo para valores modestos de B.
Infelizmente, A^B torna-se muito grande até mesmo para valores modestos de B.
Por exemplo:
2^90 = 1.237.940.039.290.000.000.000.000.000
7^256 = 2.213.595.400.050.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 83.794.038.078.300.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 721.264.246.243.000.000.000.000.000
Esses enormes valores, fazem nossas calculadoras e computadores retornarem erros.
Mesmo se não o fizessem, levaria um longo tempo para encontrar o mod destes grandes números diretamente.
Mesmo se não o fizessem, levaria um longo tempo para encontrar o mod destes grandes números diretamente.
O que podemos fazer para reduzir o tamanho dos termos envolvidos e tornar nosso cálculo mais rápido?
Suponha que queremos calcular 2^90 mod 13, mas nós temos uma calculadora que não pode conter nenhum número maior que 2^50.
Aqui está uma estratégia simples de dividir e resolver:
partes menores
regras de exponenciação
2^90 = 2^50 * 2^40
mod C
cada parte
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
2^40 mod 13 = 1099511627776 mod 13 = 3
propriedades de multiplicação modular
combinar as partes
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
Como podemos calcular A ^ B mod C rapidamente se B é uma potência de 2?
Como poderíamos calcular 7 ^ 256 mod 13 usando uma calculadora que não pode conter números maiores que 7 ^ 10?
Poderíamos dividir 7 ^ 256 em 25 partes de 7 ^ 10 e 1 parte de 7 ^ 6, mas isto não seria muito eficiente.
Há uma maneira melhor...
Quer participar da conversa?
"2^50 mod 13 = 1125899906842624 mod 13 = 4 "
Eu não consegui entender como ele descobriu o resto 4 ?Ele utilizou alguma função especifica na calculadora ?
Com numero pequeno é tranquilo, apenas pegaria o valor depois da virgula e multiplicaria por 13 (Ex: 700 mod 13 => 700\13 = 53,84615 logo 0,84615 x 13 = 11 ou seja 700 mod 13= 11).
Mas particularmente este caso, eu não sei fazer.(1 voto)