Teoria de números e criptografia RSA

Prévia do material em texto

Teoria de nu´meros e criptografia RSA
Elaine Gouveˆa Pimentel
1o Semestre - 2006
(U´ltima Modificac¸a˜o: 4 de Maio de 2006)
1 Bibliografia e refereˆncias
Livro texto: S.C. Coutinho Nu´meros inteiros e criptografia RSA IMPA/SBM,
2000.
Outras refereˆncias:
• Rosen, K. H., Elementary number theory and its applications, Addison-
Wesley,1984.
• Koblitz, N. A course in number theory and criptography, Graduate Texts
in Mathematics 97, Springer-Verlag, 1987.
Ao longo do curso, sera˜o indicadas leituras complementares.
Qualquer du´vida ou comenta´rio, escrever para:
elaine@mat.ufmg.br
2 Introduc¸a˜o
O objetivo desse curso e´ estudar o me´todo de criptografia de chaves pu´blicas
conhecido como RSA. Para entender como este me´todo funciona, e´ necessa´rio
o estudo de alguns conceitos de uma a´rea da matema´tica chamada Teoria de
nu´meros. E, e´ claro, espera-se desenvolver, ao longo do curso, o racioc´ınio
lo´gico matema´tico dos alunos, introduzindo me´todos de prova de teoremas como
induc¸a˜o matema´tica e demonstrac¸a˜o por absurdo.
Deve ficar bem claro que este e´ um curso de matema´tica para cientistas da
computac¸a˜o. Isto e´, o rigor nunca sera´ deixado de lado mas a atenc¸a˜o estara´
sempre voltada para a aplicac¸a˜o principal proposta: criptografia RSA.
1
2.1 Criptografia
• Criptografia: estuda os me´todos para codificar uma mensagem de modo
que so´ seu destinata´rio leg´ıtimo consiga interpreta´-la.
• Primo´rdios: Cesar (translac¸a˜o do alfabeto).
• Criptoana´lise: arte de decifrar co´digos secretos.
• Decodificar x Decifrar (quebrar).
• Substituir letras por s´ımbolos - contagem de frequeˆncia:
– vogais sa˜o mais frequentes;
– letra mais frequente: A;
– monoss´ılabo de uma letra = vogal;
– consoantes mais frequentes: S e M
Me´todo de contagem de frequeˆncia de caracteres pode ser usado para
decifrar inscric¸o˜es antigas.
• O surgimento dos computadores torna esse me´todo de cifragem completa-
mente inseguro (decifragem polinomial).
• Internet e criptografia: seguranc¸a, assinatura.
• Chave pu´blica: saber codificar na˜o implica saber decodificar!
2.2 Criptografia RSA
• RSA: Rivest, Shamir, Adleman (M.I.T.) 1978.
• Codificac¸a˜o: basta conhecer o produto de dois primos (n = pq). n e´
chamado chave pu´blica.
• Decodificac¸a˜o: precisamos conhecer p e q (chave de decodificac¸a˜o).
• Decifrar RSA = fatorac¸a˜o de n. Se n possui 150 algarismos ou mais,
fatora´-lo levaria milhares de anos.
• 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.
• Teoria de nu´meros: parte da matema´tica que estuda nu´meros inteiros.
2
2.3 Computac¸a˜o alge´brica
• Chave pu´blica do RSA: multiplica-se dois primos muito grandes.
• Pascal, C: na˜o permitem lidar com nu´meros dessa magnitude.
• Computac¸a˜o alge´brica: trata do ca´lculo exato com inteiros, frac¸o˜es, etc.
Exemplo: Mathematica, Maple.
• Inteiro de tamanho indeterminado: de tamanho flex´ıvel, grandes o sufi-
ciente. Restric¸o˜es: tamanho da memo´ria, estruturas de dados (vetores de
tamanhos pre´-fixados).
• 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 compli-
cado...
3 Algoritmo da divisa˜o de Euclides
3.1 Algoritmos
• Algoritmo = processo de ca´lculo baseado em regras formais.
• Especificac¸a˜o de um algoritmo: entrada + instruc¸o˜es + sa´ıda.
• Perguntas:
– ao executarmos um conjunto de instruc¸o˜es, sempre chegaremos a um
resultado? (ponto fixo)
– o resultado obtido e´ sempre o desejado? (semaˆntica)
3.2 Algoritmo da divisa˜o
• 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.
• 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.
• Observac¸o˜es:
3
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.
3.3 Teorema da Divisa˜o
Teorema 1 (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′.
3.4 Algoritmo Euclideano
• Objetivo: Calcular o mdc entre dois nu´meros inteiros.
• Definic¸a˜o: o ma´ximo divisor comum entre a e b e´ o nu´mero d tal
que:
– d|a (ou d e´ divisor de a)
– d|b
– se d′ e´ divisor de a e b, enta˜o d′|d (em outras palavras, d e´ o ma´ximo
divisor de a e b.
4
• Escrevemos d = mdc(a, b). Se mdc(a, b) = 1, dizemos que a e b sa˜o
primos entre si .
• Algoritmo Euclideano: 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).
• Exemplo:
1234 54 46 8 6 2
46 8 6 2 0
Ou seja, mdc(1234, 54) = 2.
• Perguntas:
1. Por que o u´ltimo resto na˜o nulo e´ o mdc?
2. Por que o algoritmo para?
• Respostas:
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
...
...
– 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?).
– Primeira pergunta: demonstrac¸a˜o do algoritmo euclideano
3.5 Demonstrac¸a˜o do algoritmo euclideano
Lema 2 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).
5
Afirmamos que d1 ≤ d2. De fato, d1 e´ o ma´ximo divisor de a e b. Logo d1 divide
a e b e portanto existem inteiros positivos u e v tais que:
a = d1u eb = d1v
Substituindo a e b na equac¸a˜o a = bg + s obtemos
s = d1u− d1v = d1(u− vg).
Ou seja, d1 divide s. Como d1 tambe´m divide b, 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
Teorema 3 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 .
Aplicando o algoritmo a a e b, temos:
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 portantomdc(rn−1, rn−2) = rn−1.
Aplicando sucessivamente o lema 2, temos que mdc(a, b) = rn−1.
3.6 Algoritmo euclideano estendido
O resultado que mais vamos usar durante o curso sobre mdc e´ o seguinte:
Teorema 4 Sejam a e b inteiros positivos e seja d o ma´ximo divisor comum
entre a e b. Esxistem inteiros α e β tais que
α.a+ β.b = d.
Para demonstrac¸a˜o desse teorema, veja o livro texto, pag 29-31.
Vamos ilustrar a demonstrac¸a˜o atrave´s de um exemplo nume´rico:
6
Exemplo 1 Sejam a = 1234 e b = 54. Temos que:
1234 = 54.22 + 46 ou seja, 46 = 1234− 54.22Seguindo pelo algoritmo de euclides,
54 = 46.1 + 8 ou seja, 8 = 54− 46.1
Agora, observe que sabemos calcular 46 em func¸a˜o de 1234 e 54. Enta˜o, substi-
tuindo:
8 = 54−46.1 = 54−(1234−54.22).1 = 54(1+22.1)+1234.(−1) = 54.(23)+1234.(−1)
Continuando,
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)
Logo, α = −7 e β = 160 uma vez que mdc(1234, 54) = 2.
Observe que o teorema na˜o diz que os valores de α e β sa˜o u´nicos. Na verdade,
existe uma infinidade de nu´meros que satisfazem a equac¸a˜o αa+ βb = d.
Pergunta: para que serve calcular α e β?
Resposta:
• unicidade de fatorac¸a˜o de um inteiro;
• RSA depende de um me´todo eficiente de ca´lculo de α e β.
3.7 Exerc´ıcios propostos
Na˜o deixem de fazer os seguintes exerc´ıcios do cap´ıtulo 1:
1(1), 4, 5, 7, 8, 9.
7
4 Fatorac¸a˜o u´nica
4.1 Teorema da fatorac¸a˜o u´nica
Dizemos que um nu´mero inteiro positivo p e´ primo se p 6= 1 e os u´nicos
divisores de p sa˜o p e 1.
Se um nu´mero inteiro positivo (diferente de 1) na˜o e´ primo, enta˜o ele e´ chamado
de composto .
Teorema 5 (Teorema da fatorac¸a˜o u´nica) Dado um inteiro positivo n ≥ 2
podemos sempre escreveˆ-lo, de maneira u´nica, na forma:
n = pe11 . . . . .p
ek
k
onde 1 < p1 < p2 < . . . < pk sa˜o nu´meros primos e e1, . . . , ek sa˜o inteiros
positivos (multiplicidades).
4.2 Existeˆncia da fatorac¸a˜o
Algoritmo ingeˆnuo: Dado n ≥ 2 inteiro positivo, tente dividir n por cada um
dos inteiros de 2 a n− 1. Se algum desses inteiros (digamos k) dividir n, enta˜o
achamos um fator de n.
Perguntas:
1. k e´ primo ou composto?
2. Quando se deve parar a busca? Em n− 1?
Respostas:
1. k e´ primo. De fato, suponhamos k composto. Logo, k = a.b com 1 <
a, b < k. Como k divide n, existe (por definic¸a˜o) c inteiro tal que n = k.c.
Logo,
n = a.b.c
ou seja, a e b sa˜o fatores de n menores que k, o que contraria a hipo´tese
da minimalidade de k. Logo, k e´ primo.
2. Na verdade, podemos parar o algoritmo em
√
n. De fato, n = k.c ou
c = n
k
. Como k e´ o menor fator de n, k ≤ c. Logo, k ≤ n
k
ou seja,
k2 ≤ n→ k ≤ √n.
Podemos utilizar o algoritmo acima para achar todos os fatores primos de n.
Aplicando o algoritmo uma vez, encontramos o fator q1. Enta˜o, aplicamos o
8
algoritmo ao nu´mero n
q1
, determinando q2, o segundo fator primo de n. Para
determinar o terceiro fator primo q3, aplicamos o algoritmo ao nu´mero
n
q1.q2
e
assim por diante, ate´ chegarmos em n
q1.q2.....qs−1
= qs, com qs primo. Observe
que q1 ≤ q2 ≤ . . . ≤ qs−1 ≤ qs e
n >
n
q1
>
n
q1.q2
> . . . >
n
q1.q2. . . . .qs
> 0,
ou seja, o algoritmo sempre termina.
Exemplo 2 n = 450 = 2.3.3.5.5
4.3 Eficieˆncia do algoritmo ingeˆnuo de fatorac¸a˜o
O algoritmo e´ simples mas muito ineficiente!
Exemplo 3 Seja n um nu´mero primo com 100 ou mais algarismos. Logo,
n ≥ 10100 e portanto √n ≥ 1050. Logo temos que executar pelo menos 1050
loops para determinar que n e´ primo. Suponhamos que o nosso computador
execute 1010 diviso˜es por segundo. Logo levaremos 10
50
1010 = 10
40 segundos, ou
seja, 1031 anos na frente da tela do computador aguardando... Observe que o
tempo estimado de existeˆncia do universo e´ 1011 anos!
O algoritmo e´ bom para nu´meros pequenos. E´ importante ressaltar que na˜o
existe (atualmente) algoritmo de fatorac¸a˜o eficiente para todos os
inteiros . Disso depende a seguranc¸a do RSA!
Na˜o se sabe, entretanto, se tal algoritmo na˜o existe mesmo ou se na˜o fomos
espertos o suficiente para inventa´-lo...
4.4 Fatorac¸a˜o por Fermat
• Eficiente quando n tem um fator primo na˜o muito menor que √n.
• Ide´ia: tentar achar nu´meros inteiros positivos x e y tais que n = x2 − y2.
• Caso mais fa´cil: n = r2 (x = r e y = 0).
• Se y > 0, enta˜o
x =
√
n+ y2 >
√
n
Notac¸a˜o: escrevemos [r] como a parte inteira do nu´mero real r.
Algoritmo de Fermat:
Etapa 1: Fac¸a x = [
√
n]; se n = x2, pare.
9
Etapa 2: Incremente x de uma unidade e calcule y =
√
x2 − n.
Etapa 3: Repita a etapa 2 ate´ encontrar um valor inteiro para y, ou ate´ que x = n+12 .
No primeiro caso, n tem fatores x+ y e x− y; no segundo, n e´ primo.
Exemplo 4 Seja n = 1342127. Temos que x = 1158. Mas
x2 = 11582 = 1340964 < 1342127
Logo, passamos a incrementar x ate´ que
√
x2 − n
seja inteiro ou x = n+12 , que nesse caso vale 671064:
x
√
x2 − n
1159 33, 97
1160 58, 93
1161 76, 11
1162 90, 09
1163 102, 18
1164 113
Logo, x = 1164 e y = 113. Os fatores procurados sa˜o x+y = 1277 e x−y = 1051.
Faremos aqui apenas a demonstrac¸a˜o de que, se n e´ primo, enta˜o o u´nico valor
poss´ıvel para x e´ x = n+12 . Relembrando, x e y sa˜o inteiros positivos tais que
n = x2 − y2. Ou seja,
n = (x− y)(x+ y)
Como estamos supondo n primo, temos que x− y = 1 e x+ y = n. Logo,
x =
1 + n
2
e y =
n− 1
2
como quer´ıamos.
Veja a demonstrac¸a˜o completa do algoritmo no livro texto, pa´ginas 41 a 43.
Observac¸a˜o: Esse algoritmo diz algo importante sobre o RSA. Se escolhermos
p e q muito pro´ximos, enta˜o n = p.q e´ facilmente fatora´vel pelo algoritmo de
Fermat.
4.5 Propriedade fundamental dos primos
Lema 6 Sejam a, b, c inteiros positivos e suponhamos que a e b sa˜o primos entre
si. Enta˜o:
1. Se b divide o produto a.c enta˜o b divide c.
10
2. Se a e b dividem c enta˜o o produto a.b divide c.
Prova mdc(a, b) = 1. Pelo Algoritmo euclideano estendido, existem α e β
tais que
α.a+ β.b = 1
Enta˜o,
α.a.c+ β.b.c = c
Como b divide a.c pela hipo´tese (1) e como b divide β.b.c, enta˜o b divide c.
Para provar a segunda afirmativa, se a divide c, podemos escrever c = at para
algum inteiro t. Mas b tambe´m divide c. Como mdc(a, b) = 1, pela afirmac¸a˜o
(1), b divide t. Logo, t = b.k para algum inteiro k e portanto,
c = a.t = a.b.k
Podemos usar o lema acima para provar se seguinte propriedade:
Propriedade fundamental dos primos Seja p um primo e a e b inteiros
positivos. Se p divide o produto a.b, enta˜o p divide a ou p divide b.
A demonstrac¸a˜o fica como exerc´ıcio (fac¸am!).
4.6 Unicidade
A prova de unicidade da fatorac¸a˜o de nu´meros primos decorre facilmente da
propriedade fundamental dos primos. A demonstrac¸a˜o se da´ por absurdo.
Seja n o menor inteiro positivo que admite duas fatorac¸o˜es distintas. Podemos
escrever:
n = pe11 . . . . .p
ek
k = q
r1
1 . . . . .q
rs
s
onde p1 < p2 < . . . < pk e q1 < q2 < . . . < qs sa˜o primos e e1, . . . , ek, r1, . . . , rs
sa˜o inteiros positivos.
Como p1 divide n, pela propriedade fundamental dos primos p1 deve dividir um
dos fatores do produto da direita. Mas um primo so´ pode dividir outro se forem
iguais. Enta˜o p1 = qj para algum j entre 1 e s. Logo,
n = pe11 . . . . .p
ek
k = q
r1
1 . . . . .q
rj
j . . . . .q
rs
s
= qr11 . . . . .p
rj
1 . . . . .q
rs
s
Podemos enta˜o cancelar p1 que aparece em ambos os lados da equac¸a˜o, obtendo
m = pe1−11 . . . . .p
ek
k = q
r1
1 . . . . .p
rj−1
1 . . . . .q
rs
s
onde m e´ um nu´mero menor que n que apresenta duas fatorac¸o˜es distintas.
ABSURDO pois isso contraria a minimalidade de n.
11
4.7 Exerc´ıcios propostos
1. Prove a propriedade fundamental dos primos.
2. Demonstre que, se p e´ um nu´mero primo, enta˜o
√
p e´ um nu´mero irracional.
3. Livro texto: 2, 4, 5, 8, 11, 12.
5 Nu´meros primos
Ate´ agora:
• propriedades ba´sicas dos nu´meros inteiros;
• dois algoritmos fundamentais;
Nessa sec¸a˜o, discutiremos me´todos ingeˆnuos para encontrar primos.
5.1 Fo´rmulas Polinomiais
Considere o polinoˆmio:
f(x) = an.x
n + an−1.x
n−1 + . . .+ a1.x+ a0
onde an, an−1,. . . , a1, a0 sa˜o nu´meros inteiros e que satisfaz a condic¸a˜o:
f(m) e´ primo, para todo inteiro positivo m
Exemplo 5 Seja f(x) = x2 + 1 Logo,
x f(x)
1 2
2 5
3 10
4 17
5 26
6 37
7 50
8 65
9 82
2 5
• x ı´mpar → f(x) par;
• f(8) = 65 composto...
12
A pergunta que surge enta˜o e´: isso e´ fruto do azar?
Teorema 7 Dado um polinoˆmio f(x) com coeficientes inteiros, existe uma in-
finidade de inteiros positivos m tais que f(m) e´ composto.
Prova .
Vamos Provar o teorema apenas no caso em que o polinoˆmio tem grau 2. Ou
seja, consideraremos f do tipo:
f(x) = a.x2 + b.x+ c
Podemos supor a > 0. Suponhamos que exista m tal que f(m) = p onde p e´
primo. Calculando f(m+ hp):
f(m+ hp) = a(m+ hp)2 + b(m+ hp) + c
= (am2 + bm+ c) + p(2amh+ aph2 + bh)
= p(1 + 2amh+ aph2 + bh)
Ou seja, se 1+2amh+aph2+bh e´ composto enta˜o f(m+hp) tambe´m e´ composto.
Mas isso e´ verdade sempre que
1 + 2amh+ aph2 + bh > 1
ou seja, se
2amh+ aph2 + bh = h.(2am+ aph+ b) > 0
Como podemos sempre tomar h positivo, temos:
2am+ aph+ b > 0→ h > −b− 2am
a.p
Existe uma infinidade de nu´meros dessa forma. Logo, se existe inteiro m tal
que f(m) e´ primo, enta˜o existe uma infinidade de tais nu´meros.
Conclusa˜o: na˜o existe uma fo´rmula polinomial (em uma varia´vel) para
primos .
5.2 Fo´rmulas exponenciais: nu´meros de Mersenne
• Nu´meros de Mersenne sa˜o aqueles da forma:
M(n) = 2n − 1
onde n e´ um inteiro na˜o negativo.
• Nu´meros perfeitos sa˜o aqueles iguais a` metade da soma de seus divi-
sores. Ex: 6 = 12/2 e 12 = 1 + 2 + 3 + 6
13
• Nenhum primo e´ perfeito.
• Resultado: 2n−1.(2n − 1) e´ perfeito se 2n − 1 e´ primo.
• Outro resultado: Todo nu´mero perfeito par possui a forma acima. Ex:
6 = 22−1(22 − 1)
• O que na˜o se sabe: se existem nu´meros perfeitos ı´mpares.
• Pergunta: Quais sa˜o os nu´meros de Mersenne primos? Exemplos: quando
n = 2, 3, 5, 7, 13, 17, 19, 31, 61.... Observe que os expoentes sa˜o todos pri-
mos, mas nem todos primos fazem parte dessa lista. Por exemplo,
M(11) = 2047 = 23.89
5.3 Fo´rmulas exponenciais: nu´meros de Fermat
• Nu´meros de Fermat sa˜o aqueles da forma:
F (n) = 22
n
+ 1
onde n e´ um inteiro na˜o negativo.
• Exemplos de nu´meros de Fermat primos: n = 0, 1, 2, 3, 4. F (5) = 18446744073709551617
e´ composto!
• Poucos primos de Fermat sa˜o conhecidos.Ate´ hoje, na˜o se descobriu nen-
hum F (n) primo com n ≥ 5.
5.4 Fo´rmulas fatoriais
Seja p um primo positivo. Construiremos uma func¸a˜o semelhante ao fatorial, so´
que apenas os primos sa˜o multiplicados. Vamos chama´-la de p#. Ou seja, p# e´
o produto de todos os primos menores ou iguais a p. Ex: 5# = 2.3.5 = 30
Observe que se p e q sa˜o primos sucessivos, enta˜o
p# = q#.p
Estaremos interessados nos nu´meros da forma p# + 1. Embora p# + 1 nem
sempre seja primo (Ex. 13# + 1 = 30031 = 59.509), podemos mostrar que na˜o
tem nenhum fator primo menor ou igual a p. Desta forma, temos um algoritmo
para calcular primo.
Pergunta: qual e´ o problema de tal algoritmo?
Observac¸a˜o final: p# + 1 quase nunca e´ primo!
14
5.5 Infinidade de primos
Teorema 8 Existem uma infinidade de primos
Prova .
Digamos que exista uma quantidade finita de primos:
{p1, p2, . . . , pk}
Podemos supor que esses primos esta˜o ordenados, de modo que pk e´ o maior
deles. Considere o nu´mero p#k +1. Como vimos, esse nu´mero possui fator primo
maior que pk. ABSURDO!
5.6 Crivo de Erato´stenes
O crivo de Erato´stenes e´ o mais antigo dos me´todos para encontrar primos.
Etapa 1: Listamos os nu´meros ı´mpares de 3 a n.
Etapa 2: Procure o primeiro nu´mero k da lista. Risque os demais nu´meros da lista,
de k em k.
Etapa 3: Repita a etapa 2 ate´ chegar em n.
Observac¸o˜es:
1. Podemos parar em
√
n...
2. Podemos comec¸ara riscar a partir de k2...
5.7 Crivo de Erato´stenes revisado
Etapa 1: Crie um vetor v de n−12 posic¸o˜es, preenchidas com o valor 1; fac¸a P = 3.
Etapa 2: Se P 2 > n, escreva os nu´meros 2j + 1 para os quais a j-e´sima entrada de
v e´ 1 e pare;
Etapa 3: Se a posic¸a˜o (P−1)2 de v esta´ preenchida com 0 incremente P de 2 e volte
a` Etapa 2.
Etapa 4: Atribua o valor P 2 a uma nova varia´vel T ; substitua por zero o valor da
posic¸a˜o (T−1)2 e incremente T de 2P ; repita ate´ que T > n; incremente P
de 2 e volte a` Etapa 2.
15
5.8 Exerc´ıcios propostos
1. Entenda e implemente o algoritmo da pag 65 do livro texto.
2. Livro texto: 1, 3 a 7, 8 e 10.
6 Aritme´tica modular
Aritme´tica modular = aritme´tica dos fenoˆmenos c´ıclicos.
Exemplos: Horas, dias do meˆs, letras do alfabeto, etc.
6.1 Relac¸o˜es de equivaleˆncia
Seja X um conjunto e ∼ uma relac¸a˜o entre elementos de X . Dizemos que ∼ e´
uma relac¸a˜o de equivaleˆncia se, para todos x, y, z ∈ X :
Reflexiva x ∼ x.
Sime´trica Se x ∼ y enta˜o y ∼ x.
Transitiva Se x ∼ y e y ∼ z enta˜o x ∼ z.
Exemplos:
• < nos inteiros na˜o satisfaz reflexividade;
• ≤ nos inteiros satisfaz reflexividade, mas na˜o satisfaz simetria;
• 6= e´ reflexiva, sime´trica mas na˜o transitiva;
• relac¸a˜o de equivaleˆncia: = nos nu´meros inteiros.
Relac¸o˜es de equivaleˆncia: sa˜o usadas para classificar os elementos de um con-
junto em subconjuntos com propriedades semelhantes. As subdiviso˜es de um
conjunto produzidas por uma relac¸a˜o de equivaleˆncia sa˜o conhecidas como classes
de equivaleˆncia. Formalmente, seja X um conjunto e ∼ uma r.e. definida em
X . Se x ∈ X enta˜o a classe de equivaleˆncia de x e´ o conjunto de elementos
de X que sa˜o equivalentes a x por ∼. Denotamos:
x = {y ∈ X : y ∼ x}.
Propriedades:
• Qualquer elemento de uma classe de equivaleˆncia e´ um representante de
toda a classe.
16
• X e´ a unia˜o de todas as classes de equivaleˆncia.
• Duas classes de equivaleˆncia distintas na˜o podem ter um elemento em
comum.
O conjunto das classes de equivaleˆncia de ∼ em X e´ chamado de conjunto
quociente de X por ∼. Observe que os elementos do conjunto quociente sa˜o
subconjuntos de X . Isto e´, o conjunto quociente na˜o e´ um subcojunto de X ,
mas um subconjunto das partes de X .
6.2 Inteiros mo´dulo n
Vamos construir uma relac¸a˜o de equivaleˆncia no conjunto dos inteiros. Digamos
que, pulando de n em n, todos os inteiros sa˜o equivalentes. Ou melhor: dois
inteiros cuja diferenc¸a e´ um mu´ltiplo de n sa˜o equivalentes. Formalmente, dize-
mos que dois inteiros a e b sa˜o congruentes mo´dulo n se a− b e´ mu´ltiplo
de n. Escrevemos:
a ≡ b (mod n)
Exemplos:
10 ≡ 0 (mod 5) 23 ≡ 1 (mod 11)
Observac¸a˜o: Congrueˆncia mo´dulo n e´ uma relac¸a˜o de equivaleˆncia:
• a ≡ a (mod n) (trivialmente)
• Se a ≡ b (mod n), enta˜o a − b e´ mu´ltiplo de n. Mas b − a = −(a − b);
logo, b− a tambe´m e´ mu´ltiplo de n. Portanto b ≡ a (mod n).
• Transitividade: exerc´ıcio.
Chamamos de Zn o conjunto de inteiros mo´dulo n. Ou seja, se a ∈ Z, enta˜o
a = {a+ kn | k ∈ Z}
Em particular, 0 e´ o conjunto dos mu´ltiplos de n.
Voltemos agora ao algoritmo da divisa˜o de Euclides. Vimos que, dados a e n
inteiros positivos, a > n, existem inteiros q e r tais que
a = n.q + r o ≤ r ≤ n− 1
Ou seja, a− r ≡ 0 (mod n) e portanto a ≡ r (mod n).
Em outras palavras,
Zn = {0, 1, . . . , n− 1}
.
17
6.3 Artime´tica modular
Sejam a e b classes de Zn. Enta˜o,
a+ b = a+ b
Exemplo:
5 + 4 ≡ 9 ≡ 1 (mod 8)
Logo,
5 + 4 = 9 = 1
A diferenc¸a entre duas classes e´ definida de maneira ana´loga.
A fo´rmula para a multiplicac¸a˜o das classes a e b de Zn e´:
a.b = a.b
Propriedades da adic¸a˜o:
A1 (a+ b) + c = a+ (b+ c).
A2 a+ b = b+ a.
A3 a+ 0 = a.
A4 a+−a = 0.
Propriedades da multiplicac¸a˜o:
M1 (a.b).c = a.(b.c).
M2 a.b = b.a.
M3 a.1 = a.
AM a.(b+ c) = a.b+ a.c.
Exemplo: em Z6,
2.3 = 6 = 0!!!
6.4 Crite´rios de divisibilidade
• Divisibilidade por 3: 3|a se a soma de todos os algarismosde a e´
divis´ıvel por 3.
Prova Seja
a = an.an−1. . . . .a1.a0
= an.10
n + an−1.10
n−1 + . . .+ a1.10 + a0
18
Como 10 ≡ 1 (mod 3),
a ≡ an + an−1 + . . .+ a1 + a0 (mod 3)
Logo, a ≡ 0 (mod 3) se e somente se
an + an−1 + . . .+ a1 + a0 ≡ 0 (mod 3)
Observe que podemos usar o mesmo argumento para provar que um nu´mero
inteiro e´ divis´ıvel por 9 se a soma de seus algarismos e´ divis´ıvel por 9
(10 ≡ 1 (mod 9)).
• Divisibilidade por 11: 11|a se a soma alternada de todos os algaris-
mos de a e´ divis´ıvel por 11. Prova Observe que 10 ≡ −1 (mod 11).
Portanto,
10k ≡ (−1)k (mod 11)
e´ igual a 1 ou -1 dependendo da paridade de k. Logo,
a ≡ (−1)n.an + (−1n−1).an−1 + . . .+ a2 − a1 + a0 (mod 11)
6.5 Poteˆncias
A aplicac¸a˜o mais importante de congrueˆncias no nosso curso e´ no ca´lculo de
resto da divisa˜o de uma poteˆncia por um nu´mero qualquer.
Vamos ilustrar como isso e´ feito na pra´tica atrave´s de um exemplo.
Suponhamos que o objetivo seja calcular
3515 (mod 20)
Em primeiro lugar, escrevemos o expoente 15 na base 2:
15 = 23 + 22 + 2 + 1
Logo,
3515 = 352
3+22+2+1 = 35.352.352
2
.352
3
= 35.(35)2.(352)2.((352)2)2
Como 35 ≡ 15 (mod 20), 152 ≡ 5 (mod 20) e 52 ≡ 5 (mod 20), temos:
3515 = 35.352.352
2
.352
3
≡ 15.(15)2.(352)2.((352)2)2 (mod 20)
≡ 15.5.(5)2.((352)2)2 (mod 20)
≡ 15.5.5.(5)2 (mod 20)
≡ 15.5.5.5 (mod 20)
≡ 15.5 (mod 20)
≡ 15 (mod 20)
19
6.6 Equac¸o˜es diofantinas
Uma equac¸a˜o diofantina e´ uma equac¸a˜o em va´rias inco´gnitas com co-
eficientes inteiros. Por exemplo, xn + yn = zn. Estaremos interessados em
encontrar as soluc¸o˜es inteiras dessas equac¸o˜es.
E´ claro que tais equac¸o˜es podem ter infinitas soluc¸e˜s. Por exemplo, x+ y = 2.
Ou nenhuma, como no caso da equac¸a˜o
x3 − 117y3 = 5
E´ muito fa´cil ver que isso e´ verdade atrave´s da reduc¸a˜o mo´dulo 9. De fato, como
117 e´ divis´ıvel por 9,
x3 − 117y3 ≡ x3 ≡ 5 (mod 9)
Logo, se a equac¸a˜o acima tivesse soluc¸a˜o, dever´ıamos ter 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
Ou seja, x3 ≡ 5
(mod 9) na˜o tem soluc¸a˜o.
6.7 Divisa˜o modular
Teorema 9 (Teorema da inversa˜o) A classe a tem inverso em Zn se e so-
mente se a e n sa˜o primos entre si.
Prova (⇒) Suponha que a tem inverso. Enta˜o existe b tal que
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.
O conjunto dos elementos de Zn que teˆm inverso e´ muito importante. Vamos
denota´-lo por U(n). Em outras palavras,
U(n) = {a ∈ Z(n)|mdc(a, n) = 1}
20
No caso de n = p ser primo,
U(p) = Z(n) \ {0}
Uma propriedade importante de U(n) e´ que esse conjunto e´ fechado com
relac¸a˜o a` multiplicac¸a˜o . Em outras palavras, o produto de dois elementos
de U(n) e´ um elemento de U(n). Em particular, podemos dividir a por b em Z(n)
somente se b ∈ U(n); nesse caso, b−1 tambe´m pertencera´ a U(n) e a
b
≡ a.b−1
(mod n).
Podemos utilizar o que aprendemos para resolver congrueˆncias lineares em Z(n).
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.
6.8 Exerc´ıcios propostos
4, 5, 6(b), 7, 10 e 11
7 Primeira Prova de A´lgebra A
Questa˜o 1 - a) Calcule d = mdc(252, 198).
b) Encontre dois nu´meros inteiros a e b tais que:
a.252 + b.198 = d (1)
Resoluc¸a˜o: 252=198+54 54=252-198
198=3.54+36 36=198-3.54 =198-3.(252-198)
=-3.252+4.198
54=36+18 18=54-36 =252-198-(-3.252+4.198)
=4.252+(-5).198
Deste modo, mdc(252, 198) = 18 e a = 4, b = −5
21
Questa˜o 2 - Verifique se as proposic¸o˜es abaixo sa˜o verdadeiras ou falsas. Deˆ
uma demonstrac¸a˜o (= justificativa clara e bem escrita) ou um contra-exemplo
para justificar a sua conclusa˜o.
(a) Se p e´ um nu´mero primo, enta˜o
√
p e´ um nu´mero irracional.
(b) Se um nu´mero inteiro A se escreve em base 8 na forma anan−1...a1a0, com
0 ≤ ai ≤ 7, enta˜o 2|A se e somente se a0 = 0.
(c) Se p > 3 e´ um nu´mero primo e p ≡ a( (mod 3)), enta˜o mdc(a, 3) = 1.
(d) Todo nu´mero inteiro representa´vel com treˆs algarismos iguais na base 10 e´
divis´ıvel por 37.
(e) Se x e y sa˜o inteiros ı´mpares, enta˜o x2 + y2 = p2 para algum primo p.
Resoluc¸a˜o:
a) V- Suponha que existam a, b ∈ ℵ tais que √p = a
b
. Podemos supor
mdc(a, b) = 1. Logo,
p.b2 = a2
e portanto p|a2. Pela propriedade fundamental dos primos, p|a. Logo,
existe c ∈ ℵ tal que a = pc.
p.b2 = p2.c2 =⇒ b2 = p.c2 =⇒ p|b2 =⇒ p|b
Mas isso e´ um absurdo uma vez que estamos supondo mdc(a, b) = 1.
b) F - Seja A = anan−1 . . . a1a0 um nu´mero na base 8. Enta˜o 2|A se e
somente se A ≡ 0 (mod 2). Observe que
A = an.8
n + . . .+ a1.8 + a0 ≡ a0 (mod 2)
ou seja, 2|A se e somente se 2|a0. Deste modo, 2|A se e somente se
a0 ∈ {0, 2, 4, 6}.
c) V - Se p ≡ a (mod 3), enta˜o o resto da divisa˜o de p e a por 3 e´ o mesmo.
Como p e´ primo, p > 3, temos que
p ≡ 1 (mod 3) ou p ≡ 2 (mod 3)
Logo, a ≡ 1 (mod 3) ou a ≡ 2 (mod 3), ou seja,
a = 3n+ k, com k = 1, 2
Pelo algoritmo euclideano, mdc(a, 3) = mdc(k, 3) = 1 para k = 1, 2.
22
d) V - Seja n = aaa = a(111). Como 111 = 3.37,
aaa ≡ a(111) ≡ 0 (mod 37)
e) F - Se x e y sa˜o ı´mpares, enta˜o existem n e m tais que
x = 2n+ 1, y = 2m+ 1
Logo,
x2 + y2 = 4n2 + 4n+ 1 + 4m2 + 4m+ 1
= 2(2n2 + 2n+ 2m2 + 2m+ 1)
= 2k
onde k e´ um nu´mero ı´mpar. Logo na˜o existe p ∈ ℵ tal que
x2 + y2 = p2
Observe que p na˜o precisa ser primo: vale para qualquer nu´mero natural.
Questa˜o 3 - Resolva um (e apenas um) dos exerc´ıcios abaixo:
(a) Seja p um nu´mero primo. Mostre que um inteiro positivo a e´ o seu pro´prio
inverso mo´dulo p (ou seja, a2 ≡ 1 (mod p)) se e somente se a ≡ 1 (mod p)
ou a ≡ −1 (mod p).
(b) Calcule 1235 (mod 23).
Resoluc¸a˜o:
a) (=⇒) Suponhamos a2 ≡ 1 (mod p). Logo,
(a2 − 1) ≡ 0 (mod p) =⇒ p|(a+ 1)(a− 1)
Pela propriedade fundamental dos primos, p|(a+ 1) ou p|(a− 1). Logo,
a ≡ 1 (mod p) ou a ≡ −1 (mod p)
(⇐=) Trivial!
b) Observe que 35 = 25 + 2 + 1. Logo,
1235 ≡ 1225 .122.12
≡ 2.6.12
≡ 2.3
≡ 6 (mod 23)
23
8 Induc¸a˜o e Fermat
8.1 Induc¸a˜o finita
Seja P (n) uma proposic¸a˜o que afirma que uma determinada propriedade vale
para cada nu´mero natural n. Por exemplo:
• Se p e´ um nu´mero primo, enta˜o np−n e´ divis´ıvel por p para todo natural
n.
• A soma de 1 ate´ n e´ n(n+1)2
Para provar P (n), em geral usamos o princ´ıpio da induc¸a˜o finita :
Princ´ıpio da induc¸a˜o finita Para que uma proposic¸a˜o P (n) seja verdadeira
para todo n natural, basta que:
1. P (1) seja verdadeira.
2. Se P (k) for verdadeira para algum nu´mero natural k, enta˜o P (k + 1)
tambe´m e´ verdadeira.
8.2 Pequeno teorema de Fermat
Lema 10 Seja p um nu´mero primo e a, b inteiros. Enta˜o,
(a+ b)p ≡ ap + bp (mod p)
Prova Veja livro texto, pag 94.
Teorema 11 (Teorema de Fermat) Seja p um nu´mero primo e a um nu´mero
inteiro. Enta˜o
ap ≡ a (mod p).
Prova
• Se n = 1, enta˜o 1p ≡ 1 (mod p) trivialmente.
• Suponhamos que np ≡ n (mod p) para algum n inteiro positivo. Usando
o lema anterior,
(n+ 1)p ≡ np + 1p ≡ np + 1 (mod p)
Como pela hipo´tese de induc¸a˜o temos np ≡ n (mod p),
(n+ 1)p ≡ np + 1 ≡ n+ 1 (mod p)
Como quer´ıamos demonstrar.
24
Caso geral: veja pag 95 do livro texto.
Teorema 12 (Teorema de Fermat II) Seja p um nu´mero primo e a um in-
teiro que na˜o e´ divis´ıvel por p. Enta˜o,
ap−1 ≡ 1 (mod p).
Prova Como mdc(a, p) = 1, existe a′ tal que
aa′ ≡ 1 (mod p)
Multiplicando ambos os membros de ap ≡ a (mod p). por a′, obtemos:
a′.a.ap−1 ≡ a′.a(mod p).
Logo,
ap−1 ≡ 1 (mod p).
Podemos simplificar algumas contas usando o Teorema de Fermat. De fato,
sejam p primo, a inteiro tal que mdc(a, p) = 1 e k um nu´mero inteiro tal que
k ≥ p− 1. Dividindo k por p− 1,
k = (p− 1).q + r 0 ≤ r < (p− 1)
Logo,
ak ≡ a(p−1).q+r ≡ (ap−1)q.ar (mod p).
Mas (ap−1) ≡ 1 (mod p) e portanto
ak ≡ ar (mod p).
8.3 Exerc´ıcios propostos
1, 3, 46, 7, 8, 12
9 Pseudoprimos
Nesta sec¸a˜o, veremos com usar o pequeno teorema de Fermat para identificar
que um nu´mero e´ composto sem fatora´-lo .
25
9.1 Pseudoprimos
De acordo com o teorema de Fermat, se p e´ primo e a e´ um inteiro qualquer,
enta˜o ap ≡ a (mod p). Desta forma, e´ claro que, se n e´ um nu´mero composto,
enta˜o existe um inteiro b tal que bn\ ≡ b (mod n) (usaremos o s´ımbolo \ ≡ para
significar na˜o equivalente). Observe que, na pra´tica, so´ precisamos considerar
os inteiros b no intervalo 1 < b < n− 1 (por que?).
Desta forma, temos um me´todo para determinar se um nu´mero e´ composto sem
termos que fatora´-lo:
Teste Se n, b sa˜o nu´meros inteiros, n > 0 e 1 < b < n − 1, tais que bn−1\ ≡ 1
(mod n), enta˜o n e´ composto.
A pergunta que surge enta˜o e´: o teste acima e´ um procedimento de decisa˜o?
Isto e´, o fato de na˜o encontrarmos tal b significa que n e´ primo?
Resposta: Observe que, se n e´ composto, enta˜o existe p primo, 1 < p < n− 1
tal que p|n. Logo, mdc(p, n) = p 6= 1 e portanto p na˜o e´ invers´ıvel mo´dulo n.
Desta forma, pn−1\ ≡ 1 (mod n).
E´ claro que esse na˜o e´ um me´todo eficiente para testar primalidade uma vez que
e´ um me´todo de exausta˜o.
Outra pergunta interessante que surge e´ a seguinte: sera´ que, se um nu´mero
ı´mpar n que satisfac¸a:
bn−1 ≡ 1 (mod n)
para algum 1 < b < n−1 e´ primo? Infelizmente, a resposta e´ na˜o. Por exemplo,
2340 ≡ 1 (mod 341) mas 341 = 11.31 na˜o e´ primo! Esses “falsos primos” sa˜o
conhecidos como pseudoprimos. Ou seja, um pseudoprimo n para a base b
e´ um nu´mero inteiro positivo ı´mpar e composto tal que
bn−1 ≡ 1 (mod n)
Apesar de a`s vezes dar errado, esse teste (chamado de teste de Leibniz) e´ muito
u´til. Tambee´m e´ poss´ıvel melhorar o resultado do teste se testarmos para duas
bases.
Exemplo 6 Existem 50.847.534 primos entre 1 e 109; existem apenas 5597
pseudoprimos na base 2 e 1272 pseudoprimos para as bases 2 e 3.
9.2 Nu´meros de Carmichael
Como vimos anteriormente, na˜o existem nu´meros que sejam pseudoprimos para
todas as bases. Entretanto, pode ocorrer que um nu´mero composto n seja
pseudoprimo para todas as bases b tais que mdc(b, n) = 1.
Dizemos que um nu´mero composto ı´mpar e´ um nu´mero de Carmichael se
bn ≡ b (mod n).
26
Os nu´meros de Carmichael possuem duas propriedades muito interessantes,
dadas pelo teorema baixo:
Teorema 13 (Teorema de Korselt:) Um inteiro positivo ı´mpar n e´ um nu´mero
de Carmichael se, e somente se, cada fator primo p de n satisfaz as seguintes
condic¸o˜es:
1. p2 na˜o divide n;
2. p− 1 divide n− 1.
Prova (=⇒) Seja p um fator primo de n. Enta˜o,
bn ≡ b (mod p)
De fato, se b e´ divis´ıvel por p enta˜o ambos os membros da equivaleˆncia sa˜o
congruentes a zero. Se na˜o, pelo teorema de Fermat temos:
bp−1 ≡ 1 (mod p)
Pela condic¸a˜o (2) do teorema, n− 1 = (p− 1).q para algum q. Logo,
bn ≡ (bp−1)q.b ≡ b (mod p)
Por (1), temos que n = p1 . . . pk com p1 < p2 < . . . < pk. Como os primos sa˜o
distintos, bn − b e´ divis´ıvel pelo produto p1.p2. . . . .pk = n. Em outras palavras,
bn ≡ b (mod n)
e portanto n e´ um nu´mero de Carmichael.
(⇐=) Seja n um nu´mero de Carmichael e suponhamos que exista p primo tal
que p2|n. Escolha b = p. Enta˜o:
pn − p = p(pn−1 − 1)
Mas p na˜o divide pn−1 − 1, logo p2 na˜o pode dividir pn − p. Portanto, n na˜o
pode dividir pn − p. Em outras palavras, p ≡ p (mod n). Absurdo.
O restante da demonstrac¸a˜o depende do teorema da raiz primitiva, que so´ sera´
vista no cap´ıtulo 10...
Observac¸o˜es:
• Para verificar que um nu´mero e´ de Carmichael usando o teorema acima
necessitamos fatora´-lo...
• Muitos nu´meros de Carmichael possuem fatores primos pequenos!
• Existem infinitos nu´meros de Carmichael.
• Entre 1 e 109 existem 50.847.534 primos e 646 nu´meros de Carmichael.
27
9.3 Teste de Miller
Teorema de Fermat: detecta nu´meros compostos com uma certa eficieˆncia, mas
na˜o e´ um bom teste de primalidade.
Teste de Miller: Calcula-se a sequeˆncia de poteˆncias mo´dulo n:
bq, b2q, . . . , b2
kq
onde n− 1 = 2kq.
O fato e´ que, se n e´ primo, enta˜o:
b2
kq ≡ bn−1 ≡ 1 (mod n)
Digamos que j e´ o menor expoente tal que b2
jq ≡ 1 (mod n). Se j ≥ 1
podemos escrever
b2
jq − 1 = (b2j−1q − 1)(b2j−1q + 1)
Se n e´ primo e divide b2
jq−1, enta˜o n deve dividir (b2j−1q+1) pela minimalidade
de j. Logo,
b2
j−1q − 1 ≡ −1 (mod n)
Ou seja, uma das poteˆncias
bq, b2q, . . . , b2
kq
deve ser congruente a −1 mo´dulo n. Se j = 0, enta˜o temos apenas que bq ≡ 1
(mod n). Se nada disso acontecer, enta˜o n deve ser composto.
Teste de Miller.
Etapa 1 Divida n− 1 por 2 ate´ encontrar q ı´mpar e k tais que n− 1 = 2kq.
Etapa 2 Fac¸a i = 0 e r = resto de bq por n.
Etapa 3 Se i = 0 e r = 1 ou i ≥ 0 e r = n− 1: teste inconclusivo.
Etapa 4 Fac¸a i = i+ 1 e r = r2 onde r2 e´ o resto da divisa˜o de r
2 por n.
Etapa 5 Se i < k volte a` etapa 3; sena˜o: n e´ composto.
Exemplo 7 Tome o nu´mero de Carmichael 561. Temos que 560 = 24.35.
Calculando as sequeˆncias de restos mo´dulo 561 das poteˆncias de 2:
expoentes 35 2.35 22.35 23.35
restos 263 166 67 1
28
Logo 561 tem que ser composto.
Se um nu´mero composto n tem resultado inconclusivo para o teste de Miller
com respeito a uma base b, dizemos que n e´ um pseudoprimo forte para a
base b. Observe que pseudoprimo forte −→ pseudoprimo.
Existem 1282 pseudoprimos fortes entre 1 e 109.
9.4 Primalidade e computac¸a˜o alge´brica
E´ importante ressaltar que o teste de Miller e´ muito usado na pra´tica. O que
se faz para ter maior garantia do resultado e´ fazer o teste para diversas bases.
E´ assim com o Maple, ScratchPad - IBM, Axiom 1.1 - IBM.
Vale a observac¸a˜o: dado um nu´mero finito qualquer de bases, existem infinitos
nu´meros de Carmichael que sa˜o pseudoprimos fortes para todas essas bases.
9.5 Exerc´ıcios propostos
2, 5, 7, 8, 10
10 Teorema de Euler
O pequeno teorema de Fermat nos diz como trabalhar com certas congrueˆncias
envolvendo expoentes quando o mo´dulo e´ primo. Nessa sec¸a˜o, veremos como
lidar com congrueˆncias mo´dulo um nu´mero composto.
10.1 Func¸a˜o de Euler
Definic¸a˜o. Seja n um inteiro positivo. A func¸a˜o de Euler φ(n) e´ definida
como o nu´mero de inteiros positivos na˜o excedendo n que sa˜o relativamente
primos com n.
A tabela abaixo apresenta os valores de φ(n) para 1 ≤ n ≤ 12.
n 1 2 3 4 5 6 7 8 9 10 11 12
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4
Na sec¸a˜o de aritme´tica modular, estudamos o conjunto U(n), o conjunto dos
elementos de Zscrn que teˆm inverso. Vimos que
U(n) = {a ∈ Zn : mdc(a, n) = 1}
29
Desta forma, φ(n) nada mais e´ do que o nu´mero de elementos de U(n).
Vamos ver como calcular φ(n). Comec¸amos com alguns casos especiais. Seja p
um nu´mero primo. Enta˜o todos os inteiros positivos menores que p sa˜o primos
com p. Logo
φ(p) = p− 1
Tambe´m e´ fa´cil calcular φ(pk). Observe que mdc(a, pk) = 1 se e somente se
p na˜o divide a. Enta˜o basta contar os inteiros menores que pk que na˜o sa˜o
divis´ıveis por p. Se 0 ≤ a < pk e´ divis´ıvel por p, enta˜o
a = p.b onde 0 ≤ b < pk − 1
Portanto ha´ pk−1 inteiros positivos menores que pk que sa˜o divis´ıveis por p.
Logo ha´ pk − pk−1 que na˜o sa˜o divis´ıveis por p. Ou seja,
φ(pk) = pk−1(p− 1)
Para obtermos a fo´rmula geral, e´ necessa´rio provar o seguinte resultado:
Teorema. Se m,n sa˜o inteiros positivos tais que mdc(m,n) = 1, enta˜o
φ(mn) = φ(m).φ(n)
A demonstrac¸a˜o desse teoremae´ trabalhosa (mas na˜o dif´ıcil) e portanto na˜o
faremos aqui.
Exemplo 8 φ(100) = φ(22).φ(52) = (2.1).(5.4) = 40
Pelo teorema acima temos que, se n = pe11 . . . . .p
ek
k , enta˜o,
φ(n) = pe1−11 . . . . .p
ek−1
k (p1 − 1). . . . .(pk − 1)
10.2 Teorema de Euler
Vai ser necessa´rio, para decodificac¸a˜o de mensagens, saber calcular a func¸a˜o
de Euler. Tambe´m vamos ter que aplicar o teorema de Euler. O teorema
de Euler e´ uma generalizac¸a˜o do teorema de Fermat para o caso em que o
mo´dulo na˜o e´ primo:
Teorema de Euler. Se n e´ um inteiro positivo e a e´ um inteiro tal que
mdc(a, n) = 1, enta˜o
aφ(n) ≡ 1 (mod n)
Antes de provar esse teorema, vamos apresentar um exemplo.
30
Exemplo 9 Temos que U(8) = {1, 3, 5, 7} e portanto φ(8) = 4. Observe que,
se a, b, c ∈ U(8), enta˜o a.b ∈ U(8) e, se c 6= b, enta˜o
a.b\ ≡ a.c (por que?)
Para ver como isso funciona, tome a = 3. Enta˜o,
3.1 ≡ 3 (mod 8)
3.3 ≡ 1 (mod 8)
3.5 ≡ 7 (mod 8)
3.7 ≡ 5 (mod 8)
Logo,
(3.1).(3.3).(3.5).(3.7) ≡ 1.3.5.7 (mod 8)
e portanto,
34.1.3.5.7 ≡ 1.3.5.7 (mod 8)
Como mdc(1.3.5.7, 8) = 1, podemos cortar o termo comum dos dois lados da
equivaleˆncia:
34 ≡ 1 (mod 8)
Teorema 14 (Teorema de Euler) Se n e´ um inteiro positivo e a um inteiro
tal que mdc(n, a) = 1, enta˜o
aφ(n) ≡ 1 (mod n)
Prova Escrevendo U(n) = {b1, . . . , bφ(n)}, temos que:
(a.b1). . . . .(a.bφ(n)) ≡ b1. . . . .bφ(n) (mod n)
Logo,
aφ(n).b1. . . . .bφ(n) ≡ b1. . . . .bφ(n) (mod n)
Como mdc(b1. . . . .bφ(n), n) = 1, podemos cortar o termo comum dos dois lados
e portanto,
aφ(n) ≡ 1 (mod n)
10.3 Exerc´ıcios propostos
Cap´ıtulo 8: 4, 6, 8, 9, 10, 18
31
10.4 Tabela Hashing
Uma universidade deseja estocar um arquivo para cada um de seus estudantes
no seu computador. O nu´mero identificador, ou chave para cada arquivo e´ o
nu´mero do CPF do estudante. O CPF e´ um inteiro de 11 d´ıgitos, portanto
e´ praticamente imposs´ıvel reservar uma posic¸a˜o de memo´ria para cada CPF
poss´ıvel. Deve-se encontrar um me´todo sistema´tico para arranjar esses arquivos
na memo´ria, usando um nu´mero razoa´vel de posic¸o˜es de memo´ria. De outra
forma, ficaria imposs´ıvel acessar os arquivos...
Um desses me´todos e´ utilizando a tabela hashing , baseada em func¸o˜es
hashing . Existem va´rias propostas para func¸o˜es hashing. Vamos discutir
(brevemente) o tipo mais utilizado.
Seja k a chave do arquivo a ser estocado e seja n um inteiro positivo. Definimos
a func¸a˜o hashing h(k) por
h(k) ≡ k (mod n)
onde 0 ≤ h(k) < n. E´ claro que devemos escolher um n adequado de modo que
os arquivos fiquem distribu´ıdos de uma maneira razoa´vel entre as n posic¸o˜es
poss´ıveis de memo´ria.
Por exemplo, n na˜o deve ser uma poteˆncia de 10 (10r) simplesmente porque o
valor da func¸a˜o h seria os r u´ltimos d´ıgitos da chave.
Outro exemplo de uma escolha ruim e´ quando n|10m ± a onde a e m sa˜o pe-
quenos. Por exemplo, se n = 111|(103 − 1) = 999 enta˜o 103 ≡ 1 (mod n) e
portanto os nu´meros:
64121284868 e 64184821268
va˜o para a mesma posic¸a˜o de memo´ria.
Para evitar esses problemas, n deve ser um nu´mero primo pro´ximo do nu´mero
de posic¸o˜es dispon´ıveis. Por exemplo, se existem 5000 posic¸o˜es de memo´ria para
o armazenamento de 2000 arquivos de estudantes, podemos escolher n = 4969.
Claro que, mesmo assim, coliso˜es podem ocorrer. Existem va´rias heur´ısticas
para tratamento de coliso˜es. O me´todo mais usado e´ o de escolher uma posic¸a˜o
livre. Existem va´rias maneiras de fazer isso e as mais complicadas sa˜o as mais
eficientes. Eu poderia passar o dia falando sobre elas, mas vou citar apenas
uma, a mais simples. Consiste em tomar:
hj(k) ≡ h(k) + j (mod n)
Desta forma, a chave k e´ alocada na posic¸a˜o mais pro´xima poss´ıvel de h(k).
A eficieˆncia desse me´todo e´ realmente baixa, pois tende a haver um engarrafa-
mento.
Na pra´tica, o mais fa´cil e´ “atachar” uma lista a cada posic¸a˜o de memo´ria. Dessa
forma, procede-se por busca sequencial.
32
11 Criptografia RSA
11.1 Pre´-codificac¸a˜o
Em primeiro lugar, devemos converter a mensagem em uma sequeˆncia de nu´meros.
Essa primeira etapa e´ chamada de pre´-codificac¸a˜o. Ha´ va´rias maneiras de se
fazer isso. Aqui vamos supor que o texto na˜o conte´m acentuac¸a˜o, pontuac¸a˜o,
nu´meros etc, apenas as letras A a Z (maiu´sculas). Tambe´m vamos adicionar
espac¸os em branco entre palavras, que sera´ substitu´ıdo pelo nu´mero 99. A letra
A sera´ convertida no nu´mero 10, B sera´ 11 e assim por diante, ate´ o Z corre-
spondendo ao nu´mero 35. Observe que cada letra corresponde a um nu´mero
com exatamente dois algarismos. Isso evita ambiguidades.
A chave pu´blica e´ um nu´mero n = p.q, onde p e q sa˜o primos. Antes de comec¸ar
devemos, enta˜o escolher esses nu´meros. O u´ltimo passo da pre´-codificac¸a˜o e´
quebrar a mensagem em blocos. Esses blocos devem ser nu´meros menores
que n. A maneira de escolher os blocos na˜o e´ u´nica, mas e´ importante evitar
duas situac¸o˜es:
• Nenhum bloco deve comec¸ar com o nu´mero 0 (problemas na decodi-
ficac¸a˜o).
• Os blocos na˜o devem corresponder a nenhuma unidade lingu´ıstica (palavra,
letra, etc). Assim a decodificac¸a˜o por contagem de frequeˆncia fica im-
poss´ıvel.
11.2 Codificando e decodificando
Para codificar a mensagem precisamos de n = p.q e de um inteiro positivo e que
seja invers´ıvel mo´dulo φ(n). Em outras palavras,
mdc(e, φ(n)) = mdc(e, (p− 1).(q − 1)) = 1
Chamaremos o par (n, e) a chave de codificac¸a˜o do sistema RSA.
Codificaremos cada bloco de mensagem separadamente e a mensagem codificada
sera´ a sequeˆncia de blocos codificados.
Importante: Os blocos ja´ codificados na˜o podera˜o ser reunidos de modo a formar
um longo nu´mero. Isso tornaria a decodificac¸a˜o imposs´ıvel!
Vamos agora mostrar como codificar cada bloco b. Chamaremos o bloco codifi-
cado de C(b). Em primeiro lugar, lembre-se que b e´ menor que n. Enta˜o:
C(b) ≡ be (mod n)
Onde 0 ≤ C(b) < n.
33
Exemplo 10 Considere a frase Paraty e´ linda . Convertendo em nu´meros,
2510271029349914992118231310
Agora devemos escolher n. Vamos comec¸ar com um nu´mero pequeno, por ex-
emplo
n = 11.13 = 143
Podemos enta˜o quebrar a mensagem acima em blocos, que devem ter valor
menor que 143:
25− 102− 7− 102− 93− 49− 91− 49− 92− 118− 23− 13− 10
Enta˜o temos que φ(143) = 10.12 = 120 e portanto e deve ser um nu´mero que
na˜o divide 120. O menor valor poss´ıvel e´ 7. Logo,
C(25) ≡ 257 ≡ 2522 .252.25 (mod 143)
≡ 2522 .53.25 (mod 143)
≡ 532.53.25 (mod 143)
≡ 92.53.25 (mod 143)
≡ 14.25 (mod 143)
≡ 64 (mod 143)
Procedendo dessa maneira com todos os blocos, obtemos a seguinte mensagem
cifrada:
64− 119− 6− 119− 102− 36− 130− 36− 27− 79− 23− 117− 10
Vejamos agora como proceder para decodificar um bloco de mensagem codifi-
cada. A informac¸a˜o que precisamos para decodificar esta´ contida no par (n, d),
onde d e´ o inverso de e mo´dulo φ(n). Chamaremos (n, d) de chave de de-
codificac¸a˜o e de D(c) o resultado do processo de decodificac¸a˜o. D(c) e´ dado
por:
D(c) ≡ cd (mod n)
onde 0 ≤ D(c) < n.
Observe que e´ muito fa´cil calcular d, desde que φ(n) e e sejam conhecidos: basta
aplicar o algoritmo euclideano estendido. Entretanto, se na˜o conhecemos p e q
e´ praticamente imposs´ıvel calcular d.
Voltando ao nosso exemplo, temos que n = 143 e e = 7. Para calcular d, usamos
o algoritmo euclideano estendido:
120 = 7.17 + 1 =⇒ 1 = 120 + (−17).7
Logo o inverso de 7 mo´dulo 120 e´ −17. Como d deve ser usado como um
expoente, precisamos que d seja positivo. Logo tomamos d = 120− 117 = 103.
34
11.3 Funciona?
A pergunta o´bvia que surge agora e´:
D(C(b)) = b?
Ou seja, decodificando um bloco de mensagem codificada, encontramos um bloco
da mensagem original? Porque sena˜o todo nosso esforc¸o foi sem sentido...
Vamos mostrar nessa sec¸a˜o que a resposta para a perguntaacima e´ sim .
Consideremos enta˜o n = p.q. Vamos provar que
DC(b) ≡ b (mod n)
E por que na˜o a igualdade? Observe que DC(b) e b sa˜o menores que n − 1.
Por isso escolhemos b menor que n e mantivemos os blocos separados depois da
codificac¸a˜o!
Por definic¸a˜o, temos que
DC(b) ≡ (be)d ≡ be.d (mod n)
Mas d e´ o inverso de e mo´dulo φ(n). Logo existe inteiro k tal que ed = 1+kφ(n).
Logo,
bed ≡ b1+kφ(n) ≡ (bφ(n))k.b (mod n)
Se mdc(b, n) = 1, enta˜o podemos usar o teorema de Euler:
bed ≡ (bφ(n))k.b ≡ b (mod n)
Se b e n na˜o sa˜o primos entre si, obderve que n = p.q, p e q primos distintos.
Logo,
bed ≡ b1+kφ(n) ≡ (b(p−1))k.(q−1).b (mod p)
Semdc(b, p) = 1, enta˜o podemos usar o teorema de Fermat (bp−1 ≡ 1 (mod p)).
Se na˜o, temos que p|b e portanto
bed ≡ b ≡ 0 (mod p)
Logo,
bed ≡ b (mod p)
qualquer que seja b.
Fazemos o mesmo para o primo q, obtendo:
bed ≡ b (mod q)
Portanto,
bed ≡ b (mod p.q)
como quer´ıamos.
35
11.4 Porque o RSA e´ seguro
Como ja´ vimos, o par de codificac¸a˜o (n, e) e´ conhecido e acess´ıvel a qualquer
usua´rio. O RSA so´ e´ seguro se for dif´ıcil calcular d quando apenas esse par e´
conhecido.
Observe que so´ sabemos calcular d se soubermos o valor de φ(n), cujo ca´lculo
depende da fatorac¸a˜o de n. A pergunta que surge enta˜o e´: sera´ que na˜o existe
outro processo para calcular d e φ(n)? Por exemplo, o que aconteceria se algue´m
inventasse um me´todo para calcular φ(n) a partir de n e e? A resposta e´ que
ter´ıamos, enta˜o, um algoritmo ra´pido de fatorac¸a˜o. Observe que
φ(n) = (p− 1).(q − 1) = pq − (p+ q) + 1 = n− (p+ q) + 1
Logo, (p+ q) = n− φ(n) + 1 e´ conhecido. Contudo,
(p+ q)2 − 4n = (p2 + q2 + 2pq)− 4pq = (p− q)2
Logo,
p− q =
√
(p+ q)2 − 4n
que tambe´m e´ conhecido. Ou seja, conhecemos p+q e p−q. Portanto conhecemos
p e q e fatoramos n!
Deste modo, conhecer φ(n) sem fatorar n significa que, na verdade, sabemos
fatorar n!
Outro jeito de quebrar o RSA seria achar um algoritmo que calcule d diretamente
a partir de n e e. Como ed ≡ 1 (mod φ(n)), isto implica que conhecemos um
mu´ltiplo de φ(n). Isso tambe´m e´ suficiente para fatorar n (prova complicada).
A u´ltima alternativa seria achar b a partir da forma reduzida de be mo´dulo n
sem achar d. Bom, ningue´m conseguiu fazer isso ate´ agora... Acredita-se que
quebrar o RSA e fatorar n sejam problemas equivalentes, apesar disso na˜o ter
sido demonstrado.
11.5 Escolhendo primos
Suponha que desejamos implementar o RSA de chave pu´blica (n, e), de modo que
n seja um inteiro com aproximadamente r algarismos. Para construir n, escolha
um primo p entre 4r10 e
45r
100 algarismos e, em seguida, escolha q pro´ximo de
10r
p
. O
tamanho da chave recomendado atualmente para uso pessoal e´ de 768 bits. Isso
significa que n tera´ aproximadamente 231 algarismos. Para construir tal nu´mero
precisamos de dois primos de, digamos, 104 e 127 algarismos respectivamente.
Outra coisa a ser observada e´ que os nu´meros p−1, q−1, p+1, p−1 na˜o tenham
fatores primos pequenos, pois sena˜o seria fa´cil fatorar n.
Para encontrar p e q, seguiremos a seguinte estrate´gia:
1. Tome um nu´mero s ı´mpar.
36
2. Verifique se n e´ divis´ıvel por um primo menor que 5.000.
3. Aplique o teste de Miller a s usando como base os 10 primeiros primos.
Encontrar tais primos pode ser um processo trabalhoso. Por exemplo, se x e´
um nu´mero da ordem de 10127, no intervalo entre x e x + 104 existem aproxi-
madamente 34 primos dentre 560 nu´meros que passam a etapa (1) da estrate´gia
acima...
11.6 Assinaturas
Apenas codificar mensagens na˜o basta, em geral, pois o sistema e´ de chave
pu´blica. Ou seja, qualquer pessoa pode codificar uma mensagem usando uma
chave alheia. Por exemplo, um haker poderia facilmente mandar instruc¸o˜es ao
banco para que o seu saldo banca´rio fosse transferido para uma outra conta.
Por isso, o banco precisa de uma garantia de que a mensagem teve origem em
um usua´rio autorizado. Ou seja, a mensagem tem que ser assinada .
Vamos chamar de Cm e Dm as func¸o˜es de codificac¸a˜o e decodificac¸a˜o do Ma´rio
e de Ca e Da as func¸o˜es de codificac¸a˜o e decodificac¸a˜o do Allan. Seja b um
bloco de mensagem que o Ma´rio deseja mandar para o Allan. Para mandar
uma mensagem assinada, ao inve´s de Ca(b), o Ma´rio envia
Ca(Dm(b))
Ou seja, primeiro ele “decodifica” a mensagem como so´ ele pode fazer, depois ele
codifica o resultado, como so´ o Allan pode ler. Para ler a mensagem, primeiro o
Allan aplica Da e depois Cm. Observe que Cm e´ pu´blico. Se a mensagem fizer
sentido, e´ certo que a origem foi mesmo o Ma´rio!
Mas cuidado ! Esse sistema pode ser usado para quebrar o RSA, como em
1995 por um consultor em assuntos de seguranc¸a de computadores...
11.7 Exerc´ıcios propostos
Cap´ıtulo 11: 1, 2, 3, 4, 6.
12 1o trabalho pra´tico
O trabalho tem como objetivo a criac¸a˜o de dois nu´meros primos grandes (entre
20 e 30 bits). Para isso:
• Gere dois nu´meros ı´mpares m e k da magnetude acima, de modo que na˜o
sejam muito pro´ximos um do outro.
37
• Verifique se m, k sa˜o divis´ıveis por um primo menor que 5.000.
• Aplique o teste de Miller a m, k usando como base os 10 primeiros primos
(se voceˆ quiser ter uma certeza maior sobre o resultado, fac¸ø teste para
mais primos).
Depois calcule n = m.k e aplique os algoritmos da fatorac¸a˜o e de Fermat a n
para ver se sua chave pu´blica e´ facilmente quebrada.
O trabalho devera´ ser entregue no dia 06/08/2002 (sem falta!) e devera´
constar de:
• Parte escrita de no ma´ximo duas pa´ginas digitadas. Essa parte de-
vera´ conter os resultados do trabalho juntamente com a ana´lise desses
resultados (em especial, se foi fa´cil quebrar a sua chave ou na˜o).
• Co´digo impresso comentado . Evitem C++, por favor!
• Disquete com o executa´vel do programa. Este tambe´m pode ser enviado
por e-mail. Lembrem-se que eu posso rodar apenas programas em Delphi
(4.0) ou qualquer outra linguagem que rode nas estacoes do DCC. Enta˜o
evitem artif´ıcios gra´ficos sofisticados...
13 Ra´ızes primitivas
13.1 Teste de Lucas
Para determinar se n e´ primo, podemos verificar se φ(n) = n − 1. Ou seja, se
mdc(a, n) = 1 para todo a menor que n. Isso so´ e´ poss´ıvel se n e´ ı´mpar. Logo
precisamos encontrar um jeito de calcular φ(n) sem fatorar n. Mas ja´ vimos
que isso e´ imposs´ıvel...
Teorema da raiz primitiva. Se p e´ um primo, existe b ∈ Zn tal que
bp−1 ≡ 1 (mod p)
mas
br\ ≡ 1 (mod p)
se r < p− 1.
Em geral, chamaremos de ordem do elemento b em Zn o nu´mero k tal que
bk ≡ 1 (mod n) e br\ ≡ 1 (mod n) se r < k. Observe que se n e´ primo e
1 < b < n, enta˜o a ordem de b e´ p− 1.
38
Teorema de Lagrange. A ordem de b tem que dividir a ordem de U(n), que
e´ igual a φ(n).
Logo, dado n ı´mpar, se existe b tal que bn−1 ≡ 1 (mod n) e bt\ ≡ 1 (mod n)
se t < n− 1 enta˜o n e´ primo pois ter´ıamos n− 1 ≤ φ(n) ≤ n− 1.
De acordo com o teorema da raiz primitiva, se n e´ primo, tal b sempre existe.
Encontra´-lo e´ uma questa˜o de sorte...
Para aplicar isso a` primalidade, precisamos encontrar uma maneira eficiente de
mostrar que a ordem de um elemento de U(n) e´ exatamente n− 1.
Teste de Lucas. Sejam n ´ impar e 1 ≤ b ≤ n− 1. Se
bn−1 ≡ 1 (mod n)
e
b
n−1
p \ ≡ 1 (mod n)
para cada fator primo de n− 1, enta˜o n e´ primo.
Demonstrac¸a˜o: Veja o livro texto pag 168.
Continua... Aguardem!
14 Sistemas de congrueˆncias
O objetivo dessa sec¸a˜o e´ estudar a soluc¸a˜o de sistemas de equac¸o˜es lineares. A
aplicac¸a˜o para criptografia e´ o desenvolvimento de um me´todo para partilhar
senhas.
14.1 Equac¸o˜es lineares
Ja´ estudamos o caso de uma equac¸a˜o linear
ax ≡ b (mod n)
Se a possui um inverso α em Zn, enta˜o multiplicando ambos os lados da equac¸a˜o
acima por α:
α(ax) ≡ αb (mod n)
x ≡ αb (mod n)
Em particular, se n e´ primo e a\ ≡ 0 (mod n),enta˜o a equac¸a˜o acima sempre
tem soluc¸a˜o.
39
Se a na˜o tem inverso em Zn, enta˜o mdc(a, n) = d 6= 1. Logo, a equac¸a˜o:
ax− ny = b
so´ tem soluc¸a˜o quando b e´ divis´ıvel por d.
Suponhamos enta˜o que d divide b. Escreveremos a = da′, b = db′ e n = dn′.
Cancelando os d’s, chegamos a` seguinte equac¸a˜o:
a′x− n′y = b′
Ou seja,
a′x ≡ b′ (mod n′)
Observe que agora mdc(a′, n′) = 1, e essa equac¸a˜o sempre tem soluc¸a˜o.
Exemplo 11 Seja 6x ≡ 4 (mod 8). Dividindo pelo mdc(6, 8) = 2, obtemos
3x ≡ 2 (mod 4)
Logo a soluc¸a˜o procurada e´:
x ≡ 2 (mod 4)
Mas observe que o mo´dulo mudou de 8 para 4... Para consertar isso, vamos
escrever a expressa˜o acima em uma expressa˜o de inteiros:
x = 2 + 4k
Duas possibilidades:
• k e´ par. Nesse caso, x ≡ 2 (mod 8) e 2 e´ uma soluc¸a˜o.
• k e´ ı´mpar (k = 2m+1). Nesse caso, x ≡ 6 (mod 8) e 6 e´ outra soluc¸a˜o.
Ou seja, uma equac¸a˜o linear possui mais de uma soluc¸a˜o.
14.2 Um exemplo astronoˆmico
Treˆs sate´lites passara˜o sobre o Rio essa noite. O primeiro a` uma hora , o
segundo a`s 4 horas e o terceiro a`s 8 horas da manha˜. O primeiro leva 13 horas
para completar uma volta em torno da terra, o segundo 15 horas e o terceiro 19
horas. Determine quantas horas decorrera˜o, a` partir de meia noite, ate´ que os
treˆs sate´lites passem ao mesmo tempo sobre o Rio.
Montagem matema´tica: seja x e´ o nu´mero de horas, contadas a partir da meia
noite de hoje, quando os treˆs sate´lites passara˜o juntos sobre o Rio. Enta˜o:
x ≡ 1 (mod 13)
x ≡ 4 (mod 15)
x ≡ 8 (mod 19)
40
Podemos re-escrever a primeira equac¸a˜o cmo x = 1 + 13t, Substituindo a
primeira equac¸a˜o na segunda, obtemos:
t ≡ 6 (mod 15)
Logo x = 79 + 195u. Substituindo essa equac¸a˜o na terceira:
u ≡ 1 (mod 19)
Logo,
x = 79 + 195u
= 274 + 3705v
Logo os sate´lites passara˜o juntos pela primeira vez 274 horas depois da meia
noite de hoje.
14.3 Algoritmo chineˆs do resto
Observe que, para resolver o problema dos sate´lites, resolvemos as duas primeiras
equac¸o˜es, obtendo x = 79+195u. Isso corresponde a uma nova equac¸a˜o, x ≡ 79
(mod 195). Em geral, a soluc¸a˜o de um sistema de muitas equac¸o˜es e´ obtida
atrave´s da soluc¸a˜o de va´rios sistemas de duas equac¸o˜es. Desta forma, vamos
analisar apenas o algoritmo correspondente a´ soluc¸a˜o de um sistema de duas
equac¸o˜es.
Considere enta˜o o sistema
x ≡ a (mod m)
x ≡ b (mod n)
Podemos re-escrever a primeira equac¸a˜o na forma:
x = a+my
Substituindo x na segunda equac¸a˜o, obtemos:
my ≡ (b− a) (mod n)
Sabemos que essa equac¸a˜o tem soluc¸a˜o se e somente se o mdc(n,m) divide b−a.
Vamos assumir que mdc(n,m) = 1. Seja enta˜o α o inverso de m mo´dulo n.
Enta˜o:
y ≡ α(b− a) (mod n)
y = α(b− a) + nz
x = a+mα(b− a) +mnz
x = a(1−mα) +mαb+mnz
x = aβn+mαb+mnz
Observe que essa soluc¸a˜o e´ u´nica. Temos enta˜o o seguinte teorema:
41
Teorema Chineˆs do resto. Sejam n1, . . . , nk inteiros positivos, dois a dois
primos entre si. Enta˜o o sistema
x ≡ a1 (mod n1)
...
x ≡ ak (mod nk)
sempre tem uma soluc¸a˜o u´nica em Zn1...nk .
14.4 Mo´dulos na˜o co-primos
Analisaremos esse caso atrave´s de um exemplo. Considere o sistema:
x ≡ 3 (mod 12)
x ≡ 19 (mod 8)
Da primeira equac¸a˜o, obtemos x = 3 + 12y. Substituindo isso na segunda
equac¸a˜o, temos 12y ≡ 16 (mod 8). Dividindo essa equac¸a˜o por 4, obtemos
3y ≡ 4 (mod 2). Logo,
x ≡ 3 (mod 24)
Observe que 24 e´ o mmc entre 8 e 12...
14.5 Partilha de senhas
Suponha que que desejemos partilhar uma senha s entre n pessoas, de modo
que a cada pessoa seja dado um elemento (uma parte) da senha. Esse elemento
e´ tal que e´ escolhido de um conjunto S de n pares de inteiros positivos de modo
que, para um inteiro positivo k ≤ n previamente escolhido temos:
1. qualquer subconjunto de S com k elementos permite determinar s facil-
mente;
2. e´ muito dif´ıcil determinar s conhecendo menos de k elementos de S.
Comec¸amos escolhendo um conjunto L de n inteiros positivos, dois a dois primos
entre si. Seja N o produto dos k menores nu´meros de L e M o produto dos
k − 1 maiores nu´meros de L. Dizemos que esse conjunto tem limiar k se
N > s >M
Observe que essa condic¸a˜o implica que o produto de k ou mais elementos de L
e´ sempre maior que N e o produto de menos de k elementos e´ sempre menor
queM. O conjunto S sera´ formado pelos pares da forma (m, sm) onde m ∈ L e
sm e´ a forma reduzida de s mo´dulo m. Observe que limiar k ≥ 1 implica s > m
para qualquer m ∈ L. Logo sm < s para qualquer m ∈ L.
42
Suponhamos que sejan conhecidos, em um dado momento, t elementos, ≥ k.
Denotaremos esses pares por (m1, s1), . . . , (mt, st). Vamos resolver o sistema de
congrueˆncias:
x ≡ s1 (mod m1)
x ≡ s2 (mod m2)
. . .
x ≡ st (mod mt)
obtendo x0 como soluc¸a˜o. Pelo teorema chineˆs do resto,
x0 ≡ s (mod m1. . . . .mt)
Por que? Sabemos que, como t ≥ k,
m1. . . . .mt ≥ N > s
Pelo teorema chineˆs do resto, o sistema acima tem uma u´nica soluc¸a˜o menor
que m1. . . . .mt. Mas s tambe´m e´ soluc¸a˜o do sistema e s < m1. . . . .mt. Logo
s = x0.
Observac¸o˜es:
1. E´ poss´ıvel escolher os mo´dulos de modo que fique praticamente imposs´ıvel
encontrar s atrave´s de uma busca.
2. E´ sempre poss´ıvel escolher um conjunto L que satisfac¸a todas as condic¸o˜es.
Exemplo 12 Digamos que em um banco ha´ 5 funciona´rios e pelo menos 2 teˆm
que estar presentes para que o cofre seja aberto. Logo o conjunto L deve ter
5 elementos, e seu limiar deve ser 2. Uma escolha poss´ıvel escolhendo apenas
primos pequenos e´
L = {11, 13, 17, 19, 23}
O valor de s pode ser escolhido como sendo qualquer inteiro no intervalo que
vai de 23 a 143. Digamos s = 30. Enta˜o:
S = {(11, 19), (13, 17), (17, 13), (19, 11), (23, 7)}
Se os funciona´rios que possuem as senhas (17, 13) e (23, 7) esta˜o no banco, para
obter a senha e´ preciso resolver o sistema
x ≡ 13 (mod 17)
x ≡ 7 (mod 23)
A soluc¸a˜o e´ x = 30 + 391k...
14.6 Exerc´ıcios propostos
1,2,4
43
15 Lo´gica e cieˆncia da computac¸a˜o
15.1 Motivac¸a˜o
Lo´gica em cieˆncia da computac¸a˜o:
• Primeira abordagem computac¸a˜o-como-modelo: computac¸o˜es sa˜o estru-
turas matema´ticas contendo nodos, estados e transic¸o˜es e a lo´gica constro´i
afirmativas sobre essas estruturas.
• Segunda abordagem computac¸a˜o-como-deduc¸a˜o: estados sa˜o descritos atrave´s
de um conjunto de proposic¸o˜es e mudanc¸as nos estados sa˜o modelados por
mudanc¸as nas proposic¸o˜es dentro de uma derivac¸a˜o (ou seja, por passos
na construc¸a˜o de uma prova)
A primeira abordagem tem sido amplamente estudada e faz uso de to´picos
da matema´tica como teoria de conjuntos, teoria das categorias, a´lgebras, etc.
para modelar computac¸o˜es. Em geral, as estruturas matema´ticas utilizadas sa˜o
complexas porque devem lidar com o conceito de infinitude.
A segunda abordagem, apesar de lidar com estruturas mais simples (que rara-
mente fazem refereˆncia ao infinito) e de estar mais intimamente ligada a` com-
putac¸a˜o, tem merecido pouca ou nenhuma atenc¸a˜o nos u´ltimos tempos.
Apenas apo´s recentes pesquisas na a´rea de teoria de provas e programac¸a˜o lo´gica
observou-se um crescimento do estudo nessa a´rea de pesquisa.
Lo´gicas expressivas como lo´gica linear (e Forum - linguagem de programac¸a˜o
baseada em lo´gica linear) passaram a ser utilizadas para modelar estados, transic¸o˜es
de estado e algumas primitivas de concorreˆncia.
15.2 Lo´gica Cla´ssica
• A verdade de uma afirmativa e´ absoluta e independe da quaisquer pensa-
mento, entendimento ou ac¸a˜o.
• Afirmativas sa˜o verdadeiras ou falsas, onde falso e´ a mesma coisa que na˜o
verdadeiro.
• Isso e´ conhecido com princ´ıpio do meio exclu´ıdo: p∨⌉p.
15.3 Lo´gica Intuicionista
• Em p∨⌉p nenhuma informac¸a˜o e´ dada sobre qual realmente vale:
44
Existem dois nu´meros irracionais x e y taisque xy e´ racional.
Existem sete 7s consecutivos na representac¸a˜o decimal do nu´mero
π.
• Afirmativas so´ sa˜o va´lidas perante a existeˆncia de uma prova ou construc¸a˜o
da afirmativa.
• Essa lo´gica e´ de especial interesse porque suas fo´rmulas esta˜o em corre-
spondeˆncia 1 a 1 com tipos em λ-calculus, base das linguagens de pro-
gramac¸a˜o funcionais: Lisp, ML, Haskell.
• Ainda, lo´gica intuicionista e´ uma lo´gica de recursos infinitos (mas na˜o de
concluso˜es infinitas).
15.4 Lo´gica linear
• Lo´gica linear e´ uma lo´gica de recursos conscientes.
• No caso de transic¸a˜o de estados:
maior tem valor 1 −◦ maior tem valor 2
• E´ claro que a proposic¸a˜o { maior tem valor 1} deve deixar de ser va´lida
no estado 2, enquanto que a proposic¸a˜o { maior tem valor 2}, que na˜o
era va´lida no estado 1, passa a valer no estado 2.
• Esse tipo de comportamento na˜o pode ser descrito em lo´gicas cla´ssica ou
intuicionista, apenas em lo´gica linear.
15.5 Linguagens lo´gicas de programac¸a˜o - Prolog
• Uma definic¸a˜o comum das cla´usulas de Horn e´ dada de acordo com a
seguinte grama´tica:
G ::= A|G ∧G
D ::= A|G ⊃ A|∀xD
• Ou seja, fo´rmulas gol sa˜o conjunc¸o˜es de fo´rmulas atoˆmicas e cla´usulas de
programas sa˜o da forma:
∀x1 . . . ∀xm[A1 ∧ . . . ∧An ⊃ A0]
• Observe que, como implicac¸a˜o e quantificac¸a˜o universal na˜o esta˜o pre-
sentes no gol, todas as hipo´teses e termos necessa´rios para completar a
prova devem estar presentes desde o in´ıcio do programa: assinaturas e
programas sa˜o globais.
• Ou seja, nada de mecanismos para modularizac¸a˜o ou construtores de da-
dos!
45
15.6 Linguagens lo´gicas de programac¸a˜o - λ-Prolog
• As fo´rmulas de primeira ordem de Harrop estendem as cla´usulas de Horn,
uma vez que admitem implicac¸o˜es e quantificadores universais no gol:
G ::= A|G ∧G|P ⊃ G|∀xG
D ::= A|G ⊃ A|∀xD
• Deste modo, o programa pode crescer ao longo da prova (modularizac¸a˜o) e
novas constantes podem ser adicionadas ao programa (abstract datatypes)
• Desvantagem: recursos ilimitados para construc¸a˜o de provas.
15.7 Linguagens lo´gicas de programac¸a˜o - Forum
• Lo´gica linear na˜o e´ uma linguagem abstrata de programac¸a˜o.
• Forum e´ uma linguagem lo´gica de programac¸a˜o baseada em lo´gica linear.
Σ:Ψ;∆ −→ Γ;Υ possui uma prova em Forum se e somente se !Ψ,∆ ⊢
Γ, ?Υ.
• Ale´m de modularizac¸a˜o e abstrac¸a˜o de dados tambe´m permite encap-
sulac¸a˜o de estado, concorreˆncia e primitivas de comunicac¸a˜o e sincronizac¸a˜o.
• Cla´usulas em Forum possuem a forma:
∀y¯(G1 →֒ · · · →֒ Gm →֒ G0), (m ≥ 0)
onde G0, . . . , Gm sa˜o fo´rmulas arbitra´rias em Forum e →֒ denota −◦ ou ⊃.
16 A´lgebra e cieˆncia da computac¸a˜o
A principal aplicac¸a˜o de matema´tica em cieˆncia da computac¸a˜o e´ na definic¸a˜o
de semaˆntica formal em linguagens de programac¸a˜o.
“Semaˆntica” e´ geralmente definida como o estudo da relac¸a˜o entre palavras
e sentenc¸as de uma linguagem (escrita ou falada) e os seus significados. E´
uma a´rea que tem recebido, atrave´s dos tempos, muita atenc¸a˜o em lingu¨´ıstica
e filosofia, que estudam o significado de sentenc¸as na linguagem natural. Uma
segunda a´rea de estudo de semaˆntica se concentra no significado de sentenc¸as em
linguagens formais de lo´gica matema´tica, originalmente projetada para servir
como “fundac¸a˜o” da matema´tica. Esta sec¸a˜o visa discutir, brevemente, to´picos
de uma terceira a´rea da semaˆntica: aquela que tem por objetivo desenvolver
te´cnicas para expressar a semaˆntica de linguagens utilizadas para programac¸a˜o
de computadores. Estaremos especialmente interessados no uso de estruturas
matema´ticas tais como grupos, domı´nios e teoria de categorias na descric¸a˜o de
semaˆntica de linguagens imperativas (como o Pascal) e funcionais (como ML,
Haskell).
46
17 Semaˆntica
Tradicionalmente, linguagens de computadores teˆm sido baseadas em uma sequ¨eˆncia
de comandos, determinados por sentenc¸as imperativas. Em linguagem natural,
tais sentenc¸as sa˜o aquelas que podem ser encontradas em um livro de receitas:
Bata a clara do ovo ate´ ficar dura. (1)
Em contraste, sentenc¸as de lo´gica matema´tica visam estabelecer verdades abso-
lutas:
Quando batida, a clara do ovo fica dura. (2)
Muitas pesquisas em me´todos para analisar programas em uma certa linguagem
procuram formalizar a relac¸a˜o entre os dois exemplos citados acima. Afinal
de contas, a sentenc¸a lo´gica (2) garante que uma pessoa que execute o que
manda a sentenc¸a imperativa (1) vai ter sucesso em terminar a tarefa de mudar
a consisteˆncia da clara do ovo.
Desta forma, uma maneira de descrever comandos (que sa˜o sentenc¸as impera-
tivas) de uma linguagem de programac¸a˜o e´ estabelecendo uma relac¸a˜o entre o
estado do computador antes e depois da execuc¸a˜o do comando (como descrito
por sentenc¸as lo´gicas). Essa interpretac¸a˜o relacional de fragmentos de programa
pode ser formalizada atrave´s da semaˆntica denotacional.
Vejamos um exemplo da semaˆntica do comando if. Escreveremos C[·] para de-
notac¸a˜o de um comando e E [·] para denotac¸a˜o de uma expressa˜o. Enta˜o temos:
C[if E then C1 else C2] = E [E]λv.isBool v → (v → C[C1], C[C2])
Da mesma forma, podemos escrever a semaˆntica do comando while como:
C[while E do C] = E [E]λv.isBool v → (v → C[C], C[while E do C])
ou, mais simplesmente, podemos escrever:
C[while E do C] = C[C]; C[while E do C])
Antes de falarmos um pouco sobre esse tipo de semaˆntica, vamos responder
a` uma pergunta fundamental: qual e´ o objetivo de se estudar semaˆntica de
linguagens de programac¸a˜o? Bem, quando essa a´rea surgiu, o objetivo era prover
uma descric¸a˜o suficientemente precisa para tornar poss´ıvel aos implementadores
construir um compilador para a linguagem em questa˜o. Hoje em dia, a eˆnfase
esta´ em:
1. fornecer uma descric¸a˜o precisa para os programadores, tornando poss´ıvel
que estes fac¸am afirmativas rigorosas sobre o comportamento de progra-
mas por eles escritos;
47
2. fornecer ferramentas para os designers de linguagens de programac¸a˜o, para
que possam sugerir linguagens melhores, confia´veis e com descric¸o˜es for-
mais simples.
Ou seja, a grande vantagem e´ que desenvolve-se um me´todo matema´tico (e por-
tanto formal) que garante corretude tanto de programas quanto da linguagens
desenvolvidas.
18 Semaˆntica Denotacional
E´ a semaˆntica que mapeia construtores sinta´ticos de programas em valores ab-
stratos (nu´meros, func¸o˜es, etc) que eles denotam. Esses “mapeamentos” sa˜o
usualmente definidos recursivamente (como no cado do while acima). E´ claro
que alguns cuidados devem ser tomados quando trabalhamos com func¸o˜es re-
cursivas. Em especial, para “modelar” o espac¸o de todas as func¸o˜es recursi-
vas precisar´ıamos de um conjunto X que contivesse todo o espac¸o de func¸o˜es
X −→ X. Por questo˜es de cardinalidade, sabemos que isso e´ imposs´ıvel. Para
lidar com essa dificuldade, foi proposto, em 1969, um modelo para func¸o˜es re-
cursivas X −→ X restritas a func¸o˜es cont´ınuas em X (de acordo com uma certa
topologia).
Esse modelo, chamado de teoria de domı´nio, e´ utilizado para descrever a semaˆntica
denotacional do λ-calculus, base de linguagens de programac¸a˜o funcionais. E,
utilizando o λ-calculus, podemos facilmente descrever a semaˆntica denotacional
de linguagens como o Algol60, base do Pascal.
Outro tipo de semaˆntica que tem sido muito estudada e´ a semaˆntica catego´rica.
As ide´ias ba´sicas desse to´pico (muito em moda atualmente) sa˜o elegantes e de
fa´cil entendimento para um aluno da graduac¸a˜o com alguma maturidade na
a´rea de A´lgebra.
19 Segundo trabalho pra´tico
O segundo trabalho pra´tico consiste em implementar o algoritmo RSA. Deve
ser apresentado o seguinte:
1. A chave pu´blica (n) criada no TP1, juntamente com o nu´mero e tal que
mdc(e, φ(n)) = 1.
2. Algoritmopara encontrar d, o inverso de e mo´dulo φ(n).
3. Algoritmos de codificac¸a˜o (incluindo o de partic¸a˜o da mensagem em blo-
cos) e decodificac¸a˜o.
48
4. Teste em um texto de, no mı´nimo, 20 linhas. O texto, os blocos e o texto
cifrado devera˜o estar contidos no trabalho.
Como sempre, e´ necessa´rio um pequeno texto introduto´rio de no ma´ximo duas
pa´ginas. Dessa vez na˜o vou cobrar os executa´veis...
49