Detalhes

Categoria: Chave Pública

Atualização: Terça, 14 Abril 2009 14:44

Autor: vovó Vicki

Acessos: 34720

Operações modulares da Teoria dos Números

Normalmente as operações modulares e os números primos são conceitos fáceis de serem absorvidos. Estes conceitos fazem parte da Teoria dos Números, uma área da matemática que lida apenas com números inteiros. Uma das coisas que sempre me chamou a atenção é que os matemáticos adoram encontrar particularidades e certas características de comportamento dos números. Como não sou matemática, vejo isto como uma mania de querer descobrir a personalidade dos números, o que transforma a matemática numa investigação de detetive, num jogo de caça ao tesouro ou numa brincadeira de "o que é, o que é?". Isto me ajuda um bocado

Raiz Primitiva

Por exemplo, fui dar uma olhada no que é a raiz primitiva de um módulo. Descobri que um número g é a raiz primitiva de um módulo n quando este número elevado às potências de 1 até n-1 (mod n) fornecer todos os resíduos possíveis deste módulo. Por exemplo, 3 é uma raiz primitiva do (mod 5) porque:

     31 (mod 5) =  3 (mod 5) = 3
     32 (mod 5) =  9 (mod 5) = 4
     33 (mod 5) = 27 (mod 5) = 2
     34 (mod 5) = 81 (mod 5) = 1

Estas operações resultaram em todos os resíduos que o módulo 5 pode oferecer. O fato de não estarem em ordem não tem importância, pois a premissa é que todos apareçam uma vez. Apenas para fixar esta noção, observe o comportamento de 4 no módulo 5:

     41 (mod 5) =   4 (mod 5) = 4
     42 (mod 5) =  16 (mod 5) = 1
     43 (mod 5) =  64 (mod 5) = 4
     44 (mod 5) = 256 (mod 5) = 1

Estes cálculos nos mostram que 4 não é uma raiz primitiva do módulo 5. Quando o valor dos módulos é pequeno, pode-se fazer o cálculo com lápis e papel, mas, se o valor do módulo for muito grande, a calculadora não vai ter espaço para os dígitos e os cálculos vão levar um tempo enorme. Ainda bem que os matemáticos acham atalhos que facilitam a nossa vida. Conforme Burton publicou em 1986, um dos atalhos que podemos pegar é

     Se o MDC(g,n)=1 (ou seja, g e n são primos entre si)
     e a ordem multiplicativa de g (mod n) for igual a φ(n), onde φ(n) é a função totiente,
     então g é uma raiz primitiva do módulo n.

Deu nó na sua cabeça? Pra falar a verdade, na minha também deu. É que estão faltando algumas peças para resolver este quebra-cabeça. O MDC, ou máximo divisor comum, não tem segredos. Já a ordem multiplicativa e a função totiente...

Ordem Multiplicativa

O jeito é ir por partes. A ordem multiplicativa, também chamada de ordem modular, Haupt-exponent (expoente principal) ou simplesmente ordem, é uma característica dos módulos (mais um dos seus traços de pesonalidade ) Se obtivermos a resposta para a pergunta "Qual é o expoente de um número (mod n) para que o resultado seja 1?", saberemos a ordem deste número neste módulo. Por exemplo, a ordem de 2 (mod 7) é igual a 3 porque 2¹ (mod 7) = 2, 2² (mod 7) = 4 e 2³ (mod 7) = 1. Como o resultado procurado é o expoente 3, a ordem multiplicativa de 2 (mod 7) = 3. Reveja os cálculos que foram feitos para achar uma das raízes primitivas do módulo 5. Eles também nos mostram que a ordem de 3 (mod 5) = 4.

Mas, e se o módulo for muito grande? Será que precisamos calcular um monte de potências módulo até descobrir qual é a ordem multiplicativa de um número neste módulo? Alguns matemáticos famosos já cuidaram disso, facilitando as coisas para nós.

O Pequeno Teorema de Fermat

Fermat nos conta que, se o módulo n for um número primo e se o número g não for um múltiplo de n, então a ordem multiplicativa do número g no módulo n é igual a n-1 porque

     gn-1 (mod n) = 1

Função Totiente de Euler

A função totiente de Euler, também conhecida como função phi de Euler, é designada por phi(n) ou φ(n). Esta função, onde o n representa um módulo, nos revela mais uma faceta modular: indica quantos resíduos (os restos das divisões) deste módulo são primos em relação a n. Por exemplo, no módulo 6, os resíduos possíveis vão de 1 a 5. Como o valor zero indica ausência de resíduo, ele não é considerado. Agora, comparando 6 com cada elemento do conjunto de resíduos possíveis, quando é que estes números são primos entre si? Acompanhe:

     6 e 1 --> Sim, o único divisor comum é 1, ou seja, MDC(6, 1) = 1
     6 e 2 --> Não, ambos são divisíveis por 1 e 2
     6 e 3 --> Não, ambos são divisíveis por 1 e 3
     6 e 4 --> Não, ambos são divisíveis por 1 e 2
     6 e  5 --> Sim, MDC(6, 5) = 1

De acordo com os resultados, φ(6) é representado pelo conjunto de dois elementos {1, 5}, ou seja, φ(6) = 2. Aí acontece mais uma coisa interessante: quando n for um número primo, todos os resíduos são relativamente primos a n. Se soubermos disso de antemão, não será preciso calcular nenhum MDC, é só lembrar que o zero é a ausência de resíduo. Então, φ(7) = 6, φ(5) = 4 e, generalizando, φ(n) = n - 1 E tem mais uma dica. Se o módulo for um número composto por dois fatores primos p e q, então

     phi(n) ou φ(n) = (p - 1) x (q - 1)

Para conferir, basta fazer as contas com o módulo 6. Como 6 é composto pelos números primos 2 e 3, então phi(6) = (2 - 1) x (3 - 1) = 1 x 2 = 2. Guarde bem esta última fórmula porque ela aparece uma porção de vezes em algoritmos de chave pública!

Mas Euler também nos forneceu uma outra ferramenta muito útil que serve para calcular a ordem multiplicativa de um número num módulo que não seja primo. Acabamos de ver que Fermat quebrou o galho para os módulos que são primos. Euler generalizou o Pequeno Teorema de Fermat e quebrou um galho ainda maior.

A generalização de Euler do Pequeno Teorema de Fermat

Euler nos ensina que, se o MDC(g, n) = 1, ou seja, se o número g e o módulo n forem primos entre si, então a ordem multiplicativa de g (mod n) é igual a phi(n) porque

     gφ(n) (mod n) = 1