aula01_2010

Prévia do material em texto

A´lgebra A - Aula 01
Algoritmo da divisa˜o de Euclides e Algoritmo
Euclideano estendido
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Introduc¸a˜o
I Objetivo: estudar o me´todo de criptografia de chaves pu´blicas
conhecido como RSA.
I E´ necessa´rio o estudo de alguns conceitos de uma a´rea da
matema´tica chamada Teoria de nu´meros.
I Espera-se desenvolver o racioc´ınio lo´gico matema´tico
introduzindo me´todos de prova de teoremas como induc¸a˜o
matema´tica e demonstrac¸a˜o por absurdo.
I E´ um curso de matema´tica para cientistas da computac¸a˜o.
Criptografia
I Criptografia: estuda os me´todos para codificar uma mensagem
de modo que so´ seu destinata´rio leg´ıtimo consiga interpreta´-la.
I Primo´rdios: Cesar (translac¸a˜o do alfabeto).
I Criptoana´lise: arte de decifrar co´digos secretos.
I Decodificar x Decifrar (quebrar).
Criptografia
I Substituir letras por s´ımbolos - contagem de frequeˆncia:
I vogais sa˜o mais frequentes;
I letra mais frequente: A;
I monoss´ılabo de uma letra = vogal;
I consoantes mais frequentes: S e M
Me´todo de contagem de frequeˆncia de caracteres pode ser
usado para decifrar inscric¸o˜es antigas.
I Computadores: me´todo de cifragem completamente inseguro
(polinomial).
I Internet e criptografia: seguranc¸a, assinatura.
I Chave pu´blica: saber codificar na˜o implica saber decodificar!
Criptografia RSA
I RSA: Rivest, Shamir, Adleman (M.I.T.) 1978.
I Codificac¸a˜o: basta conhecer o produto de dois primos
(n = pq). n e´ chamado chave pu´blica.
I Decodificac¸a˜o: precisamos conhecer p e q (chave de
decodificac¸a˜o).
I Decifrar RSA = fatorac¸a˜o de n. Se n possui 150 algarismos
ou mais, fatora´-lo levaria milhares de anos.
I Obs: E´ dif´ıcil determinar os fatores primos de um nu´mero
composto, mas e´ poss´ıvel verificar se um nu´mero e´ primo ou
composto sem tentar fatora´-lo.
I Teoria de nu´meros: parte da matema´tica que estuda nu´meros
inteiros.
Computac¸a˜o alge´brica
I Chave pu´blica do RSA: multiplica-se dois primos muito
grandes.
I Pascal, C: na˜o permitem lidar com nu´meros dessa magnitude.
I Computac¸a˜o alge´brica: trata do ca´lculo exato com inteiros,
frac¸o˜es, etc. Exemplo: Mathematica, Maple.
I Inteiro de tamanho indeterminado: de tamanho flex´ıvel,
grandes o suficiente. Restric¸o˜es: tamanho da memo´ria,
estruturas de dados (vetores de tamanhos pre´-fixados).
I Inteiros = listas! Algarismos = elemento da lista; operac¸o˜es
de soma e multiplicac¸a˜o: usuais, como com la´pis e papel.
Divisa˜o e´ mais complicado...
Algoritmos
I Algoritmo = processo de ca´lculo baseado em regras formais.
I Especificac¸a˜o de um algoritmo: entrada + instruc¸o˜es + sa´ıda.
I Perguntas:
I ao executarmos um conjunto de instruc¸o˜es, sempre
chegaremos a um resultado? (ponto fixo)
I o resultado obtido e´ sempre o desejado? (semaˆntica)
Algoritmo da divisa˜o
I Objetivo: encontrar o quociente q e o resto r (sa´ıda) da
divisa˜o entre dois inteiros positivos a e b (entrada):
a = bq + r 0 ≤ r < b.
I Algoritmo da divisa˜o:
Etapa 1: q = 0; r = a
Etapa 2: Se r < b, pare. Nesse caso, o quociente e´ q e o
resto r .
Etapa 3: Se r ≥ b, fac¸a r := r − b, q := q + 1 e volte a`
Etapa 2.
Algoritmo da divisa˜o
I Observac¸o˜es:
1. O algoritmo sempre para: sequeˆncia decrescente de nu´meros
inteiros positivos.
2. O resultado da aplicac¸a˜o do algoritmo corresponde a`s
especificac¸o˜es da sa´ıda (trivialmente).
3. O algoritmo e´ extremamente ineficiente, em especial se
a >> b.
Teorema da Divisa˜o
Teorema de divisa˜o: Sejam a e b inteiros positivos. Existem
nu´meros inteiros q e r tais que
a = bq + r 0 ≤ r < b
Ale´m disso, q e r sa˜o u´nicos.
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, temos
0 ≤ q − q′ < 1
ou seja, q − q′ = 0→ q = q′ e r = r ′.
Algoritmo Euclideano
I Objetivo: Calcular o mdc entre dois nu´meros inteiros.
I Definic¸a˜o: o ma´ximo divisor comum entre a e b e´ o nu´mero d
tal que:
I d |a (ou d e´ divisor de a)
I d |b
I se d ′ e´ divisor de a e b, enta˜o d ′|d .
I Escrevemos d = mdc(a, b). Se mdc(a, b) = 1, dizemos que a
e b sa˜o primos entre si.
Algoritmo Euclideano
I Dados dois nu´meros inteiros positivos a e b tais que a ≥ b,
divide-se a por b, encontrando resto r1. Se r1 6= 0, dividimos
b por r1, obtendo resto r2. Se r2 6= 0, dividimos r1 por r2 e
assim por diante.
O u´ltimo resto diferente de zero dessa sequeˆncia de diviso˜es e´
o mdc(a, b).
I Exemplo:
1234 54 46 8 6 2
46 8 6 2 0
Ou seja, mdc(1234, 54) = 2.
Algoritmo euclideano
Perguntas:
1. Por que o u´ltimo resto na˜o nulo e´ o mdc?
2. Por que o algoritmo para?
a = bq1 + r1 e 0 ≤ r1 < b
b = 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 sequeˆncia e´ finita, o algoritmo sempre para. Mais
ainda, o nu´mero de diviso˜es efetuadas e´ no ma´ximo b (por
que?).
I Primeira pergunta: demonstrac¸a˜o do algoritmo euclideano
Demonstrac¸a˜o do algoritmo euclideano
Lema
Sejam a e b nu´meros inteiros positivos. Se existem inteiros g e s
tais que a = bg + s, enta˜o 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 v
tais que:
a = d1u e b = d1v
Substituindo a e b na equac¸a˜o a = bg + s obtemos
s = d1u − d1vg = d1(u − vg).
Demonstrac¸a˜o do algoritmo euclideano
Ou seja, d1 e´ um divisor comum de b e s. Mas d2 e´ o maior divisor
de b e s e portanto (por definic¸a˜o) d1 ≤ d2 como quer´ıamos.
Seguindo um argumento semelhante, podemos provar o inverso, ou
seja, d2 ≤ d1. Em outras palavras, d1 = d2
Demonstrac¸a˜o do algoritmo euclideano
Teorema
Dados a e b inteiros positivos, o u´ltimo resto diferente de zero da
sequeˆncia de diviso˜es dada pelo algoritmo euclideano para a e b e´
o ma´ximo divisor comum entre a e b.
Prova
a = bq1 + r1 e 0 ≤ r1 < b
b = 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 u´ltima linha, temos que rn−1 divide rn−2 e portanto
mdc(rn−1, rn−2) = rn−1. Aplicando sucessivamente o lema 1,
temos que mdc(a, b) = rn−1.
Algoritmo euclideano estendido
Teorema
Sejam a e b inteiros positivos e seja d o ma´ximo divisor comum
entre 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 β na˜o sa˜o u´nicos.
Pergunta: para que serve calcular α e β?
Resposta:
I unicidade de fatorac¸a˜o de um inteiro;
I RSA depende de um me´todo eficiente de ca´lculo de α e β.
Exerc´ıcios propostos - Cap´ıtulo 1
1. Livro texto: 2 a 7.