Algebra A - Aula 01Algoritmo da divisao de Euclides e Algoritmo
Euclideano estendido
Elaine Pimentel
Departamento de Matematica, UFMG, Brazil
2o Semestre - 2010
Introducao
I Objetivo: estudar o metodo de criptografia de chaves publicasconhecido como RSA.
I E necessario o estudo de alguns conceitos de uma area damatematica chamada Teoria de numeros.
I Espera-se desenvolver o raciocınio logico matematicointroduzindo metodos de prova de teoremas como inducaomatematica e demonstracao por absurdo.
I E um curso de matematica para cientistas da computacao.
Criptografia
I Criptografia: estuda os metodos para codificar uma mensagemde modo que so seu destinatario legıtimo consiga interpreta-la.
I Primordios: Cesar (translacao do alfabeto).
I Criptoanalise: arte de decifrar codigos secretos.
I Decodificar x Decifrar (quebrar).
Criptografia
I Substituir letras por sımbolos - contagem de frequencia:I vogais sao mais frequentes;I letra mais frequente: A;I monossılabo de uma letra = vogal;I consoantes mais frequentes: S e M
Metodo de contagem de frequencia de caracteres pode serusado para decifrar inscricoes antigas.
I Computadores: metodo de cifragem completamente inseguro(polinomial).
I Internet e criptografia: seguranca, assinatura.
I Chave publica: saber codificar nao implica saber decodificar!
Criptografia RSA
I RSA: Rivest, Shamir, Adleman (M.I.T.) 1978.
I Codificacao: basta conhecer o produto de dois primos(n = pq). n e chamado chave publica.
I Decodificacao: precisamos conhecer p e q (chave dedecodificacao).
I Decifrar RSA = fatoracao de n. Se n possui 150 algarismosou mais, fatora-lo levaria milhares de anos.
I Obs: E difıcil determinar os fatores primos de um numerocomposto, mas e possıvel verificar se um numero e primo oucomposto sem tentar fatora-lo.
I Teoria de numeros: parte da matematica que estuda numerosinteiros.
Computacao algebrica
I Chave publica do RSA: multiplica-se dois primos muitograndes.
I Pascal, C: nao permitem lidar com numeros dessa magnitude.
I Computacao algebrica: trata do calculo exato com inteiros,fracoes, etc. Exemplo: Mathematica, Maple.
I Inteiro de tamanho indeterminado: de tamanho flexıvel,grandes o suficiente. Restricoes: tamanho da memoria,estruturas de dados (vetores de tamanhos pre-fixados).
I Inteiros = listas! Algarismos = elemento da lista; operacoesde soma e multiplicacao: usuais, como com lapis e papel.Divisao e mais complicado...
Algoritmos
I Algoritmo = processo de calculo baseado em regras formais.
I Especificacao de um algoritmo: entrada + instrucoes + saıda.I Perguntas:
I ao executarmos um conjunto de instrucoes, semprechegaremos a um resultado? (ponto fixo)
I o resultado obtido e sempre o desejado? (semantica)
Algoritmo da divisao
I Objetivo: encontrar o quociente q e o resto r (saıda) dadivisao entre dois inteiros positivos a e b (entrada):
a = bq + r 0 ≤ r < b.
I Algoritmo da divisao:Etapa 1: q = 0; r = aEtapa 2: Se r < b, pare. Nesse caso, o quociente e q e oresto r .Etapa 3: Se r ≥ b, faca r := r − b, q := q + 1 e volte aEtapa 2.
Algoritmo da divisao
I Observacoes:
1. O algoritmo sempre para: sequencia decrescente de numerosinteiros positivos.
2. O resultado da aplicacao do algoritmo corresponde asespecificacoes da saıda (trivialmente).
3. O algoritmo e extremamente ineficiente, em especial sea >> b.
Teorema da DivisaoTeorema de divisao: Sejam a e b inteiros positivos. Existemnumeros inteiros q e r tais que
a = bq + r 0 ≤ r < b
Alem disso, q e r sao unicos.Prova: Unicidade - Sejam q, q′, r , r ′ tais que
a = bq + r 0 ≤ r < b (1)
a = bq′ + r ′ 0 ≤ r ′ < b (2)
Subtraindo-se (1) de (2), obtemos:
r − r ′ = b(q′ − q)
Ora, mas 0 ≤ r , r ′ < b e portanto 0 ≤ r − r ′ < b. Ou seja,
0 ≤ b(q′ − q) < b
Como b > 0, temos0 ≤ q − q′ < 1
ou seja, q − q′ = 0→ q = q′ e r = r ′.
Algoritmo Euclideano
I Objetivo: Calcular o mdc entre dois numeros inteiros.I Definicao: o maximo divisor comum entre a e b e o numero d
tal que:I d |a (ou d e divisor de a)I d |bI se d ′ e divisor de a e b, entao d ′|d .
I Escrevemos d = mdc(a, b). Se mdc(a, b) = 1, dizemos que ae b sao primos entre si.
Algoritmo Euclideano
I Dados dois numeros inteiros positivos a e b tais que a ≥ b,divide-se a por b, encontrando resto r1. Se r1 6= 0, dividimosb por r1, obtendo resto r2. Se r2 6= 0, dividimos r1 por r2 eassim por diante.O ultimo resto diferente de zero dessa sequencia de divisoes eo mdc(a, b).
I Exemplo:1234 54 46 8 6 2
46 8 6 2 0Ou seja, mdc(1234, 54) = 2.
Algoritmo euclideano
Perguntas:
1. Por que o ultimo resto nao nulo e o mdc?
2. Por que o algoritmo para?
a = bq1 + r1 e 0 ≤ r1 < bb = r1q2 + r2 e 0 ≤ r2 < r1
r1 = r2q3 + r3 e 0 ≤ r3 < r2
r2 = r3q4 + r4 e 0 ≤ r4 < r3...
...
Algoritmo euclideano
Respostas:
I Segunda pergunta: observe que
b > r1 > r2 > . . . ≥ 0
Como essa sequencia e finita, o algoritmo sempre para. Maisainda, o numero de divisoes efetuadas e no maximo b (porque?).
I Primeira pergunta: demonstracao do algoritmo euclideano
Demonstracao do algoritmo euclideano
LemaSejam a e b numeros inteiros positivos. Se existem inteiros g e stais que a = bg + s, entao mdc(a, b) = mdc(b, s).
Prova Sejam
d1 = mdc(a, b) e d2 = mdc(b, s).
Afirmamos que d1 ≤ d2. De fato, existem inteiros positivos u e vtais que:
a = d1u e b = d1v
Substituindo a e b na equacao a = bg + s obtemos
s = d1u − d1vg = d1(u − vg).
Demonstracao do algoritmo euclideano
Ou seja, d1 e um divisor comum de b e s. Mas d2 e o maior divisorde b e s e portanto (por definicao) d1 ≤ d2 como querıamos.Seguindo um argumento semelhante, podemos provar o inverso, ouseja, d2 ≤ d1. Em outras palavras, d1 = d2
Demonstracao do algoritmo euclideano
TeoremaDados a e b inteiros positivos, o ultimo resto diferente de zero dasequencia de divisoes dada pelo algoritmo euclideano para a e b eo maximo divisor comum entre a e b.
Provaa = bq1 + r1 e 0 ≤ r1 < bb = r1q2 + r2 e 0 ≤ r2 < r1
r1 = r2q3 + r3 e 0 ≤ r3 < r2
r2 = r3q4 + r4 e 0 ≤ r4 < r3...
...rn−2 = rn−1qn e rn = 0
Da ultima linha, temos que rn−1 divide rn−2 e portantomdc(rn−1, rn−2) = rn−1. Aplicando sucessivamente o lema 1,temos que mdc(a, b) = rn−1.
Algoritmo euclideano estendido
TeoremaSejam a e b inteiros positivos e seja d o maximo divisor comumentre a e b. Existem inteiros α e β tais que
αa + βb = d .
Exemplo: Sejam a = 1234 e b = 54. Temos que:
1234 = 54.22 + 46 ou seja, 46 = 1234− 54.22
54 = 46.1 + 8 ou seja, 8 = 54− 46.1
Logo,8 = 54− 46.1 = 54− (1234− 54.22).1
= 54(1 + 22.1) + 1234.(−1)= 54.(23) + 1234.(−1)
Algoritmo euclideano estendido
Logo,
46 = 8.5 + 6 → 6 = 46− 8.5= (1234− 54.22)− (54.(23) + 1234.(−1)).5= 1234.(6) + 54.(−22− (23).5)= 1234.(6) + 54.(−137)
8 = 6.1 + 2 → 2 = 8− 6= (54.(23) + 1234.(−1))− (1234.(6) + 54.(−137))= 1234(−1− 6) + 54(23 + 137)= 1234(−7) + 54(160)
E portanto, α = −7 e β = 160.
Algoritmo euclideano estendido
Obs. α e β nao sao unicos.Pergunta: para que serve calcular α e β?Resposta:
I unicidade de fatoracao de um inteiro;
I RSA depende de um metodo eficiente de calculo de α e β.
Exercıcios propostos - Capıtulo 1
1. Livro texto: 2 a 7.
Recommended