Criptografia números primos e algoritmos

Criptografia números primos e algoritmos

(Parte 3 de 4)

Demonstracao. Temos de provar que (a,b) = ri. Primeiro, vamos mostrar, por inducao em n, que ri divide ri+1−n para todo 0 ≤ n ≤ i + 1. Isso e claramente verdade quando n e igual a 0 e a 1, ja que ri+1 = 0. Suponha que n > 1 e que ri divide ri+1−k para todo

inducao finita na sua segunda forma. Logo ri e um divisor comum de a e b.

Seja d um divisor comum de a e b. Vamos mostrar por inducao que d divide rn para todo 0 ≤ n ≤ i, em particular divide ri e consequentemente ri e o maior divisor comum de a e b. Por hipotese, o resultado vale para k igual a 0 e a 1. Suponha que n > 1 e que d divide rk para todo k < n. Como rn = rn−2 − qn−1rn−1, entao d

tambem divide rn e mais uma vez o resultado segue pelo princıpio da inducao na sua segunda forma.

No proximo resultado estimamos o numero de divisoes que sao necessarias para calcular o MDC atraves do algoritmo de Euclides. Para um numero real x, denotamos por ⌊x⌋ o maior inteiro menor ou igual a x.

Proposicao 3. Se a e b sao inteiros tais que a ≥ b > 0, entao o algoritmo de Euclides realiza no maximo 1 + 2⌊log2 a⌋ divisoes para calcular o MDC de a e b.

Demonstracao. Sejam r0,r1,...,ri,ri+1 = 0 como no algoritmo de Euclides para o calculo do MDC. Vamos mostrar que rk > 2rk+2, (1.5) para todo k < i. Do algoritmo, sabemos que

Logo (1.5) segue. Seja m o maior inteiro tal que 2m ≤ i. Por inducao em n, mostra-se, a partir de (1.5), que para n satisfazendo 1 ≤ n ≤ m. Fazendo n = m e r0 = a em (1.6) obtemos

Consequentemente 2m < a e daı

[SEC. 1.4: ALGORITMO DA DIVISAO DE EUCLIDES 19

O algoritmo de Euclides e extremamente eficiente, e e usado ate hoje para calcular o maior divisor comum de dois inteiros e escreve-lo como combinacao linear destes, com uma pequena otimizacao, onde permitimos que os restos involvidos possam ser negativos. Isto e, utilizamos a seguinte variante do algoritmo de divisao de Euclides: se a e b sao inteiros, com b 6= 0, entao existem unicos q e r tais que

(Para garantir a existencia e a unicidade do quociente e resto e necessario que o intervalo onde o resto pode variar tenha comprimento |b| e inclua exatamente um dos extremos. Verifique isto.) Com este novo algoritmo de divisao garantimos que o valor do resto cai pela metade em cada etapa e nao apos duas etapas como no algoritmo que apresentamos. Vamos fazer um exemplo, calcular (947,−409):

e o maior divisor comum entre 947 e −409 e 1. Usando esse exemplo, vamos escrever o maior divisor comum entre esses numeros como combinacao linear deles:

e daı 1 = 130·947+301·(−409). Usando uma raciocınio analogo ao feito acima, podemos mostrar o seguinte resultado:

Proposicao 4. Se a e b sao inteiros, um dos quais nao e nulo, entao existem inteiros α e β tais que αa + βb = (a,b).

Demonstracao. Primeiro mostraremos que podemos supor que a e b sao nao-negativos. Sabemos que (a,b) = (|a|,|b|). Caso

onde sg(x) e igual a 1, quando x for nao-negativo, ou −1, quando x for negativo. Portanto basta mostrar este resultado quando a e b sao nao-negativos. Se um deles for zero, digamos b = 0, entao o resultado segue pois

A partir de agora, vamos assumir que a e b sao positivos.

Sejam r0,r1,...,ri,ri+1 = 0 como no algoritmo de Euclides para o calculo do MDC. Vamos mostrar por inducao, da primeira forma, em n, com n satisfazendo 1 ≤ n ≤ i−1, que existem inteiros αn e βn tais que

Se definirmos αn+1 = βn − qi−n−1αn e βn+1 = αn, a ultima equacao pode ser reescrita como que e exatamente (1.7) quando n e substituıdo por n + 1. Portanto (1.7) vale por inducao da primeira forma. O resultado segue ao fazermos n = i − 1 em (1.7).

[SEC. 1.5: REPRESENTACAO DE NUMEROS INTEIROS 21

Observe que temos um algoritmo para encontrar α e β implıcito na demonstracao da proposicao anterior. Mais ainda, esta proposicao sera de fundamental importancia para mostrar que todo inteiro nao nulo decompoe-se como produto de primos de maneira unica.

1.4.1 Exercıcios 1. Calcule o maior divisor comum dos seguintes pares de numeros:

2. Para cada um dos itens da questao anterior, expresse o maior divisor comum de cada par de numeros como a combinacao linear destes numeros.

3. Suponha que a,q1,q1,...,qi sao como no algoritmo de Euclides para o calculo do MDC. Mostre que

4. Seja αn e βn como na Proposicao 4. Mostre que |αn| ≤ ri−1−n e |βn| ≤ ri−n.

1.5 Representacao de numeros inteiros

Consideraremos apenas o caso em que o numero e inteiro positivo, ja que a extensao para os numeros inteiros e imediata, bastando adicionar um sinal de − (menos) a esquerda da representacao quando o numero for negativo e o zero e representado como 0.

Proposicao 5. Seja b um numero natural tal que b > 1. Para cada numero inteiro positivo n, existem unicos numeros naturais

k, b0, b1, b2, bk tais que bi < b, para todo i ∈ {0, 1, 2, . . . , k}, bk 6= 0

Demonstracao. Inciaremos estabelecendo a existencia de k e dos bi’s. Faremos isto por inducao do segundo tipo em n. Observe que o resultado vale para todo natural n tal que n < b. Neste caso, tome k = 0 e b0 = b. Podemos supor que n ≥ b. Por hipotese de inducao, o resultado vale para todo natural menor que n. Pelo algoritmo da divisao, existem inteiros q e r tais que

Como n ≥ b, temos que q ≥ 1. Como q < n, por hipotese de inducao,

Portanto

A exsitencia da decomposicao de n segue por inducao bastando tomar b0 = r. A unicidade segue por inducao do segundo tipo em n pois o quo- ciente e o resto da divisao de n por b sao respectivamente

e sao unicos.

Seja b um inteiro tal que b > 1. Diremos que (bk ···b2b1b0)b e a representacao de n na base b quando n,b,k,b0,b1,b2,...,bk satisfazem as hipoteses e as conclusoes da Proposicao 5. Note que na demonstracao desta proposicao esta implıcito um algoritmo para obter a representacao de n na base b. Quando estiver claro com que base estamos trabalhando, a representacao de n nesta base sera de- notada simplesmente por bk ···b2b1b0. Um inteiro pertencente ao conjunto {0,1,...,b−1} e dito um dıgito para a base b. Usualmente trabalhamos na base 10. No ocidente, cada dıgito para a base 10 possui um sımbolo especial para designa-lo que e largamente conhecido:

[SEC. 1.6: CUSTO DE REALIZAR OPERACOES ARITMETICAS 23

0,1,2,3,4,5,6,7,8 e 9 (descritos por ordem crescente de tamanho). Contudo, os computadores trabalham na base 2, com apenas dois que sao 0 e 1. O numero de dıgitos de n na base b e denotado por digb(n) e e igual a k + 1. Note que

No caso em que b = 2, omitimos oındice desta funcao, isto e, dig2(n) e simplesmente denotado por dig(n).

3. Faca uma adaptacao nos algoritmos conhecidos de soma, comparacao, subtracao, multiplicacao e divisao para numeros naturais quando escritos em uma base b (que pode ser diferente de 10).

4. Seja n um numero natural que possui k + 1 dıgitos quando escrito na base b. Mostre que bk ≤ n < bk+1.

5. Utilizando a questao anterior, demostre a igualdade que foi apresentada na equacao (1.9).

1.6 Custo de realizar operacoes aritmeticas

Nesta secao faremos a analise do custo das operacoes aritmeticas nos inteiros, com os algoritmos tradicionais (aqueles que aprendemos na escola ha muitos anos atras). Como os computadores trabalham com numeros escritos na base 2, consideraremos o custo de realizar as operacoes nesta base. (A seguir iremos definir como medir tal custo. Nao mostraremos aqui, mas o custo independe da base escolhida para representar os inteiros envolvidos na operacao.)

Sejam f e g funcoes que assumem valores reais definidas sobre subconjuntos dos numeros naturais (ou reais) que contem todo numero

natural (ou real) no intervalo [a,+∞), para algum natural a. Di- remos que f = O(g) quando existem um numero natural n0 e um numero real positivo C tais que, para todo n ≥ n0,

Por exemplo, quando f(x) e um polinomio de grau k com coeficientes reais, f(x) = O(xk).

Vamos analisar o custo das operacoes aritmeticas entre dois numeros naturais a e b que possuem no maximo k dıgitos na base 2. Nossas estimativas de custo seriam melhores caso utilizassemos o numero de dıgitos de a e de b na base 2. Nao faremos isto, pois temos apenas o interesse de estabelecer que o custo de tais operacoes e polinomial em k (observe que k e o tamanho de cada uma das duas entradas do algoritmo — que sao os numeros a e b). Isto e, nosso custo e um polinomio no tamanho da entrada do algoritmo. Um algoritmo com esta caracterıstica e conhecido como polinomial. Note que ao restringirmos a analise de custo ao caso em que a entrada do algoritmo sao numeros naturais a e b nao perdemos generalidade pois as operacoes aritmeticas entre numeros inteiros podem ser facilmente reduzidas a operacoes similares entre numeros naturais.

Lema 2. O numero de operacoes elementares realizadas em qualquer operacao de comparacao ou adicao ou subtracao entre dois numeros naturais com ate k dıgitos na base 2 e O(k), isto e, de tempo linear.

Para estimar o custo de um algoritmo, calculamos o numero de operacoes elementares que este realiza. Descreveremos o que consideramos como operacao elementar na demonstracao do lema que vira a seguir.

Demonstracao do Lema 2. Sejam a e b os numeros naturais tendo no maximo k dıgitos. Para simplificar nossa argumentacao iremos completar estes numeros com zeros a esquerda de forma que “fiquem com k dıgitos” (isto e, vamos operar considerando todas as k posicoes de memoria reservadas para estes numeros no computador).

Iniciaremos pela comparacao. Percorremos os dois numeros simultaneamente da esquerda para a direita, um dıgito de cada vez, e os comparamos. Caso sejam iguais avancamos para o dıgito seguinte

[SEC. 1.6: CUSTO DE REALIZAR OPERACOES ARITMETICAS 25 e continuamos com o algoritmo (caso nao seja possıvel avancar, estamos no dıgito mais a direita de cada um dos numeros e neste caso a = b). Caso sejam diferentes, um dıgito sera 0 e o outro sera 1. O numero que possui o dıgito 1 sera o maior e o algoritmo para retornando esta informacao. Consideraremos como operacao elementar a comparacao dos dois dıgitos. Neste algoritmo foram realizadas no maximo k comparacoes. Portanto seu custo sera O(k).

Necessitamos de uma posicao de memoria extra para o “vai um”, que inicialmente recebe o valor 0 (que ao final sera o (k + 1)-esimo dıgito da soma). Percorremos simultaneamente os dois numeros da direira para a esquerda um dıgito de cada vez. Neste momento calcula-se o dıgito correspondente da soma dos dois numeros observando tres posicoes de memoria: a do dıgito de a, a do dıgito de b e a do “vai um”. Sera 0 se existe um numero par de 1’s nestas posicoes e 1 caso contrario. O “vai um” recebe o valor de 0 caso existam no maximo um dıgito 1 nestas posicoes e 1 caso contrario. Esta computacao sera considerada como uma operacao elementar. Ao atingirmos o k-esimo dıgito da soma, colocamos o “vai um” como o (k + 1)-esimo dıgito da soma. Portanto realizamos k operacoes elementares e o custo do algoritmo sera O(k).

Para calcular a−b necessitamos primeiro realizar uma comparacao.

Caso a < b, calculamos b−a e o resultado sera igual a −(b−a). Caso a = b, o resultado sera 0. Portanto necessitamos apenas de um algoritmo para realizar a subtracao a − b no caso em que a > b. O custo desta etapa sera de uma comparacao, logo e O(k). O algoritmo sera o mesmo do da adicao exceto no calculo do valor a ser armazenado no “vai um” que sera igual a 1 quando o numero de dıgitos igual a 1 na posicao “vai um” e no dıgito de b for maior que o numero de digitos igual a 1 na posicao do dıgito de a. Esta segunda etapa tem custo O(k). Consequentemente o custo do algoritmo sera O(k).

Lema 3. O numero de operacoes elementares realizadas em qualquer operacao de multiplicacao ou divisao entre dois numeros naturais com ate k dıgitos na base 2 e O(k2), isto e, de tempo quadratico.

Existem algoritmos diferentes dos usuais para realizar as operacoes de multiplicacao e divisao de “numeros grandes” que sao muito mais eficientes. O custo de cada um destes algoritmos e O(k logk loglogk).

Nao apresentamos tais algoritmos aqui, pois fogem do objetivo deste curso.

Demonstracao. Sejam a e b numeros naturais possuindo no maximo k dıgitos quando representados na base 2. Suponha que b possua exatamente l dıgitos. O produto de a por b e igual a soma de um conjunto X de numeros com cardinalidade no maximo l, cada um sendo uma translacao de a, obtidos da seguinte forma: enumere as posicoes dos dıgitos de b da direita para esquerda com 0,1,2,...,l−1 e, caso na na posicao i o dıgito de b for igual a 1, adicione a X um numero obtido a partir de a colocando i dıgitos iguais a 0 na sua direira (isto e, uma translacao de a de i casas para a esquerda). Como a soma de quaisquer dois numeros em X tem no maximo 2k dıgitos, o custo de realizar a soma de todos elementos de X sera O(l − 1)O(2k) = O(lk) = O(k2). Deixo a analise do algoritmo da divisao por conta do leitor (veja o quinto exercıcio desta secao).

Lema 4. O custo para o calculo do maior divisor comum de dois numeros naturais com no maximo k dıgitos quando representados na base 2 e O(k3).

Demonstracao. Seja a o maior destes numeros. Pela Proposicao 3, o numero de divisoes realizadas pelo algoritmo de Euclides para o calculo do MDC e limitado superiormente por 2⌊log2 a⌋ + 1. Como dig(a) = ⌊log2 a⌋ + 1, este limite superior passa a ser 2dig(a) − 1 ≤ 2k − 1 = O(k). Pelo Lema 3, o custo de cada uma destas divisoes e

O(k2). Portanto, o custo do algoritmo de Euclides para o calculo do MDC sera O(k2)O(k) = O(k3).

1. Para um numero real a maior que 1, mostre que loga x = O(log2 x).

{1, 2,, k}, fi = O(gi).

4. Mostre que o custo do algoritmo usual para realizar a multiplicacao de dois numeros naturais a e b e igual a O(dig(a)dig(b)).

5. Dados numeros naturais a e b, o algoritmo da divisao garante a existencia de numeros inteiros q e r tais que a = qb + r, com 0 ≤ r < b. Mostre que o custo de fazer esta divisao com o algoritmo usual e O(dig(q)dig(b)).

6. Mostre que o custo de encontrar o MDC de dois numeros naturais a e b e O(dig(a)dig(b)) — use o exercıcio anterior e o exercıcio 3 da Secao 1.4. (Isto e, podemos obter uma estimativa muito melhor do que a apresentada nesta secao para este custo.)

7. Encontre uma estimativa para o custo de expressar o MDC de dois numeros naturais como a combinacao linear destes numeros (utilizando o algoritmo implıcito na demonstracao da Proposicao 4).

8. Escreva um algoritmo para encontrar a parte inteira da raiz quadrada de um numero natural n cujo custo seja O(dig2(n)3).

Nessa secao iremos demonstrar o teorema da fatoracao unica para os inteiros. O nucleo da demonstracao e o lema que provaremos a seguir:

Lema 5. Sejam a e b inteiros. Se um primo p divide ab, entao p divide a ou b.

Demonstracao. Suponha que p nao divide a. Nesse caso (p,a) = 1, pois os unicos divisores positivos de p sao 1 e p. Pela Proposicao 4, existem inteiros α e β tais que αa + βp = 1. Multiplicando esta relacao por b obtemos que αab + βpb = b. Como p divide ab, temos que p divide b.

Teorema 5 (Teorema fundamental da aritmetica). Todo numero inteiro n nao-nulo pode ser escrito de maneira unica na forma

· · · > pr e a1, a2,, ar sao inteiros positivos.

Demonstracao. Observe que basta mostrar o resultado para os naturais. Faremos a demonstracao por inducao do segundo tipo em n. O resultado e claramente verdadeiro para n = 1. Suponha que todo natural k < n pode ser escrito de maneira unica como produto de primos e que com p1 > p2 > · > pr e q1 > q2 > · > qs, todos primos. Sem perda de generalidade, podemos supor que p1 ≥ q1. Pelo lema anterior, p1 divide qi para algum i. Como p1 ≥ q1 > q2 > · > qs, segue que i = 1 e p1 = q1. Consequentemente

(Parte 3 de 4)

Comentários