aula04_2010

Prévia do material em texto

A´lgebra A - Aula 04
Equac¸o˜es diofantinas, congrueˆncias lineares
e criptografia
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Equac¸o˜es diofantinas
Equac¸a˜o diofantina: equac¸a˜o em va´rias inco´gnitas com
coeficientes inteiros.
Exemplos: xn + yn = zn, x + y = 2, x3 − 117y 3 = 5
A u´ltima equac¸a˜o na˜o tem soluc¸a˜o:
x3 − 117y 3 ≡ x3 ≡ 5 (mod 9)
Mas:
classes mo´dulo 9: 0 1 2 3 4 5 6 7 8
cubos mo´dulo 9: 0 1 8 0 1 8 0 1 8
Divisa˜o modular
Teorema da inversa˜o A classe a tem inverso em Zn se e somente
se a e n sa˜o primos entre si.
Prova (⇒) Se a tem inverso b:
a.b ≡ 1 (mod n)
Logo, a.b + k.n = 1 e portanto mdc(a, n) = 1.
(⇐) Suponha mdc(a, n) = 1. Logo existem α e β tais que:
α.a + β.n = 1
Ou seja, α.a ≡ 1 (mod n) e portanto a tem inverso em Zn.
U(n)
O conjunto dos elementos de Zn que teˆm inverso e´ muito
importante:
U(n) = {a ∈ Z(n)|mdc(a, n) = 1}
No caso de n = p ser primo,
U(p) = Z(n) \ {0}
Propriedade importante de U(n): esse conjunto e´ fechado com
relac¸a˜o a` multiplicac¸a˜o.
Congrueˆncia linear
Uma congrueˆncia linear e´ uma equac¸a˜o do tipo:
a.x ≡ b (mod n)
onde a, b ∈ Z. A soluc¸a˜o dessa equac¸a˜o e´:
x ≡ α.b (mod n)
onde α e´ o inverso de a mo´dulo n.
Conclusa˜o: Se mdc(a, n) = 1 enta˜o a congrueˆncia linear a.x ≡ b
(mod n) tem uma e so´ uma soluc¸a˜o em Zn.
Sistemas de congrueˆncias lineares
Considere a seguinte congrueˆncia linear:
ax ≡ b (mod n) (1)
Se x0 e´ soluc¸a˜o de (1) e x1 ≡ x0 (mod n), enta˜o
ax1 ≡ ax0 ≡ b (mod n)
Ou seja, x1 tambe´m e´ soluc¸a˜o de (1).
Desta forma, se um membro de uma classe de equivaleˆncia mo´dulo
n e´ uma soluc¸a˜o, enta˜o todos os membros da classe sa˜o soluc¸o˜es.
Portanto faz sentido perguntar quantas das n classes de
congrueˆncia mo´dulo n sa˜o soluc¸o˜es de (1).
Sistemas de congrueˆncias lineares
Teorema. Sejam a, b, n inteiros com n > 0 e mdc(a, n) = d . Se
d 6 | b, enta˜o ax ≡ b (mod n) na˜o possui soluc¸o˜es. Se d | b, enta˜o
ax ≡ b (mod n) possui exatamente d soluc¸o˜es diferentes mo´dulo n.
Exemplo. 9x ≡ 12 (mod 15) tem exatamente treˆs soluc¸o˜es: 3, 8 e
13.
Exemplo. 7x ≡ 1 (mod 13) so´ tem uma soluc¸a˜o: x ≡ 2 (mod 13).
Sistemas de congrueˆncias lineares
Suponhamos que queremos calcular todos os inteiros x e y tais
que:
3x + 4y ≡ 5 (mod 13)
2x + 5y ≡ 7 (mod 13)
Multiplicando a primeira linha por 5 e a segunda por 4:
15x + 20y ≡ 25 (mod 13)
8x + 20y ≡ 28 (mod 13)
Subtraindo:
7x ≡ −3 (mod 13)
Logo
x ≡ 7 (mod 13) e y ≡ 9 (mod 13)
Criptografia
Podemos utilizar transformac¸o˜es do tipo
C ≡ aP + b (mod 26)
com mdc(a, 26) = 1 para cifrar mensagens. Ce´sar:
C ≡ P + 3 (mod 26).
Exemplo. Considere a = 7 e b = 10. Enta˜o
PLEASE SEND MONEY
e´ transformado em
LJMKG MGMXF QEXMW
Criptografia
Para decifrar:
P ≡ a−1(C − b) (mod 26)
onde a−1 e´ o inverso de a mo´dulo 26.
Desta forma, para o exemplo anterior a−1 = 15 e portanto o texto
cifrado
FEXEN XMBMK JNHMG MYZMN
vira
DONOT REVEA LTHES ECRET
Criptografia
Suponhamos que sabemos que o texto em ingleˆs abaixo foi cifrado
utilizando uma transformac¸a˜o da forma C ≡ aP + b (mod 26)
USLEL JUTCC YRTPS URKLT YGGFV
ELYUS LRYXD JURTU ULVCU URJRK
QLLQL YXSRV LBRYZ CYREK LVEXB
RYZDG HRGUS LJLLM LYPDJ LJTJU
FALGU PTGVT JULYU SLDAL TJRWU
SLJFE OLPU
Criptografia
Sabe-se que a letra mais frequ¨ente em ingleˆs e´ E e a segunda mais
frequ¨ente e´ T. Desta forma,
4a + b ≡ 11 (mod 26)
19a + b ≡ 20 (mod 26)
Ou seja, a ≡ 11 (mod 26) e b ≡ 19 (mod 26). Como 19 e´ o
inverso de 11 mo´dulo 26, a transformac¸a˜o para decifrar a
mensagem e´
P ≡ 19(C − 19) ≡ 19C + 3 (mod 26)
Exerc´ıcios propostos - Cap´ıtulo 4
1. Resolva em detalhes o sistema
4a + b ≡ 11 (mod 26)
19a + b ≡ 20 (mod 26)
2. Prove que 19 e´ o inverso de 11 mo´dulo 26.
3. Decifre a mensagem do u´ltimo exemplo.
4. Exerc´ıcios do livro: 4, 5, 6(b), 7, 10 e 11.