UNIVERSIDADE ESTADUAL DA PARAIBA

CENTRO DE CIENCIAS E TECNOLOGIA

DEPARTAMENTO DE MATEMATICA

CURSO DE LICENCIATURA EM MATEMATICA

Os Numeros Primos e o Crivo de Eratostenes

JOSENILDO FERREIRA GALDINO

CAMPINA GRANDE - PB

Dezembro de 2011

Josenildo Ferreira Galdino

Os Numeros Primos e o Crivo de Eratostenes

Trabalho Academico Orientado apresentado

ao curso de Licenciatura em Matematica

do Departamento de Matematica do Cen-

tro de Ciencias e Tecnologia da Universi-

dade Estadual da Paraıba em cumprimento

as exigencias legais para obtencao do tıtulo

de licenciado em Matematica.

Orientador: Dr. Aldo Trajano Louredo

CAMPINA GRANDE-PB

Dezembro de 2011

FICHA CATALOGRÁFICA ELABORADA PELA BIBLIOTECA CENTRAL – UEPB

G131n Galdino, Josenildo Ferreira.

Os números primos e o crivo de Eratóstenes [manuscrito] /

Josenildo Ferreira Galdino. – 2011.

49 f. : il. color.

Digitado.

Trabalho de Conclusão de Curso (Graduação em

Matemática) – Universidade Estadual da Paraíba, Centro de

Ciências Tecnológicas, 2011.

“Orientação: Prof. Dr. Aldo Trajano Lourêdo, Departamento

de Matemática e Estatística”.

1. Matemática. 2. Números Primos. 3. Eratóstenes. 4.

Criptografia. I. Título.

21. ed. CDD 510.7

Dedicatoria

Dedico este trabalho a toda minha

famılia, e em especial ao meu pai, o

Sr. Jose Galdino Fernandes, e a minha

mae, a Sra Aurenir de Feitas Fernandes.

i

Agradecimentos

Desejo expressar os meus sinceros agradecimentos.

Primeiramente, agradeco a DEUS por proporcionar a conclusao de mais uma

etapa da minha vida que se consuma neste trabalho.

Aos meus pais: Jose Galdino Fernades e Aurenir Freitas Fernandes e aos meus

queridos irmaos: Juraci, Jurandir e Joelma, agradeco todo o amor, carinho e mo-

tivacao.

Ao Dr Aldo Trajano Louredo, sou grato pela orientacao e confianca em mim

depositada. Agradeco pelas discussoes e reflexoes que possibilitaram o enriquecimento

e realizacao deste trabalho.

Ao Dr Vandenberg Lopes Viera e Ms Fernando Luiz Tavares da Silva pelas va-

liosas criticas e sugestoes.

Aos funcionarios da coordenacao e departamento de matematica.

ii

Epıgrafe

”A mente que se abre a

uma nova ideia jamais vol-

tara ao seu tamanho origi-

nal”

(Albert Einstein)

iii

Resumo

Este trabalho aborda alguns resultados e problemas relacionados aos numeros pri-

mos, destacando o metodo classico do Crivo de Eratostenes que tem a finalidade de

determinar se um dado numero e primo. Alguns fundamentos da criptografia sao apre-

sentados. Alem disso, apresentam-se alguns conceitos de algebra abstrata, tais como:

congruencia, classes residuais, conjunto quociente, funcao de Euler e, principalmente,

a correlacao e relevancia dos numeros primos na criptografia RSA.

Palavras chave: Numeros Primos, Eratostenes e Criptografia.

iv

Abstract

This paper discusses some results and problems related to prime numbers, highlighting

the classic method of Riddle Eratostenes which has the purpose of determining whether

a given number is cousin. Some fundamentals of cryptography are presented. beyond

addition, it presents some concepts of abstract algebra, such as: congruence classes

residual quotient set, function of Euler and, especially, the correlation and significance

of prime numbers in RSA encryption.

Keywords: Primes, Eratostenes and encryption

v

Lista de Figuras

1.1 Marin Mersenne (1588-1648) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1 Eratostenes (276 a.C a 196 a.C) . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Leonhard Euler (1707-1785) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

vi

Lista de Tabelas

1.1 Tabela de Numeros de Mersenne de 1 a 24. . . . . . . . . . . . . . . . . . . . . . 3

1.2 Tabela de Numeros de Mersenne de 25 a 47. . . . . . . . . . . . . . . . . . . . . 4

2.1 Numeros de 1 a 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Multiplos de 2 eliminados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Multiplos de 3 eliminados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Crivo de Eratostenes para N = 100. . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5 Quantidade de primos de 1 a N . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

vii

Sumario

1 Numeros Primos 1

1.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Definicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Resultados sobre primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Conjecturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.1 Conjectura de Goldback . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.2 Conjectura de Polignac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Biografia e Crivo de Eratostenes 10

2.1 Crivo de Eratostenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Implementacao do Crivo de Eratostenes . . . . . . . . . . . . . . . . . . . . . . . 14

3 Conjectura de Goldback 15

3.1 Conjectura de Goldback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Criptografia 18

4.1 Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5 Cifra de Substituicao 20

5.1 Cifra de Cesar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.2 Cifra Monoalfabetica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

viii

ix

5.3 Cifra Polialfabetica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

6 Aritmetica Modular 23

6.1 Congruencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2 Classes Residuais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.3 Conjunto Quociente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.4 Funcao de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

7 Cifras de Hill 26

7.1 Decifracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

8 Cripto-Sistemas 30

8.1 Cripto-sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

9 Criptografia RSA 34

9.1 Chaves Publica e Privada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10 Conclusao 36

Referencias Bibliograficas 37

Capıtulo 1

Numeros Primos

Neste capıtulo apresentaremos alguns conceitos e definicoes sobre numeros primos. Alem

disso, destacaremos alguns de seus teoremas e resultados elementares.

1.1 Introducao

A Teoria dos Numeros e considerada um dos ramos mais antigos da matematica e estuda as

propriedades e relacoes entre os numeros. E uma area que vem ganhando destaque na literatura

especializada e, principalmente, pela grande utilidade na engenharia e na matematica aplicada.

Por exemplo, na engenharia, os sistemas criptograficos utilizam primos gigantes.

1.2 Definicoes

Definicao 1. Um inteiro p diz-se primo se tem exatamente dois divisores positivos, 1 e | p |.

Definicao 2. Um inteiro a diz-se composto se nao e primo e for diferente de 0,1 e -1.

Definicao 3. (Primos Gemeos)

Seja p um primo maior que 2. Os pares de primos da forma (p, p+2) sao chamados de primos

gemeos. Alguns exemplos de primos gemeos sao

(3, 5), (5, 7), (11, 13), (17, 19)

Definicao 4. (Numero Perfeito) Um numero e dito perfeito, se for igual a soma de seus

1

divisores, excluindo o proprio numero. [5] Alguns exemplos de numeros perfeitos sao

6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14

Definicao 5. (Numero de Mersenne) Um numero e dito numero de Mersenne se ele for da

forma Mn = 2n − 1 com n ∈ N. O numero de Mersenne e uma homenagem ao matematico

frances Marin Mersenne1 .

Figura 1.1: Marin Mersenne (1588-1648)

Definicao 6. (Primo de Mersenne) Um numero Mp se diz primo de Mersenne se Mp for primo,

na qual

Mp = 2p − 1 (1.1)

para um primo positivo p.

A busca de numeros de Mersenne incentivou a criacao de alguns grupos de pesquisa. E

o caso do GIMPS2. Este grupo encontrou os 13 maiores primos de Mersenne. Alem disso, no

site http://mersenne.org sao disponiblizados alguns programas computacionais que podem ser

utilizados por amadores ou especialistas na area. Uma lista completa de todos os numeros de

Mersenne encontrados e apresentada nas tabelas (1.1) e (1.2).

1Marin Mersenne - Teologo, filosofo e matematico frances (1588-1648). Estudou no colegio dos padres jesuıtas de La Fleche em

Paris, onde conheceu Descartes, com quem manteve lacos de amizade ate a morte. Em 1611 ingressou na Ordem dos Franciscanos.

Lecionou filosofia em Nevers (1614-1620) e Paris. A partir de 1630, aproximadamente, apos publicar algumas obras filosoficas e

teologicas, dedicou-se especialmente ao estudo da Matematica e da Fısica. Exerceu grande influencia nos movimentos filosoficos

e cientıficos de seu tempo, principalmente por ser o animador de um grupo de intelectuais, como Galileu, Torricelli, Gassendi,

Descartes, Roberval e Pascal. Foi o primeiro a medir experimentalmente a velocidade do som e a determinar a frequencia das

notas musicais. Traduziu para o latim diversos tratados cientıficos gregos. Escreveu, entre outras obras: Questiones celeberrimae

in Genesim (1623), L’impiete des deistes, athees et libertins (1624), La verite des sciences contre les Sceptiques et les Pyrrhoniens

(1625), L’harmonic universelle, contenant la theorie et la pratique de la musique.[6]2GIMPS - Great Internet Mersenne Prime Search ( Grande Pesquisa pela Internet sobre os numeros de Mersenne.)

2

No n (expoente) No de Digitos de Mn Ano Pesquisador

1 2 1

2 3 1

3 5 2

4 7 3

5 13 4

6 17 6 1588 Cataldi

7 19 6 1588 Cataldi

8 31 10 1772 Euler

9 61 19 1883 Pervushin

10 89 27 1911 Powers

11 107 33 1914 Powers

12 127 39 1876 Lucas

13 521 157 1952 Robinson

14 607 183 1952 Robinson

15 1279 386 1952 Robinson

16 2203 664 1952 Robinson

17 2281 687 1952 Robinson

18 3217 969 1957 Riesel

19 4253 1281 1961 Hurtwitz

20 4423 1332 1961 Hurwitz

21 9689 2917 1963 Gillies

22 9941 2993 1963 Gillies

23 11213 3376 1963 Gillies

24 19937 6002 1971 Tuckerman

Tabela 1.1: Tabela de Numeros de Mersenne de 1 a 24.

3

No n (expoente) No de Digitos de Mn Ano Pesquisador

25 21701 6533 1978 Noll & Nickel

26 23209 6987 1979 Noll

27 44497 13395 1979 Nelson & Slowinski

28 86243 25962 1982 Slowinski

29 110503 33265 1988 Colquitt & Wilsh

30 132049 39751 1983 Slowinski

31 216091 65050 1985 Slowinski

32 756839 227832 1992 Slowinski & Gage et al.

33 859433 258716 1994 Slowinski & Gage

34 1257787 378632 1996 Slowinski & Gage

35 1398269 420921 1996 Armengaud, Woltman, et al. (GIMPS)

36 2976221 895932 1997 Spence, Woltman, et al. (GIMPS)

37 3021377 909526 1998 Clarkson, Woltman, Kurowski et al. (GIMPS)

38 6972593 2098960 1999 Hajratwala, Woltman, Kurowski et al. (GIMPS)

39 13466917 4053946 2001 Cameron, Woltman, Kurowski et al. (GIMPS)

40 20996011 6320430 2003 Shafer, Woltman, Kurowski et al. (GIMPS)

41 24036583 7235733 2004 Findley, Woltman, Kurowski et al. (GIMPS)

42 25964951 7816230 2005 Novak, Woltman, Kurowski et al. (GIMPS)

43 30402457 9152052 2005 Cooper, Boone, Woltman, Kurowski et al. (GIMPS)

44 32582657 9808358 2006 Cooper, Boone, Woltman, Kurowski et al. (GIMPS)

45 37156667 11185272 2008 Elvenich, Woltman, Kurowski et al. (GIMPS)

46 42643801 12837064 2009 Strindmo, Woltman, Kurowski et al. (GIMPS)

47 43112609 12978189 2008 Smith, Woltman, Kurowski et al. (GIMPS)

Tabela 1.2: Tabela de Numeros de Mersenne de 25 a 47.

4

Definicao 7. (Numeros de Fermat) Todo numero escrito na forma Fn = 22n

+ 1 e chamado

de Numero de Fermat.

Em 1640, Fermat3 percebeu que os quatro primeiros numeros de Fermat eram primos,

isto e, Fn para n = 1, 2, 3, 4. Sendo assim, ele conjecturou que todo os numeros de Fermat eram

primos. Demorou quase 100 anos para invalidar a conjectura de Fermat, pois em 1739, Euler

demonstrou que o quinto numero de Fermat, F5, e divisıvel por 641. A seguir mostraremos a

prova de que F5 e divisivel por 641 usando o conceito e algumas propriedades de congruencias.

F5 = 225

+ 1 = 232 + 1

216 = 65536

Ao dividir o numero 65536 por 641, obtemos um resto igual a 154. Usando, congruencias

podemos escrever este fato como

216 ≡ 154(mod 641)

Da Teoria dos Numeros temos o seguinte resultado.

Proposicao 1. Sejam a, b inteiros arbitrarios e m, n inteiros positivos. Se a ≡ b(modm)

entao an ≡ bn(modm), para todo inteiro positivo n.

3Pierre de Fermat - Matematico Frances (1601-1665). Foi um dos grandes nomes da Matematica, tendo influenciado muito na

criacao do ramo chamado Calculo, com seu estudo sobre maximos, mınimos e tangentes de curvas. Essas tangentes sao chamadas

atualmente de taxas de variacao de uma quantidade ou simplemente de derivada. Tal a importancia de seu trabalho que, baseado

nele, Newton desenvolveu o calculo diferencial, base matematica para sua lei da gravidade e as leis da Mecanica. Outro ramo que

ajudou a desenvolver , juntamente com Pascal, foi a Teoria das Probabilidades.

A maior contribuicao de Fermat foi na Teoria dos Numeros, forma mais pura e antiga da Matematica. Porem, tinha uma maneira

nada academica de mostrar seus conhecimentos e progressos. Na maioria das vezes, em suas anotacoes e cartas, dava indıcios de

como provar determinadas propriedades e teoremas, mas nao os fazia por completo. As vezes, apos a descoberta de uma propriedade,

escrevia a amigos matematicos desafiando-os a prova-la. Seu mais celebre problema, conhecido como o Ultimo Teorema de Fermat,

foi escrito como uma anotacao incompleta nas margens do livro Aritmetica, de Diofante. Dizia ele:

E impossivel para um cubo ser escrito como a soma de dois cubos ou um numero elevado a quarta potencia

ser escrito como a soma de dois numeros elevados a quarta potencia, ou, em geral, para qualquer numero que seja

elevado a uma potencia maior que dois ser escrito como a soma de duas potencias semelhantes. Ou seja:

xn + yn = zn e impossıvel para n > 2

Logo apos esse desafio, Fermat escreveu. Tenho uma demonstracao realmente maravilhosa para essa proposicao, mas esta mmargem

e muito estreita para conte-la.

A fama do Ultimo Teorema de Fermat veio da sua grande dificuldade de ser demonstrado, bem como do fato de Fermat ter afirmado

poder demonstra-lo. Nao se sabe se com os conhecimentos da epoca ele o faria, mas esse teorema levou 355 anos para ser finalmente

demonstrado pelo matematico Andrew Wiles.

5

Daı,

216 ≡ 154(mod 641) ⇒ (216)2 ≡ 1542(mod 641)

Note que 1542 = 23716, e dividindo por 641 obtemos umn resto igual a 640. Sendo assim,

temos a seguinte congruencia.

1542 ≡ 640(mod 641).

Outro resultado da Teoria dos Numeros sobre congruencias e dado a seguir.

Proposicao 2. Sejam a, b e c inteiros arbitrarios e m um inteiro positivo. Se a ≡ b(modm)

e b ≡ c(modm) entao a ≡ c(modm)

Como 232 ≡ 1542(mod 641) e 1542 ≡ 640(mod 641). Entao,

232 ≡ 640(mod 641)

Por fim, utilizaremos o seguinte resultado

Proposicao 3. Sejam a, b e c inteiros arbitrarios e m um inteiro positivo. Se a ≡ b(modm)

entao a+ c ≡ b+ c(modm)

Portanto,

232 ≡ 640(mod 641) ⇒ 232 + 1 ≡ 641(mod 641)

Logo, concluımos que 641 divide 232 + 1.

1.3 Resultados sobre primos

Proposicao 4. Seja p um numero primo e a, b ∈ Z

1. Se p † a, entao mdc(p,a) = 1.

2. Se p | ab, entao p | a ou p | b

Demonstracao:

1. Como p e primo, entao seus divisores sao 1 e p. Se p † a, consequentemente, o unico

divisor comum positivo de a e p e 1, o que implica que mdc(p, a) = 1.

6

2. Suponhamos que p | ab. Agora, pelo Teorema de Euclides se mdc(p, a) = 1, entao p | b. Da

mesma forma, se mdc(p, b) = 1, entao p | a.

Teorema 1.1. (Principio de Inducao Completa - 1a Forma) Seja a um inteiro dado.

Suponhamos que para cada inteiro n ≥ a esta dada uma afirmacao A(n) de forma que

• A(a) e verdadeira.

• Se para um inteiro k ≥ a A(k) e verdadeira, entao A(k+1) e verdadeira.

Entao A(n) e verdadeira para todo inteiro n ≥ a.

Iremos utilizar o princıpio de inducao completa - 2a forma

Teorema 1.2. (Principio de Inducao Completa - 2a Forma) Suponhamos que para

cada inteiro n ≥ a esta dada uma afirmacao A(n) de forma que

• A(a) e verdadeira.

• Se A(m) e verdadeira para todo inteiro m tal que a ≤ m ≤ k, entao A(k+1).

Entao A(n) e verdadeira para todo inteiro n ≥ a.

Lema 1.1. Todo inteiro a > 1 pode ser escrito como produto de numeros primos.

Demonstracao:

Para a = 2 o resultado e valido, visto que 2 e um numero primo. Suponhamos agora que

o resultado seja verdadeiro para todo inteiro b, 2 ≤ b ≤ a. Devemos mostrar que o resultado

tambem vale para a.

Note que se a e primo, o lema esta demonstrado. Caso contrario, a admite um divisor

positivo b tal que 1 < b < a. Isto e, a = bc, e temos tambem 1 < c < a. Pela hipotese de

inducao, b e c podem ser escrito como produto de primos, na forma

b = p1 . . . pr c = q1 . . . qs

Como a = bc, temos

a = p1 . . . prq1 . . . qs.

Portanto, o resultado tambem vale para a.

7

Teorema 1.3. O conjunto dos numeros primos e infinito.

Demonstracao:

Suponhamos que o conjunto dos primos e finito e os numeros p1, p2, . . . , pn sao primos.

Agora, considere o numero P dado por

P = p1p2 . . . pn + 1.

Pelo lema anterior, P admite um divisor positivo primo pi. Sendo assim, pi divide o

produto p1p2 . . . pn. Entao, pi divide tambem 1 = P − p1p2 . . . pn, uma contradicao.

�

Proposicao 5. Se an − 1 e primo com n ∈ N, entao a = 2 e n e primo.

Demonstracao:

Seja um primo qualquer p, ele e fatorado da forma 1 ·p, isto e, p = 1 ·p. Se an−1 e primo

entao seus fatores sao 1 e o proprio numero.

an − 1 = (a− 1)(1 + a+ a2 + · · ·+ an−1).

Note que 1 + a+ a2 + · · ·+ an−1 > 1. Sendo assim, a− 1 = 1, isto e, a = 2.

Mostremos agora que n e primo. Sejam r, s inteiros positivos.

2r − 1 = (2− 1)(2r−1 + 2r−2 + · · ·+ 21 + 1)

Agora, substitua 2 por 2s.

(2s)r − 1 = (2s − 1)[(2s)r−1 + (2s)r−2 + · · ·+ (2s)1 + 1]

2rs − 1 = (2s − 1)[(2s)r−1 + (2s)r−2 + · · ·+ (2s)1 + 1]

2rs − 1 = (2s − 1)[2s(r−1) + 2s(r−2) + · · ·+ 2s·1 + 1]

8

Faca n = rs. Suponha que n e composto, isto e, tem dois fatores diferentes de 1.

Note que 2s(r−1) + 2s(r−2) + · · ·+ 2s·1 + 1 > 1. Como 2n − 1 e primo entao 2s − 1 = 1, isto e,

s = 1. Como deveriamos encontrar dois fatores diferentes de 1 entao a suposicao de que n e

composto e falsa. Logo, n e primo.

�

1.4 Conjecturas

1.4.1 Conjectura de Goldback

Conjectura 1. (Conjectura de Goldback) Todo inteiro positivo par maior que dois pode ser

escrito como soma de dois primos.

A seguir listamos alguns exemplos que satisfazem a conjectura de Goldback.

4 = 2 + 2 12 = 7 + 5

6 = 3 + 3 14 = 11 + 3

8 = 5 + 3 16 = 13 + 3

10 = 7 + 3 18 = 13 + 5

1.4.2 Conjectura de Polignac

Conjectura 2. (Conjectura de Polignac) Para todo par na forma 2n existem infinitas duplas

de primos consecutivos, isto e, primos que diferem de d =| 2n |

Quando n = 1 e d = 2 temos um caso particular da conjectura de Polignac que e conhecida

na literatura como conjectura dos primos gemeos.

9

Capıtulo 2

Biografia e Crivo de Eratostenes

Figura 2.1: Eratostenes (276 a.C a 196 a.C)

Filosofo, geografo e matematico (276a.C.196a.C.) foi criado em Cirene, cidade grega lo-

calizada ao norte da Africa. Eratostenes estudou em Alexandria, no Egito, e posteriormente,

em Atenas, retornando a Alexandria em 255 a.C. Ele escreveu sobre matematica, astronomia,

geografia e historia. Alem disso, Eratostenes ensinou em Alexandria, e por seu vasto conheci-

mento nas diversas areas do conhecimento tornou-se diretor da famosa biblioteca de Alexandria

em 240 a.C.

Naquela epoca, Ptolomeu III governava Alexandria e partes do Egito e ordenou que todos

os navios e caravanas fossem revistados em busca de livros, mapas ou documentos interessantes

para serem copiados. A biblioteca de Alexandria se tornou fonte dos vastos conhecimentos do

mundo antigo.

Com as riquezas do mundo intelectual prontamente disponıveis, Eratostenes compilou um

10

mapa do mundo conhecido, que se estendia das ilhas Britanicas ao Sri Lanka e incluıa todos

os paıses que faziam fronteira com o mar Mediterraneo. O mapa foi util por 200 anos. Ele

tambem percebeu que o calendario solar egıpcio ficava atrasado em um dia a cada quatro anos

com relacao as estacoes e sugeriu que se acrescentasse um dia extra de quatro em quatro anos.

Eratostenes e mais conhecido por ter calculado o tamanho da Terra, conclusao a que

chegou usando um metodo engenhoso. Ele sabia que o Sol fica mais alto ao meio-dia de 22 de

junho, o solstıcio de verao. Nessa hora especial, uma vara vertical projeta a menor sombra. Se

o sol estiver diretamente acima, a vara nao projeta sombra nenhuma. Isto acontece em Syene,

cidade ao sul de Alexandria, onde se encontra hoje a represa de Aswan. Como Eratostenes

descobriu que o Sol estava diretamente acima de Syene naquela hora unica? Ele sabia, atraves

das informacoes contidas na biblioteca, que ao meio-dia de 22 de junho, a luz do sol brilhava

diretamente ate o fundo de um poco profundo em Syene e era refletida de volta para cima,

em linha reta, mostrando, desta forma, que o sol estava diretamente acima. Usando geometria

simples, Eratostenes mostrou que existe um angulo de 7, 2 graus entre Alexandria e Syene, o que

corresponde a 1/50 de um cırculo. Viajava-se de Syene a Alexandria com frequencia e sabia-se

que a distancia media 5 mil estadios. Entao, Eratostenes calculou que a Terra tinha 50 x 5 mil

estadios, ou cerca de 250 mil estadios. Esta medida e incrivelmente proxima a circunferencia

da Terra aceita modernamente, cerca de 39.490 quilometros.

Eratostenes mostrou que a Terra e um lugar muito maior do que os gregos imaginavam.

Eles ficaram confusos, porque isso fazia o mundo conhecido parecer comparativamente muito

pequeno, e rejeitaram o numero de Eratostenes a favor de um tamanho menor e impreciso.

No campo das ciencias matematicas, destaca-se o metodo conhecido como Crivo de

Eratostenes. Este Crivo de Eratostenes e considerado um algoritmo simples e pratico para

encontrar numeros primos.

Infelizmente, apesar de seu sucesso como estudioso e escritor, o fim da vida de Eratostenes

foi tragica. Ele ficou cego e, aos 80 anos de idade, induziu sua propria morte parando de comer.

11

2.1 Crivo de Eratostenes

Eratostenes elaborou um metodo para determinar todos os primos menores que um dado

numero N > 0. Este metodo e conhecido como o Crivo de Eratotenes.

Inicialmente escrevemos todos os inteiros positivos menores ou iguais a N. Por exemplo,

se escolhermos N = 100 terıamos a seguinte tabela dada a seguir.

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70

71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90

91 92 93 94 95 96 97 98 99 100

Tabela 2.1: Numeros de 1 a 100.

Agora, eliminamos todos os multiplos de 2, excetuando-se o proprio 2.

1 2 3 //4 5 //6 7 //8 9 ///10

11 //12 13 //14 15 //16 17 //18 19 ///20

21 //22 23 //24 25 //26 27 //28 29 ///30

31 //32 33 //34 35 //36 37 //38 39 ///40

41 //42 43 //44 45 //46 47 //48 49 ///50

51 //52 53 //54 55 //56 57 //58 59 ///60

61 //62 63 //64 65 //66 67 //68 69 ///70

71 //72 73 //74 75 //76 77 //78 79 ///80

81 //82 83 //84 85 //86 87 //88 89 ///90

91 //92 93 //94 95 //96 97 //98 99 ////100

Tabela 2.2: Multiplos de 2 eliminados.

12

Agora, eliminamos todos os multiplos de 3, excetuando-se o proprio 3.

1 2 3 //4 5 //6 7 //8 //9 ///10

11 //12 13 //14 //15 //16 17 //18 19 ///20

//21 //22 23 //24 25 //26 //27 //28 29 ///30

31 //32 //33 //34 35 //36 37 //38 //39 ///40

41 //42 43 //44 //45 //46 47 //48 49 ///50

//51 //52 53 //54 55 //56 //57 //58 59 ///60

61 //62 //63 //64 65 //66 67 //68 //69 ///70

71 //72 73 //74 //75 //76 77 //78 79 ///80

//81 //82 83 //84 85 //86 //87 //88 89 ///90

91 //92 //93 //94 95 //96 97 //98 //99 ////100

Tabela 2.3: Multiplos de 3 eliminados.

Continuando com este procedimento

1 2 3 //4 5 //6 7 //8 //9 ///10

11 //12 13 //14 //15 //16 17 //18 19 ///20

///21 //22 23 //24 //25 //26 ///27 //28 29 ///30

31 //32 ///33 //34 //35 //36 37 //38 ///39 ///40

41 //42 43 //44 //45 //46 47 //48 ///49 ///50

///51 //52 53 //54 //55 //56 ///57 //58 59 ///60

61 //62 ///63 //64 //65 //66 67 //68 ///69 ///70

71 //72 73 //74 //75 //76 ///77 //78 79 ///80

///81 //82 83 //84 //85 //86 ///87 //88 89 ///90

91 //92 ///93 //94 //95 //96 97 //98 ///99 ////100

Tabela 2.4: Crivo de Eratostenes para N = 100.

13

2.2 Implementacao do Crivo de Eratostenes

Para utilizarmos o Crivo de Eratostenes foi criado uma funcao chamada crivo em lingua-

gem Matlab que referido metodo. A funcao crivo determina se o numero N e primo e tambem

fornece o numero de primos menores que N . Na tabela (2.5) apresentamos alguns resultados

de simulacao para diferentes valores de N .

N Numero de primos menores que N

10 4

100 25

1000 168

10000 1229

100000 9592

1000000 78498

Tabela 2.5: Quantidade de primos de 1 a N .

14

Capıtulo 3

Conjectura de Goldback

Neste capıtulo apresentaremos a famosa conjectura de Goldback que e um dos problemas

em aberto1 sobre os numeros primos. Geralmente, os problemas que envolvem numeros primos

sao de areas bem especıficas da matematica. Uma area bastante interessante e que aborda

varios problemas e resultados sobre os numeros primos e a Teoria dos Numeros.2 Nesta area

contempla diversos problemas em aberto de facil entendimento e qualquer pessoa tendo algumas

nocoes sobre numeros podera entender o enunciado do problema.

Um dos problemas mais conhecidos e a Conjectura de Goldback3 que abordaremos na

proxima secao.

1Problema em aberto sao problemas matematicos que nao foram resolvidos ainda.2Segundo (Shokranian, Soares e Godinho, 1998) Teoria dos Numeros e a ciencia na qual se estudam propriedades e relacoes

entre os numeros.3Matematico prussiano-russo nascido em Konigsberg, Prussia, hoje Kaliningrado, Russia, amigo de Euler a quem este confiou a

descoberta de que uma potencia imaginaria de um numero imaginario pode ser um numero real. Filho de um pastor, estudou leis e

matematica e tornou-se professor de matematica e historia e viajou praticamente por toda a Europa, encontrando-se pessoalmente

com muitos matematicos famosos, entre eles Leibniz, Nicolaus (I) Bernoulli, Nicolaus (II) Bernoulli, de Moivre, Daniel Bernoulli e

Hermann. da Academia Imperial de Sao. Petersburgo (1725). Depois, foi trabalhar para a recem-criada Academia de Ciencias de

Sao Petersburgo (1728) e tornou-se tutor daquele que mais tarde viria a ser o Czar Pedro II. Especialista em teoria dos numeros

criou conjecturas como a sobre numeros primos (1742), em que todo inteiro maior que 2 pode ser representado pela soma de dois

primos, enviada numa correspondencia para Euler. Tambem estudou somas infinitas, teoria das curvas e teoria das equacoes e

morreu em Moscou, Russia. Realizou, assim, trabalho importante na matematica e hoje, e a conjectura de Goldbach que mais

contribui para a sua fama. [7]

15

3.1 Conjectura de Goldback

Figura 3.1: Leonhard Euler (1707-1785)

Em 1742, o matematico alemao Christian Goldback (1690-1764) propos o seguinte pro-

blema em uma correspondencia enviada a Euler.4

Provar que todo inteiro positivo par pode ser escrito como soma de dois primos e todo

inteiro maior que dois pode ser escrito como soma de tres numeros primos.

4Leonhard Euler (1707-1785), matematico suico, dominou praticamente todas as areas da Matematica. Seu pai, o pastor

protestante Paul Euler, enviou-o, aos 14 anos, a Universidade de Basileia para estudar Teologia e preparar-se para ser pastor. La,

o professor Johann Bernoulli cedo descobriu o potencial de Euler para a Matematica.

Em 1723, Euler formou-se em Filosofia, tendo comparado as ideias filosoficas de Descartes e Newton. No outono do mesmo ano,

seguindo os desejos de seu pai, iniciou o curso de Teologia. No entanto, nao encontrou entusiasmo suficiente para estudar, embora

fosse um cristao devotado. Com o auxılio de Johann Bernoulli, persuadiu seu pai a deixa-lo estudar Matematica. Sob a tutela de

Bernoulli concluiu, em 1726 seus estudos.

Em 1727, assumiu um cargo na divisao de Matematica-Fısica na recem-inaugurada Academia de Sao Petersburgo, onde, em

contato com grandes cientistas, pode desenvolver-se em varias areas do conhecimento (Matematica aplicada, Teoria dos numeros,

Astronomia, Trigonometria, Geografia . . . ).

No ano de 1735, apos um surto de febre muito alta, perdeu a visao do olho direito. Nos dois anos seguintes, Euler publicou

varios artigos e o livro de Mecanica, no qual utilizou analise matematica para o estudo da dinamica newtoniana.

Em torno de 1740, Euler tinha grande reputacao em toda a Europa. Aceitando o convite para ingressar na Academia de Ciencias

de Berlim, mudou-se para essa cidade em julho daquele ano. Durante os vinte e cinco anos que passou em Berlim, publicou em

torno de 380 artigos e varios livros em diversas areas, uma quantidade invejavel para qualquer genio.

Em 1766, devido a interferencia do rei Frederico nos rumos da Academia, Euler decidiu voltar para Sao Petersburgo. Proximo de

seu retorno a Russia, ficou completamente cego. Devido a sua incrıvel memoria, continuou fazendo seus trabalhos. Para isso, teve

a ajuda de seus filhos, Johann Euler e Christoph Euler, que anotavam suas observacoes, alem de outros matematicos da Academia,

como Lexell, Krafft, Albrecht, que receberam os creditos por sua ajuda na obra de 775 paginas sobre o movimento da Lua. Seus

amigos diziam: a cegueira ampliou os horizontes de sua imaginacao. Seu trabalho matematico e cientıfico foi tao vasto que ele e

considerado o maior escritor matematico de todos os tempos.

16

A primeira sentenca do problema de Goldback, ou seja, todo numero par maior que 2 e

soma de dois primos e conhecida hoje como conjectura de Goldback. Alguns pesquisadores da

area de matematica tentaram resolver esse problema. Em 1966, o matematico chines Jeng-Run

Chen provou parcialmente a conjectura de Goldback. Chen mostrou que a partir de algum n,

todo numero par maior que dois ou e soma de dois primos, ou a soma de um primo com o

produto de dois primos. Vale ressaltar que o argumento de Chen nao nos diz qual e o n. So

que tal numero existe.

Ja a segunda sentenca do problema de Goldback foi demonstrada em parte. Em 1937, o

matematico sovietico I. M. Vinogradov demonstrou, usando somas trigonometricas adequadas,

que qualquer numero ımpar suficientemente grande e soma de tres numeros primos.

Apesar da simplicidade do enunciado do problema de Goldback este problema continua

ainda sem solucao, isto e, ate o momento ninguem conseguiu provar ou encontrar um contra-

exemplo para o problema.

17

Capıtulo 4

Criptografia

4.1 Historia

O primeiro registro do uso da criptografia foi em 1900 a.c., quando os egıpcios escreveram

os famosos hieroglifos, que eram codigos. Ja os romanos usavam os codigos para comunicar

planos de batalha. Alguns dos primeiros relatos sobre escritas secretas datam de Herodoto, “o

pai da historia”, de acordo com o filosofo e estadista romano Cıcero. Herodoto que escreveu

As Historias, narrou os conflitos entre a Grecia e a Persia ocorridos no quinto seculo antes

de Cristo. De acordo com Herodoto, foi a arte da escrita secreta que salvou a Grecia de ser

conquistada por Xerxes, Rei dos Reis, o despota lıder dos Persas.

Depois da Segunda Guerra surgiu o computador, a area floresceu, e surgiram codigos mais

rapidos, praticos e seguros, com o auxilio de algoritmos matematicos.

A palavra criptografia e derivada do grego kryptos e graphos, os quais significam “oculto”e

“escrita”. O objetivo da criptografia nao e ocultar a existencia de uma mensagem, e sim escon-

der o seu significado. A vantagem da Criptografia e que, se o inimigo interceptar a mensagem

codificada, ela sera ilegıvel e seu conteudo nao podera ser percebido. Sem conhecer o protocolo

de codificacao, o inimigo achara difıcil, se nao impossıvel, recriar a mensagem original a partir

do texto cifrado.

Atualmente, o termo criptografia refere-se a ciencia e a arte da transformacao de mensa-

gens tornando-as seguras e imunes a ataques. Na criptografia comumente sao utilizados alguns

nomes para facilitar o entedimento de sistemas criptograficos, sendo eles: Alice, Bob e Eve.

Alice e a personagem que necessita transmitir dados com seguranca. Bob e o personagem re-

18

ceptor dos dados. Eve e a personagem que, de algum modo, perturba a comunicacao entre Alice

e Bob, interceptando mensagens ou enviando mensagens dissimuladas proprias. O objetivo da

criptografia e garantir que a mensagem original enviada por Alice seja acessada apenas por

Bob.

A criptografia lida com as transformacoes de uma mensagem para a forma codificada

atraves de codificacao e recuperacao da mensagem original por meio de decodificacao. A men-

sagem original, isto e, antes de sofrer transformacao, e denominada texto limpo ou texto em

claro. Na etapa de codificacao da mensagem original, e utilizada um algoritmo de crifagem

que transforma o texto limpo em texto cifrado. Ja na etapa de decodificacao e utilizado um

algoritmo de decifragem que reverte o processo, ou seja, transforma o texto cifrado em texto

limpo.

A palavra criptografia e derivada da palavra grega kriptos, que significa “oculto”.

Conceito de Criptografia: E a arte ou ciencia de escrever mensagens em cifras ou em

codigos, de modo que somente a pessoa autorizada possa decifrar e ler mensagens.

Cada cifra pode ser considerada em termos de um metodo geral de codificacao conhecido

como algoritmo e usa uma chave, que especifica os detalhes exatos de uma codificacao em

particular. O algoritmo consiste em substituir o alfabeto original pelo cifrado, e a chave define

o alfabeto cifrado que sera usado em uma codificacao em particular. Assim se o inimigo inter-

ceptar uma mensagem em codigo, ele pode suspeitar qual seja o algoritmo, mas espera-se que

ele nao conheca a chave.

A palavra, criptografia, ainda evoca imagens de agentes secretos sorrateiramente transfe-

rindo informacoes sigilosas a nacoes rivais, entretanto, a principal missao da criptografia mo-

derna e proteger as informacoes referentes a transacoes bancarias e comerciais que transitam

entre computadores numa rede.

19

Capıtulo 5

Cifra de Substituicao

5.1 Cifra de Cesar

O primeiro registro da cifra de substituicao e atribuıdo a Julio Cesar e, assim, ficou

conhecido como cifra de Cesar. Na cifra de Cesar, cada letra da mensagem do texto que sera

cifrado e substituıdo pela k-esima letra sucessiva do alfabeto. Por exemplo, se k = 4, entao a

letra a fica sendo a letra d no texto cifrado; a letra b se transforma na letra f no texto cifrado,

e assim por diante. A seguir mostramos o alfabeto e o texto cifrado usando a cifra de Cesar

com k = 4.

Comum A B C D E F G H I J K L M N O P Q R S T

Cifra E F G H I J K L M N O P Q R S T U V W X

U V W X Y Z

Y Z A B C D

As letras A do texto comum sao substituıdas por E, as letras B do texto comum por F e

assim por diante. Com essa cifra a mensagem do texto comum:

A ESCADA DA SABEDORIA SE FAZ COM NUMEROS

fica da seguinte forma

E IWGEHE HE WEFIHSVME WI JEV GSQ RYQIVSW

20

Apesar do texto cifrado nao ter nenhum nexo e bastante facil quebrar o codigo supondo

que saibamos que o texto foi cifrado com a cifra de Cesar. Na verdade, no pior dos casos

terıamos que testar 25 valores para o deslocamento, isto e, k = 1, 2, . . . , 25.

5.2 Cifra Monoalfabetica

Ao longo do tempo, a ideia de Cesar de codificar o texto foi sendo adotada por outros e

alterada para que o codigo ficasse mais difıcil de ser quebrado. Um aperfeicoamento da cifra de

Cesar e a cifra monoalfabetica, que substitui uma letra do alfabeto por outra. Ao contrario

da cifra de Cesar que e feita uma substituicao seguindo um padrao regular (por exemplo,

substituicao por um deslocamento de k para todas as letras), na cifra monoalfabetica, qualquer

letra pode ser substituıda por qualquer outra, contanto que cada letra tenha uma unica letra

substituta e vice-versa.

Comum A B C D E F G H I J K L M N O P Q R S T

Cifra M N B V C X Z A S D F G H J K L P O I U

U V W X Y Z

Y T R E W Q

Com essa cifra a mensagem do texto comum:

A ESCADA DA SABEDORIA SE FAZ COM NUMEROS

fica da seguinte forma

M CIBMVM VM IMNCVKOSM IC XMQ BKH JYHCOKI

A cifra monoalfabetica requer 26! (aproximadamente 1026) possibilidades para codificar o

alfabeto, um numero estrondoso em comparacao a 25 possibilidades para o alfabeto da cifra de

Cesar. Uma abordagem pelo metodo de forca bruta que testa todas as possibilidades deman-

daria um esforco computacional grande e isto impediria que este codigo fosse quebrado. No

entanto, a cifra monoalfabetica tem um ponto fraco com relacao a codificacao de maneira unica

para cada letra do alfabeto. Observe no exemplo anterior que: se a letra A e cifrada como a

21

letra M, significa que toda letra A do texto original vai ser substituida pela letra M. Portanto,

pela analise estatıstica da linguagem do texto e sabendo que as letras A, E e O sao as mais

frequentes nos textos em portugues, e possivel quebrar esse codigo.

5.3 Cifra Polialfabetica

Na cifra polialfabetica, cada ocorrencia de um caractere pode ter um substituto diferente.

Em outras palavras, cada caractere do texto original pode ser cifrado por diferentes caracteres.

A ideia da cifra polialfabetica e utilizar varias cifras monoalfabeticas com uma cifra monoal-

fabetica especıfica para codificar uma letra em uma posicao especıfica do texto. Assim, uma

mesma letra, quando aparece em diferentes posicoes no texto, pode ser codificada de maneira

diferente. Por exemplo, considere um esquema criptografico polialfabetico composto por duas

cifras de Cesar (k = 5 e k = 19). Uma opcao e utilizar essas duas cifras de Cesar, C1 e C2,

seguindo o modelo de repeticao C1C2C2C1C2C1C2C2C1C1. A seguir temos um esquema de uma

cifra polialfabetica que utiliza duas cifras de Cesar.

Alfabeto : ABC DE F GH I J K LM N OP QRS T U V W X Y Z

C1(k = 5) : F GH I J K LM N OP QRS T U V W X Y Z ABC DE

C2(k = 19) : T U V W X Y Z AB C DE F GH I J K LM N OP QRS

Com essa cifra a mensagem do texto comum:

MATEMATICA

fica da seguinte forma

RTMJFFMBHT

22

Capıtulo 6

Aritmetica Modular

6.1 Congruencia

Definicao 8. Seja m > 1 um numero inteiro. Dados a, b ∈ Z, dizemos que a e congruente a b

modulo m se, e somente se, m|(a− b) e usamos a notacao:a ≡ b(modm).

Exemplo:

21 ≡ 1(mod 5) pois 21− 1 = 20 que e divisıvel por 5

Propriedades:

• Reflexiva: a ≡ a(mod m);

• Simetrica: Se a ≡ b(mod m) entao b ≡ a(mod m);

• Transitiva: Se a ≡ b(mod m) e b ≡ c(mod m), entao a ≡ c(mod m).

Alem destas, a congruencia modulo m goza das seguintes propriedades:

• Se a ≡ a(mod m) e c ≡ d(mod m), entao a + c ≡ b+ d(mod m);

• Se a ≡ b(mod m) e c ≡ d(mod m), entao a.c ≡ b.d(mod m);

• Se a ≡ b(mod m) entao an ≡ bn(mod m) para todo n ∈ N.

23

6.2 Classes Residuais

Definicao 9. Toda classe de equivalencia em Z determinada pela congruencia modulo m,

chama-se classe residual modulo m.

A classe residual modulo m de um inteiro a e o conjunto de todos os numeros inteiros x

tais que x ≡ a(mod m), ou seja, tais que x − a = k.m, k ∈ Z e representada por a que se le:

”a barra”. Portanto, simbolicamente:

a = {x ∈ Z; x ≡ a(mod m)}

a = {x ∈ Z; x = m.k + a}

6.3 Conjunto Quociente

O conjunto quociente de Z pela conguencia modulo m, isto e, o conjunto de todas as

classes residuais modulo m, indica-se por Zm. Portanto, simbolicamente:

Zm = {a | a ∈ Z}

Como a = q.m+r, onde 0 ≤ r < m, qualquer a ∈ Z e congruente modulo m a um dos elementos

0, 1, 2, ..., m− 1 e mostra-se que:

Zm = {0, 1, 2, ..., m− 1}

Em Zm definimos as seguintes operacoes:

• Adicao: a+ b = a+ b

• Multiplicacao: a.b = a.b

Um elemento a ∈ Zm e dito invertıvel se existir x ∈ Zm tal que:

a.x = x.a = 1

ou equivalente,

ax ≡ 1(mod m)

Proposicao 6. Um elemento a ∈ Zm e invertıvel, se e somente se, mdc(a,m) = 1.

24

6.4 Funcao de Euler

Seja φ : N −→ N a funcao de Euler, isto e, a funcao definida por

φ(n) = #{1 ≤ r ≤ n;mdc(r, n) = 1}

Exemplo: φ(6) = 2, pois mdc(1, 6) = 1, mdc(2, 6) = 2, mdc(3, 6) = 3, mdc(4, 6) = 2,

mdc(5, 6) = 1, mdc(6, 6) = 6.

Proposicao 7. Se p e q, sao primos, entao

φ(p.q) = (p− 1)(q − 1)

25

Capıtulo 7

Cifras de Hill

Uma desvantagem de cifras de substituicao e que elas preservam as frequencias de letras

individuais, tornando relativamente facil quebrar o codigo por metodos estatısticos. Uma ma-

neira de superar este problema e dividir o texto em grupos de letras e criptografar o texto

comum por grupo, em vez de uma letra de cada vez. Um sistema poligrafico e um sistema de

criptografia no qual o texto comum e dividido em conjuntos de n letras, cada um dos quais

e substituıdo por um conjunto de n letras cifradas. Estudaremos agora uma classe de siste-

mas poligraficos chamados Cifras de Hill que sao baseados em trasformacoes matriciais. (O

nome e em referencia a Lester S. Hill que introduziu estes sistemas em dois artigos: ”Cryp-

tography in na Algebraic Alphabet”, American Mathematical Monthly, vol. 36, Junho-Julho

de 1929 e ”Conserning Certain Linear Transmation Apparatus of Cryptography”, American

Mathematical Monthly, vol. 38, Marco de 1931, paginas 135-154).

Nos casos mais simples de cifras de Hill, tranformamos pares sucessivos de texto comum

em texto cifrado pelo seguinte procedimento:

Passo 1: Escolha uma matriz 2× 2

A =

a11 a12

a21 a22

em Zm

com entradas aiji, j = 1, 2 inteiras para efetuar a codificacao.

Passo 2: Agrupe letras sucessivas do texto comum em pares, adicionando uma letra

fictıcia para complemetar o ultimo par se o texto comum tem um numero ımpar de letras;

substitua cada letra do texto comum por seu valor numerico.

26

Passo 3: Converta cada par sucessivo p1 p2 de letras de texto comum em um vetor-coluna.

P =

p1

p2

e forme o produto AP . Chama-se P de vetor comum e AP o correspondente vetor cifrado.

Passo 4: Converta cada vetor cifrado em seu equivalente alfabetico.

Exemplo 7.1. Use o alfabeto da tabela abaixo e a matriz dada:

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y Z E , ?

20 21 22 23 24 25 26 27 28

A =

4 1

0 2

em Z29

Para obter a cifra de Hill da mensagem de texto comum

MATEMATICA

Solucao: Agrupamos o texto comum em pares de letras o qual obteremos:

MA TE MA TI CA

ou, equivalentemente, usando a tabela dada

12 0 19 4 12 0 19 8 2 0

Para codificar o par MA efetua-se o produto matricial

4 1

0 2

12

0

=

48

0

=

19

0

Aqui temos um problema, pois o numero 48 nao possui equivalente alfabetico de acordo com a

tabela dada, ja que esta se usando o conjunto Z29. Para resolver este problema faz-se o seguinte:

sempre que ocorrer um inteiro maior que 28, ele sera substituıdo pelo resto da divisao deste

27

inteiro por 29.

Com o resto da divisao e um dos inteiros 0, 1, 2, ..., 28, este procedimento sempre fornece um

inteiro com equivalente alfabetico.

Assim substitui-se 48 por 19, que e o resto da divisao deste numero por 29 e obtem-se o texto

cifrado TA, no lugar de MA.

As contas para os demais vetores cifrados sao:

4 1

0 2

19

4

=

80

8

=

22

8

4 1

0 2

19

8

=

84

16

=

26

16

4 1

0 2

2

0

=

8

0

Estes vetores correspondem aos pares de texto cifrado TA, WI, TA, EQ e IA, respectivamente.

Coletando os pares, obtemos a mensagem cifrada completa:

TA WI TA EQ IA

Que, normalmente, seria transmitida como uma unica cadeia sem espacos:

TAWITAEQIA

Como o texto comum foi agrupado em pares e criptografado por uma matrix 2 × 2, diz-

se que a cifra de Hill do exemplo e uma 2-cifra de Hill. Evidentemente tambem e possıvel

agrupar o texto comum em ternas e criptografar com uma matriz 3× 3 com entradas inteiras,

isto e chamado de uma 3-cifra de Hill. Em geral, para uma n-cifra de Hill agrupa-se o

texto comum em conjuntos de n letras e codifica-se com uma matriz codificadora n×n de

entradas inteiras.

7.1 Decifracao

Para decifrarmos a mensagem codificada acima faz-se o seguinte:

pela tabela dada o equivalente numerico e

28

19 0 22 8 19 0 26 16 8 0

Para obtermos os pares de texto comum, multiplica-se cada vetor cifrado pela inversa de A,

onde a inversa de A e dada por A−1 = (a11a22 − a21a12)−1

a22 −a12

−a21 a11

(mod m)

Tem-se

A−1 =

22 18

0 15

em Z29

Logo, para decodificar o par 19 0, faz-se a seguinte operacao:

22 18

0 15

19

0

=

418

0

=

12

0

E, assim por diante, ate que todos os vetores tenham sido decifrados.

22 18

0 15

22

8

=

628

120

=

19

4

22 18

0 15

26

16

=

860

240

=

19

8

em Z29

22 18

0 15

8

0

=

176

0

=

2

0

Pela tabela dada anteriormente temos que os equivalentes alfabeticos desses vetores sao:

MA TE MA TI CA

Que fornece a mensagem cifrada anteriormente.

Exercıcio 7.1. Usando a cifra de Hill do exemplo acima, como seria codificada a mensagem

”Deus e fiel”?

Use o alfabeto da tabela abaixo.

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y Z E ?

20 21 22 23 24 25 26 27 28

29

Capıtulo 8

Cripto-Sistemas

Amensagem a ser enviada e chamada de texto-original e a mensagem codificada e chamada

de texto-cifrado. O texto-original e o texto cifrado sao escritos em algum alfabeto P constituıdo

de um certo numero de sımbolos. Isto e,

#(P ) = n

O texto-original e o texto cifrado sao divididos em mensagens unitarias, que podem ser

um bloco de k sımbolos do alfabeto P . O processo de codificacao e uma funcao que associa cada

mensagem unitaria m do texto-original a uma mensagem unitaria c do texto-cifrado. Seja M o

conjunto de todas as possıveis mensagens unitarias c do texto-cifrado. Entao a correspondencia

biunıvoca

f : M −→ C tal que f(m) = c

e o processo de codificacao. A correspondencia biunıvoca

f−1 : C −→ M tal que f−1(c) = m

e o processo de decodificacao. Assim, temos o seguinte diagrama

Mf

−→ Cf−1

−→ M

8.1 Cripto-sistema

Um cripto-sistema e qualquer bijecao de M sobre C.

30

E util substituir os sımbolos de uma alfabeto P , por numeros inteiros 0, 1, 2, ..., para

tornar mais facil a construcao do cripto-sistema f . Uma correspondencia que pode ser feita

entre o alfabeto

P = {A,B,C, ..., X, Y, Z, E, , , ?}

e o conjunto dos numeros inteiros

Z29 = {0, 1, 2, ..., 25, 26, 27, 28}

e a seguinte

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y Z E , ?

20 21 22 23 24 25 26 27 28

De forma geral pode-se rotular mensagens unitarias, com blocos de k sımbolos, de um

alfabeto P de n sımbolos, por inteiros do conjunto

Znk = {0, 1, 2, ..., nk − 1}

do seguinte modo:

(xk−1, ..., x1, x0) ∈ Znk ⇔ xk−1nk−1 + ... + x1n+ x0n

0 ∈ Znk ,

onde cada xi corresponde a um sımbolo do alfabeto P . Por exemplo, a mensagem unitaria com

blocos de quatro sımbolos

”AMOR

corresponde ao inteiro

0.293 + 12.292 + 14.29 + 17.290 = 10515 ∈ Z294

Observacao 1. O cripto-sistema

f(x) = ax+ b

e chamado de transformacao afim. O par (a, b) e chamado de chave de codificacao ou chave

secreta. Quando n = 27, a = 1 e b ∈ Z27, o cripto-sistema

f(x) = ax+ b

31

e chamado de Cifra de Cesar, pois Julio Cesar a utilizava. Quando b = 0, o cripto-sistema

f(x) = ax

e uma transformacao linear

Exemplo 8.1. A correspondencia biunıvoca entre o alfabeto P e os numeros inteiros e dado

pela tabela

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y Z E , ?

20 21 22 23 24 25 26 27 28

Seja o sımbolo x ∈ Z29 correspondendo a uma mensagem unitaria com blocos de um

sımbolo do texto-original. Assim, com a = 5 e b = 2, temos que a funcao

f : Z29 −→ Z29 dada por f(x) = 5x+ 2

e um cripto-sistema. Portanto, para decodificar o texto-original

”CRIPTOGRAFIA”

primeiro calculamos

f(2) = 12, f(17) = 0, ..., f(8) = 13, f(0) = 0,

logo a mensagem cifrada e

”MANTKODAC,NC”

Para decodificar a mensagem cifrada, primeiro calculamos

f−1(x) = 6x− 12

e depois

f−1(12) = 2, f−1(0) = 17, ..., f−1(13) = 8, f−1(2) = 0,

Logo a mensagem decifrada e

”CRIPTOGRAFIA”

32

Exercıcio 8.1. Usando o cripto-sistema acima, como ficaria codificada a mensagem:

O melhor Sao Joao do mundo fica em Campina Grande.

a correspondencia biunıvoca entre o alfabeto P e os numeros inteiros e dado pela tabela

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y Z A .

20 21 22 23 24 25 26 27 28

Exercıcio 8.2. Usando o cripto-sistema acima, como ficaria codificada a mensagem

O melhor da Paraıba, e o Campinense Clube

a correspondencia biunıvoca entre o alfabeto P e os numeros inteiros e dado pela tabela

A B C D E F G H I J K L M N O P Q R S T

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

U V W X Y I , E

20 21 22 23 24 25 26 27 28

33

Capıtulo 9

Criptografia RSA

A criptografia de chave publica RSA surgiu em 1978 e tem esse nome devido as iniciais dos

inventores Rivest, Shamir e Adleman. E considerado o metodo mais utilizado na criptografia

com chave publica.

A criptografia RSA baseia-se no fato da simplicidade de calcular o produto de dois numeros

primos grandes. Em contrapartida, a seguranca do RSA reside na inviabilidade de fatorar um

numero gigantesco.

Na criptografia RSA, utiliza-se duas chaves: uma privada e uma publica. A chave privada

e formada por um par de numeros (N,d). Ja a chave publica e formada por outro par (N,e).

Note que o numero N e comum a ambas as chaves.

Na codificacao, Alice utiliza o seguinte algoritmo para cifrar a mensagem

C = P emodN

na qual, P e o texto original (texto limpo), que e representado por um numero; C e

um numero que representa o texto cifrado. Os numeros e e N sao os componentes da chave

publica. O texto limpo e gerado por meio de P = CemodN . Deve-se ressaltar que o termo

mod representa o resto da divisao de P por N, e esse resto e enviado como o texto cifrado.

Na decodificacao, Bob usa o seguinte algoritmo para decifrar a mensagem

P = CdmodN

Os numeros d e N sao os componentes da chave privada.

34

9.1 Chaves Publica e Privada

Uma questao primordial na criptografia RSA e a escolha adequada para os tres numeros

N, d e e que compoem as chaves publica e privada. Estes numeros sao fundamentais no pro-

cesso de cifragem e decifragem do texto. A seguir descreveremos o procedimento padrao para

geracao dos numeros das chaves.

1. Escolha dois numeros primos grandes. Denote-os por p e q.

2. Calcule N = p× q

3. Escolha e (menor que N) tal que e e (p− 1)(q− 1) sejam primos entre si, isto e, nao tem

nenhum divisor comum, exceto o numero 1.

4. Escolha d tal que (e× d)mod [(p− 1)(q − 1)] = 1.

Este procedimento foi desenvolvido pelos inventores da criptografia RSA e e baseado em

resultados obtidos da teoria dos numeros.

35

Capıtulo 10

Conclusao

Com a realizacao desse trabalho algumas definicoes, teoremas e conjecturas associados

aos numeros primos foram destacadas. Em especial, a conjectura de Goldback que afirma que

todo inteiro positivo par pode ser escrito como soma de dois primos.

O metodo classico do Crivo de Eratostenes foi implementado em linguagem Matlab o

que propiciou um bom aprendizado com alguns fundamentos em programacao, e sobretudo,

explorar os poderosos recursos disponibilizados pelo Matlab que e considerado uma ferramenta

essencial para estudantes das ciencias exatas. Desta forma, este trabalho pretende contribuir

para que outros alunos venham a se interessar a utilizar o Matlab.

No estudo feito sobre criptografia foi apresentado um pouco da historia da criptografia,

principais tipos de cifras e conceitos matematicos associados a criptografia.

36

Referencias Bibliograficas

[1] Coelho S. P; Milies C. P. Numeros: Uma Introducao a Matematica. Edusp - Editora da

Universidade de Sao Paulo, 3a Edicao, 2006 - Sao Paulo - SP - Brasil.

[2] Shokranian S, Soares M e Godinho H. Teoria dos Numeros. Editora Universidade de

Brasılia, 2a Edicao, 1999.

[3] Forouzan B. A, Comunicacao de Dados e Redes de Computadores. Editora Bookman, 3a

Edicao, 2006. Porto Alegre.

[4] Kurose J. F, Ross K. W. Redes de Computadores e Internet - Uma abordagem top-down.

Editora Pearson Addison Wesley. 3a Edicao, 2006. Sao Paulo - SP.

[5] Filho D. C. M, Um Convite a Matematica - Fundamentos-Logicos com Tecnicas de De-

monstracao, Notas Historicas e Curiosidades, Editora Universitaria da Universidade Fe-

deral de Campina Grande (EDUFCG), 2a Edicao, 2007.

[6] Enciclopedia Brasileira Globo. 19a Edicao, Editora Globo, Porto Alegre, 1981.

[7] http://www.dec.ufcg.edu.br/biografias/ChrstiaG.html (Consultado em novembro de

2011).

[8] http://primes.utm.edu/mersenne/index.html (Consultado em novembro de 2011).

[9] Coutinho, S.C., Numeros Inteiros e Criptografia RSA; IMPA, Rio de Janeiro, 2000.

[10] Andrade, A.S.,Numeros, Relacoes e Criptografia, UFPB, Joao Pessoa, 1997.

[11] Hefez, A., Curso de Algebra, Volume 1.(3a edicao) IMPA, Rio de Janeiro, 2000.

37