aula01_2010

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).


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


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)


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.


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.

Documents

aula01_2010