Criptografia números primos e algoritmos

Criptografia números primos e algoritmos

(Parte 4 de 4)

Por hipotese de inducao, todo natural menor que n possui fatoracao unica e daı r = s, pi = qi e ai = bi para todo i. Logo as fatoracoes de n acima sao identicas e, por inducao, o resultado vale para todo

Observe que foi possıvel demonstrar fatoracao unica nos inteiros, pois esse conjunto tem um algoritmo de divisao. Iremos nos deparar com outros conjuntos, que possuem algoritmos de divisao e, de maneira analoga, podemos mostrar que gozam da propriedade da fatoracao unica. Claro que alguns conjuntos possuem fatoracao unica, mas nao tem um algoritmo de divisao.

1. Encontre o expoente da maior potencia de 2 que divide 100! (100 fatorial).

[SEC. 1.8: ALGUMAS APLICACOES DA FATORACAO UNICA 29 2. Seja p um numero primo e n um inteiro positivo. Mostre que o

expoente da maior potencia de p que divide n! e∑ i≥1

1.8 Algumas aplicacoes da fatoracao unica

Nessa ultima secao, iremos fazer algumas aplicacoes bem simples da fatoracao unica. Primeiro, iremos mostrar que √ 2 nao e um numero racional. Argumentaremos por contradicao: suponha que √ 2 e um numero racional. Logo existem inteiros m e n tais que

Elevando-se essa expressao ao quadrado obtemos 2n2 = m2.

Se 2a e 2b sao as maiores potencias de 2 que dividem m e n, respectivamente, entao o expoente de 2 na fatoracao de 2n2 e 2b + 1 e na de m2 e 2a. Chegamos a uma contradicao usando o teorema da fatoracao unica, pois 2n2 = m2. Logo √ 2 nao e um racional.

O mais conhecido teorema da matematica, que e o de Pitagoras, garante que em um triangulo retangulo onde a e sua hipotenusa e b e c seus catetos. Sabemos que existem varios desses triangulos com todos os lados naturais, por exemplo:

(501.0)2 + (1.001)2 = (501.001)2

Fazemos a seguinte pergunta: quais sao todos esses triangulos? Em outras palavras, quais sao todas as solucoes nos naturais da equacao

Encontrar todas as solucoes inteiras de uma determinada equacao, no jargao matematico, e resolver uma equacao diofantina (em homenagem ao matematico grego Diofantus).

Observe que (λa,λb,λc) tambem e uma solucao dessa equacao quando (a,b,c) e solucao, pois

Logo necessitamos encontrar as solucoes (a,b,c) tais que MDC(a,b,c) = 1, pois as demais sao obtidas apartir destas multiplicando-as por um inteiro qualquer. Caso isso ocorra, temos de ter (a,b) = (a,c) = (b,c) = 1, caso contrario, MDC(a,b,c) 6= 1. (Por exemplo, se um primo p divide b e c, temos que p divide b2+c2 = a2 e daı p divide a.) Podemos fazer uma outra simplificacao no problema, procurar solucoes apenas nos inteiros positivos, pois (a,b,c) e solucao se e somente se (|a|,|b|,|c|) tambem e, e as unicas solucoes que tem uma das coordenadas nula sao (a,±a,0) e (a,0,±a). Seja (a,b,c) uma solucao em numeros inteiros positivos de tal que MDC(a,b,c) = 1. Observe que b ou c eımpar, caso contrario 2 dividiria MDC(a,b,c) pois a soma de numeros pares e par. Digamos que b seja ımpar. Como temos que MDC(a − c,a + c) = 1, ja que todo numero d que divide a−c e a+c tambem divide (a−c)+(a+c) = 2a e (a+c)−(a−c) = 2c e como (a,c) = 1 concluımos que d e igual a 1 ou 2, mas d nao pode ser 2 pois divide b, que e ımpar. Se pa e a maior potencia de um primo p que divide b, entao 2a e o expoente de p na fatoracao de b2 como produto de primos. Em decorrencia de MDC(a−c,a+c) = 1, temos que p2a ou divide a − c ou divide a + c. Consequentemente os expoentes dos primos na fatoracao unica de a − c e a + c sao todos pares e existem naturaisımpares r e s tais que a−c = r2 e a+c = s2, com (r,s) = 1. Como b2 = (a − c)(a + c) = r2s2, obtemos que

Logo chegamos ao seguinte resultado:

[SEC. 1.8: ALGUMAS APLICACOES DA FATORACAO UNICA 31

Teorema 6. As solucoes da equacao a2 = b2 + c2 nos inteiros positivos sao

onde λ e um numero inteiro positivo qualquer e r e s sao numeros naturais ımpares, com s > r e (r,s) = 1.

Nos paragrafos anteriores, mostramos que toda solucao e dessa forma. Para provar que toda tripla dessa forma e solucao, observamos que a e c sao naturais pois s2 − r2 e s2 + r2 sao pares. Por fim

Considere agora a seguinte equacao an = bn + cn.

Estudamos acima esta equacao para n = 2. Fermat escreveu nas margens de um livro, ha mais de 350 anos atras, que possuia uma demonstracao de que esta equacao nao tinha solucao em inteiros todos nao nulos, para n ≥ 3. Este resultado ficou conhecido como o “Ultimo Teorema de Fermat”. So nesta decada, depois de inumeras tentativas de solucao pelos mais renomados matematicos, este resultado foi demonstrado por Wiles. Seja

α = cos que e uma raız n-esima da unidade, isto e, αn = 1. Considere o seguinte conjunto de numeros:

Sn = {p(α) : p(X) e um polinomio com coeficientes inteiros}.

Cauchy e Lame, de maneira independente, nos meados do Seculo XIX, pensaram que tinham demostrado o “Ultimo Teorema de Fermat”, mas suas demonstracoes tinham um furo: assumiam que o conjunto de numeros Sn admitia fatoracao unica, o que infelizmente

nao ocorre para todo n. Kummer observou este erro e foi capaz de demonstrar que para uma infinidade de numeros primos n o conjunto

Sn admite fatoracao unica em um sentido mais amplo (o numero 37 e o primeiro primo n para o qual Kummer nao conseguiu estabelecer tal fatoracao). Para n = 4, este resultado e verdade, e o conjunto Sn e conhecido como inteiros de Gauss (pois este demonstrou a fatoracao unica nesse conjunto). Obseve que

13 nao sao racionais.

2. Para um numero racional positivo r e um numero natural n, caracterize quando √ r e um numero racional.

3. Determine todos os triangulos retangulos cujos lados tem comprimentos inteiros tais que a diferenca do comprimento de um dos catetos para o da hipotenusa e 1.

4. Mostre que e necessario demonstrar o “Ultimo Teorema de Fermat” apenas quando o expoente n for primo.

5. Sejam a,b e c numeros naturais tais que a2 + 2b2 = c2 e

MDC(a,b,c) = 1. Mostre que existem numeros naturais r e s tais que (r,s) = 1 e

6. Mostre que a4+b4 = c2 nao possui solucao inteira com abc 6= 0.

7. Encontre um algoritmo da divisao, como o de Euclides, para S4.

Capıtulo 2 Congruencias

Neste capıtulo apresentaremos o conceito de congruencia modulo um natural, nocao que foi criada por Gauss, e mostraremos propriedades basicas a seu respeito. Dentre os principais resultados apresentados, destacamos os seguintes:

• O Pequeno Teorema de Fermat. Uma pequena variante deste resultado permitiu a Rabin elaborar um algoritmo (randomizado) eficiente para decidir se um numero natural e primo ou composto. Este algoritmo, que tem quase tres decadas, ainda e utilizado na pratica para decidir primalidade. (Encontrar dois numeros primos “grandes” e essencial para utilizar o sistema de criptografia de chave publica conhecido por RSA.)

• O Teorema de Euler. Este resultado generaliza o Pequeno

Teorema de Fermat e e fundamental para o funcionamento do RSA. (Em criptografia, poderia ser chamado do Teorema Fundamental do RSA.)

• O Teorema de Wilson. Este resultado caracteriza numeros primos atraves do calculo de um fatorial. Seguindo este topico, faremos consideracoes sobre a complexidade de realizar exponenciacao e calcular o fatorial modulo um natural.

• O Teorema Chines dos Restos. Este resultado e classico e foi utilizado pelos chineses em aplicacoes militares (para calcular o numero de soldados em seus exercitos).

Sempre discutiremos algoritmos associados com estes resultados, bem como o custo da execucao destes procedimentos.

Seja n um numero natural maior que 1, que manteremos fixo durante toda essa secao. Diremos que dois inteiros a e b sao congruentes modulo n, e denotamos por a ≡ b mod n, se e somente se n divide a − b. Listaremos abaixo algumas propriedades que essa relacao possui:

(C1) a ≡ a mod n; (C2) se a ≡ b mod n, entao b ≡ a mod n; (C3) se a ≡ b mod n e b ≡ c mod n, entao a ≡ c mod n; (C4) se a ≡ b mod n e a′ ≡ b′ mod n, entao a+a′ ≡ b+b′ mod n; (C5) se a ≡ b mod n e a′ ≡ b′ mod n, entao a′ ≡ b′ mod n.

A primeira e segunda propriedade sao imediatas. A terceira tambem: como n divide a − b e b − c, entao n divide a soma desses numeros que e a−c. Consequentemente a ≡ c mod n. Qualquer outra relacao que possua as tres primeiras propriedades e dita de equivalencia. Varios resultados que valem para a relacao de congruencia modulo um natural tambem sao verificados numa relacao de equivalencia qualquer. A igualdade nos reais e paralelismo em retas no espaco (uma reta e paralela a si mesma) sao exemplos de relacoes de equivalencia. Porem, ser maior ou igual nao e uma relacao de equivalencia nos reais.

Agora estabeleceremos a quarta e a quinta propriedades. Como a ≡ b mod n e a′ ≡ b′ mod n, temos que n divide a − a′ e b − b′. Logo tambem divide

donde seguem a quarta e a quinta propriedades. Definimos a classe de congruencia de um inteiro a como

Observe que a ∈ a. Vamos definir operacoes de adicao e multiplicacao de classes de congruencias e mostrar que essas operacoes possuem as mesmas propriedades aritmeticas que as dos inteiros. Isto e, o conjunto de classes de equivalencia modulo um natural, munido com estas operacoes, e um anel.

Demonstracao. Basta mostrar que a ⊆ c, ja que a ∈ c e por esse resultado c ⊆ a, e teremos a igualdade de conjuntos. Se b ∈ a, entao a ≡ b mod n. Como c ≡ a mod n, pois c ∈ a, temos que c ≡ b mod n, por (C3). Logo b ∈ c e consequentemente a ⊆ c.

Lema 7. Se a e b sao inteiros, entao a = b ou a ∩ b = ∅.

Demonstracao. Suponha que a∩b 6= ∅ e que c ∈ a∩b. Pelo Lemma 6, segue-se que c = a e c = b. Consequentemente a = b.

O seguinte conjunto e conhecido como os inteiros modulo n. Pelo algoritmo da divisao de Euclides, para cada inteiro a, existem inteiros q e r tais que

Logo a ≡ r mod n e daı a = r. Isto e, toda classe de congruencia tem um representante entre 0 e n − 1. Consequentemente

0,1,2,,n − 1}

Vamos mostrar que todas as classes listadas acima sao diferentes. Suponha que 0 ≤ r,r′ < n e que r = r′. Nesse caso, r−r′ = λn, para algum inteiro λ, e necessariamente r = r′. Logo |Zn| = n.

Sejam a,b ∈ Zn, definimos a soma e o produto dessas classes de congruencias como respectivamente

Como essas operacoes dependem dos representantes escolhidos, temos que mostrar que estao bem definidas. Caso a = a′ e b = b′, segue que a + b = a′ + b′ e ab = a′b′, por respectivamente (C4) e (C5). Essas operacoes de Zn possuem todas as propriedades das operacoes dos inteiros: sao comutativas, associativas, ambas tem elemento neutro, a adicao possui inverso e a multiplicacao e distribuitiva com relacao a adicao. Vamos mostrar a validade da ultima propriedade, as demais ficam como exercıcio. Se a,b,c ∈ Zn, entao

Portanto Zn e um anel.

1. Faca as tabuas de adicao e multiplicacao para Z6. 2. Encontre o resto da divisao de 7256 por 15.

3. Um elemento a de um anel A e dito nilpotente quando existe k ∈ N tal que ak = 0. Caracterize os naturais n para os quais o anel Zn possui um elemento nilpotente diferente de 0?

4. Estabeleca a validade do criterio para decidir se um inteiro e divisıvel por 3 (tres) que voce aprendeu na quarta serie do ensino fundamental.

5. Mostre a validade da “prova dos nove” que foi ensinada na segunda serie do ensino fundamental.

(Parte 4 de 4)

Comentários