Criptografia números primos e algoritmos

Criptografia números primos e algoritmos

(Parte 2 de 4)

Obtemos (1.1), pois 1 e o inverso aditivo de −1 e o inverso aditivo e unico. (Caro leitor, chegue a esta mesma conclusao de outra maneira, isto e, sem usar a unicidade do inverso aditivo.) Agora mostraremos o seguinte:

Lema 1. Em um anel ordenado A, temos que 1 e positivo.

Demonstracao. Iniciaremos estabelecendo que −1 nao e positivo. Argumentaremos por contradicao. Suponha que −1 e positivo. Por (1.1), (−1)(−1) = 1. Consequentemente 1 e positivo, ja que o conjunto de elementos positivos e fechado com relacao ao produto. Isto e, 1 e −1 sao ambos positivos; uma contradicao a propriedade da tricotomia. Portanto, −1 nao e positivo. Como 1 6= 0, temos que 1 ou −1 e positivo. Logo 1 e positivo, pois −1 nao e positivo, e o resultado segue.

Em um anel ordenado A, com conjunto de elementos positivos

P, podemos definir uma relacao de ordem da seguinte forma: para a,b ∈ A, diremos que a ≥ b se somente se a = b ou a − b ∈ P, e que a > b quando a − b ∈ P. Nao e difıcil verificar que essa relacao de ordem tem as propriedades usuais, que deixaremos como exercıcio para o leitor:

(Para as tres ultimas propriedades, podemos substituir todos os ≥ por >. Verique tambem isto.)

Utilizando a propriedade da tricotomia, podemos mostrar que, em um anel ordenado, o produto de um numero positivo por um negativo e negativo e que o produto de dois numeros negativos e positivo. Conclua, a partir desta informacao, que este anel nao possui divisores de zero. Mostraremos que o produto de dois elementos negativos a e b e positivo. Por definicao, −a e −b sao positivos. Como o conjunto de numeros positivos e fechado com relacao ao produto, temos que (−a)(−b) e positivo. Contudo:

Isto e, o produto de a por b e positivo. (Nesta passagem estamos utilizando um fato que nao foi estabelecido e que ficara como exercıcio: se c e um elemento de um anel, entao −c = (−1)c.)

Vamos assumir que Z e um anel ordenado cujo conjunto de elementos positivos e N − {0}.

A ultima propriedade que assumiremos sobre os inteiros e tao importante que sera descrita em uma secao propria.

1.2.3 Princıpio da inducao finita

Como temos agora uma relacao de ordem nos inteiros podemos anunciar o ultimo axioma a respeito desses numeros que iremos assumir.

Axioma da boa ordenacao. Todo subconjunto nao vazio dos naturais possui um menor elemento.

(Pode-se mostrar que, a menos de isomorfismo, Z e o unico anel ordenado possuindo o axioma da boa ordenacao para o conjunto de elementos positivos.) Primeiro encontraremos qual e o menor numero inteiro positivo.

Proposicao 1. O menor numero inteiro positivo e o 1.

Demonstracao. Pelo axioma da boa ordem, existe um menor numero inteiro positivo a. Comparando a com 1, temos uma das tres possibilidades:

Sera suficiente mostrar que (i) e (i) nao ocorrem. Claramente (i) nao ocorre, ja que 1 e um numero inteiro positivo e nao pode ser menor que o menor inteiro positivo. Agora assuma que (i) ocorre. Multiplicando ambos os lados da desigualdade por a, obtemos

Como o conjunto dos numeros inteiros positivos e fechado com relacao ao produto, temos que a e um numero inteiro positivo que e menor que a; um absurdo! Concluımos que (i) tambem nao ocorre.

Usando esse axioma, podemos estabelecer o princıpio da inducao finita, que e uma ferramenta importantıssima para demonstrar resultados discretos.

Teorema 1 (Princıpio da inducao finita — primeira forma). Seja P(n) uma proposicao a respeito de um natural n. Se

(i) assumindo P(n) podemos deduzir P(n + 1), entao P(n) e verdadeira para todo natural n.

Demonstracao. Seja S o conjunto dos naturais n tais que P(n) nao e verdadeira. Queremos mostrar que S = ∅. Vamos argumentar por contradicao: suponha que S 6= ∅. Pelo princıpio da boa ordem, S possui um menor elemento m. Por (i) temos que m > 0. Como m e o menor elemento de S, entao m − 1 e um natural que nao pertence a S. Logo P(m − 1) e verdadeira. Por (i) podemos deduzir P(m) a partir de P(m − 1), e daı P(m) tambem e verdadeira. Chegamos a uma contradicao e a hipotese de S ser nao vazio e falsa. Logo S = ∅ e P(n) e valida para todo natural n.

Claro, se desejarmos provar P(n) para n ≥ k, entao basta mostrarmos que P(k) e verdadeiro e que (i) vale para todo n ≥ k. Este fato pode ser demostrado de maneira analoga.

Vamos aplicar o resultado que acabamos de demonstrar. Considere a seguinte proposicao, que chamaremos de S(n), a respeito de um natural n: a soma dos n primeiros inteiros positivos e igual a metade do produto de n por seu consecutivo, em uma linguagem matematica podemos expressar este fato por:

(Mostre que o natural consecutivo ao natural n e n + 1, isto e, n + 1 e o menor natural maior que n.) Para mostrar que S(n) e verdadeira para todo natural n temos de seguir os passos enunciados no princıpio da inducao finita:

Passo 1: S(0) e verdadeira pois:

Passo 2: Vamos supor que S(n) e verdadeira, isto e que a seguinte relacao e valida:

e podemos deduzir S(n + 1) apartir de S(n).

Logo S(n) e verdadeira para todo natural n, pelo princıpio da inducao finita.

Esse princıpio vai ser tao utilizado que iremos enunciar uma versao mais poderosa dele, sem no entanto prova-la, pois sua demonstracao e similar a da primeira versao:

Teorema 2 (Princıpio da inducao finita — segunda forma). Seja P(n) uma proposicao a respeito de um natural n. Se

(i) quando n ≥ 1, assumindo P(k), para todo k < n, podemos deduzir P(n), entao P(n) e verdadeira para todo natural n. Demonstracao. Exercıcio. Divirta-se!

Iremos concluir esta secao fazendo uma aplicacao deste resultado.

O mesmo comentario feito no paragrafo que segue a demonstracao do princıpio da inducao finita, na primeira forma, tambem vale neste caso.

A sequencia (fn) de Fibonacci e famosa. Os dois primeiros termos sao: f0 = 1 e f1 = 2. Para cada natural n, com n ≥ 2, esta sequencia e definida recursivamente como:

Considere a seguinte proposicao, que chamaremos F(n), sobre um numero natural n (que pode ser zero):

(Vamos assumir as propriedades usuais sobre numeros reais para mostrar esta identidade. Caso algum leitor nao queira assumir tais propriedades, pode ignorar este exemplo.)

Para mostrar que F(n) e verdadeira para todo natural n temos de seguir os passos enunciados no princıpio da inducao finita:

que e o valor de f0.

Passo 2: Para n > 1, vamos supor que F(m) e verdadeira, para todo m < n. Necessitamos estabelecer que F(n) tambem e valida a partir deste fato. Caso isto ocorra, pelo princıpio da inducao finita na segunda forma, concluımos que F(n) vale para todo n. Temos dois casos a considerar: quando a recorrencia (1.2) pode ser utilizada e quando nao pode. A recorrencia pode ser utilizada apenas quando n ≥ 2. Portanto, o caso n = 1 tem de ser tratado separadamente.

que e o valor de f1. Portanto, neste caso, F(n) e verificada. Assuma que n ≥ 2. Neste caso F(n − 2) e F(n − 1) sao verdadeiras, por hipotese de inducao. Isto e, podemos substituir n por n−1 ou n−2 na

identidade (1.3). Para tornar as equacoes compactas, substituiremos os numeros envolvidos por letras, a saber:

e a equacao (1.3) pode ser reescrita como

= Aαn +Bβn ja que α e β sao as raızes do polinomio p(X) = X2−X−1. Portanto, F(n) tambem e verificada neste caso.

Terminamos esta seccao com uma lista de exercıcios complementares (ja que varios foram deixados ao longo da secao). Resolva-os utilizando um dos princıpios de inducao finita vistos na subsecao anterior.

1. Mostre que a soma dos angulos internos de um polıgono convexo com n lados, quando medido em radianos, e igual a π(n − 2).

2. Mostre que a soma dos n primeiros termos de uma progressao geometrica de razao q, q 6= 1, e termo inicial a e igual a

3. Mostre que dentre quaisquer k numeros inteiros consecutivos existe um divisıvel por k.

4. Mostre que a soma dos n primeiros cubos de naturais e igual a[ n(n + 1)

5. Caso existam numeros racionais a,b e c tais que a soma dos n primeiros quadrados de naturais e igual a an3 + bn2 + cn, para todo natural n, determine tais numeros.

6. Mostre que 5 divide n5 − n, para todo natural n. 7. Mostre que o numero de subconjuntos com i elementos de um conjunto com n elementos e igual a( n

8. Para quaisquer numeros complexos a e b e natural n, mostre que

9. Utilizando (1.3), mostre que o n-esimo termo da sequencia de Fibonacci e dado por:

onde {x} denota o inteiro mais proximo do numero real x.

10. Seja (an) uma sequencia de numeros complexos definida para todo natural n. Assuma que existam numeros complexos r e s tais que, para todo natural n ≥ 2,

Isto e, um termo e definido recursivamente a partir dos dois termos anteriores da sequencia, como no caso da de Fibonacci.

Mostre que, quando α e β sao as raızes de p(X) = X2−rX−s, entao, para todo natural n,

1. Um conjunto contendo n retas, sem que quaisquer duas delas seja paralelas, divide o plano em varias regioes. Mostre que:

(i) Estas regioes podem ser pintadas com duas cores de forma que regioes que possuem um segmento em comum na sua fronteira sao pintadas com cores diferentes.

(i) O plano fica dividido em pelo menos 2n regioes.

(i) O mınimo descrito no item anterior e atingido se e somente se estas retas possuem um ponto em comum.

(iv) O plano fica dividido em no maximo 1 + n(n+1)2 regioes. (v) O maximo descrito no item anterior e atingido se e somente se estas retas estao em posicao geral, isto e, a intercecao de quaisquer tres delas e vazia.

O que ocorre em cada um dos itens desta questao quando permitimos que o conjunto possa ter retas em paralelo?

1.3 Numeros primos

Nessa secao, iniciaremos o estudo dos numeros primos, e o nosso objetivo, nas secoes vindouras, e mostrar que todo inteiro pode ser escrito de maneira unica, a menos de ordem dos fatores, como o produto de numeros primos.

Um natural p maior que 1 e dito primo quando e impossıvel escrever p como o produto de dois naturais a e b com a > 1 e b > 1. Consequentemente, os unicos divisores de um numero primo sao a unidade e ele proprio. Como exemplos de primos temos 2,3,5,7,1,13,...

Vamos mostrar agora que qualquer natural nao-nulo pode ser escrito como o produto de um numero finito de primos. O produto do conjunto vazio da origem ao 1. O produto do conjunto unitario {p} sera p. Iremos convencionar isto, para que possamos enunciar esta proposicao em toda sua generalidade.

Proposicao 2. Todo natural nao-nulo pode ser escrito como o produto de um numero finito de primos.

Demonstracao. Para estabelecer este fato, iremos usar o princıpio da inducao finita em sua segunda forma:

Passo 1: Observe que o resultado vale para n = 1, pois 1 e o produto do conjunto vazio (de primos).

Passo 2: Suponha que n > 1 e que todo natural k < n possa ser escrito como o produto de numeros primos. Se n e um numero primo, entao n e o produto de numeros primos. Suponha entao que n nao e um numero primo. Nesse caso, existem naturais a e b tais que a < n, b < n e n = ab. Por hipotese, existem primos pi e qj tais que:

e consequentemente

Podemos enunciar agora um dos resultados mais antigos conhecidos a respeito dos numeros primos:

Teorema 3 (Teorema de Euclides). Existe um numero infinito de numeros primos.

Demonstracao. Argumentaremos por contradicao. Suponha que exis- ta apenas um numero finito de primos: p1,p2,...,pk. Considere o seguinte natural n = p1p2 ···pk + 1. Pela proposicao anterior, existe um primo p que divide n. Observe que p nao pode ser igual a nenhum pi ja que pi nao divide 1. Chegamos a uma contradicao e, consequentemente, existem infinitos numeros primos.

Existem teoremas maravilhosas a respeito da distribuicao dos numeros primos, vamos descrever um deles agora. Considere π(x)

como sendo o numero de primos menores ou iguais a x. Gauss conjecturou o seguinte resultado, que foi provado por Hadamard e Poussin e e conhecido na literatura como o teorema dos numeros primos:

π(x)lnx

Como sua demonstracao nao e simples, foge ao proposito dessas notas, e nao sera apresentada.

1. Um numero natural e dito composto quando pode ser escrito como o produto de dois numeros naturais menores. Mostre que todo numero natural composto n possui um divisor menor ou igual a √ n.

3. Um numero primo da forma 2n − 1, para n ∈ N, e dito de Mersenne. Quando isto ocorre, mostre que n tem de ser primo.

4. A recıproca do exercıcio anterior vale? Isto e, se n e primo, entao 2n − 1 e primo?

5. Um numero primo da forma 2n + 1, para n ∈ N, e dito de

Fermat. Quando isto ocorre, mostre que n tem de ser uma potencia de 2.

6. Para k ∈ {1,3}, seja Pk o conjunto dos numeros primos que deixam resto k quando divididos por 4. Mostre que:

(i) O produto, podendo ter repeticao, de qualquer numero de membros de P1 deixa resto 1 quando dividido por 4.

(i) O produto de um numero par de membros de P3 deixa resto 1 quando dividido por 4.

(i) O produto de um numero ımpar de membros de P3 deixa resto 3 quando dividido por 4.

7. Utilizando o exercıcio anterior e um argumento similar ao utilizado na demonstracao do Teorema de Euclides, mostre que existe um numero infinito de primos que deixam resto 3 quando dividido por 4.

1.4 Algoritmo da divisao de Euclides

Nessa secao apresentaremos o algoritmo da divisao de Euclides. A fatoracao unica nos inteiros e decorrencia desse algoritmo. Outros conjuntos que possuem duas operacoes como as dos inteiros gozam da propriedade de fatoracao unica quando tambem possuem um algoritmo de divisao similar ao de Euclides.

Teorema 4 (Algoritmo de divisao de Euclides). Se a ∈ Z e b ∈ N − {0}, entao existem unicos inteiros q e r tais que a = qb + r e 0 ≤ r < b.

Demonstracao. Seja S o seguinte conjunto:

Pelo axioma da boa ordem, existe um menor elemento r ∈ S. Como r ∈ S, existe q ∈ Z tal que r = a − qb.

Observe que r < b, caso contrario 0 ≤ r−b = a−qb−b = a−(q+1)b e r − b ∈ S, o que nao pode ocorre pois r e o menor elemento de S. Acabamos de demonstrar que a pode ser escrito na forma qb+r com 0 ≤ r < b.

Vamos mostrar que essa decomposicao e feita de maneira unica. Suponha que

Caso q = q′ temos que r = r′ como querıamos demostrar. Podemos supor que q 6= q′, mais ainda, que q > q′. Obtemos que

[SEC. 1.4: ALGORITMO DA DIVISAO DE EUCLIDES 17

Observe que o lado esquerdo dessa igualdade e maior ou igual a b e o direiro menor que b. Chegamos a uma contradicao e o resultado segue.

O algoritmo da divisao, quando b e um inteiro negativo, e uma imediata consequencia do algoritmo que acabamos de apresentar. Enuncie tal algoritmo e o demonstre.

Dado dois inteiros a e b, um dos quais nao e nulo, existe um maior natural que divide simultaneamente a e b. Esse numero e dito o maior divisor comum (MDC) de a e b e e denotado por (a,b). Antes de descrever o algoritmo de Euclides para encontrar o maior divisor comum entre a e b, observamos que (a,b) = (b,a), (a,0) = a e (a,b) = (|a|,|b|). Portanto, apresentamos o algoritmo para o calculo do MDC apenas quando os inteiros envolvidos sao ambos positivos.

Algoritmo de Euclides para encontrar o MDC. A entrada desse algoritmo sao dois inteiros positivos a e b e a saıda (a,b).

Passo 2: Defina ri+1 como o resto da divisao de ri−1 por ri, isto e, ri−1 = qiri + ri+1 com 0 ≤ ri+1 < ri;

Passo 3: Se ri+1 6= 0 incremente i de 1 e volte para o passo 2, senao (a,b) = ri.

(Parte 2 de 4)

Comentários