Logaritmo discreto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais. Em particular, um logaritmo loga(b) é a solução de uma equação ax = b sobre os reais ou complexos. De maneira análoga, se g e h são elementos de um grupo cíclico finito G então a solução x da equação gx = h é chamada logaritmo discreto na base g de h no grupo G.

Exemplo[editar | editar código-fonte]

Logaritmos discretos são talvez mais simples de entender no grupo (Zp)×. Este é o conjunto {1, …, p − 1} de classes de equivalências sob a multiplicação módulo o primo p.

Se queremos encontrar o k-ésimo potência de um dos números neste grupo, podemos fazer isso encontrando k-esimas potências como um inteiro e então encontrando o resto da divisão por p. Este processo é chamado exponenciação discreta. Por exemplo, considere (Z17)×. Para calcular 34 neste grupo, primeiro calculamos 34 = 81, e então dividimos 81 por 17, obtendo o resto 13. Logo 34 = 13 no grupo (Z17)×.

Logaritmo discreto é apenas a operação inversa. Por exemplo, pegue a equação 3k ≡ 13 (mod 17) para k. Como mostrado acima k=4 é uma solução, mas não é a única. Desde que 316 ≡ 1 (mod 17) segue que se n é um inteiro então 34+16 n ≡ 13 × 1n ≡ 13 (mod 17). Assim a equação tem infinitas soluções da forma 4 + 16n. Além disso, desde que 16 é o menor inteiro positivo m que satisfaz 3m ≡ 1 (mod 17), i.e. 16 é a ordem multiplicativa de 3 em (Z17)×, estas são as únicas soluções. De maneira equivalente, a solução pode ser expressa da forma k ≡ 4 (mod 16).

Definição[editar | editar código-fonte]

De maneira geral, seja G um grupo cíclico finito com n elementos. Assumimos que este grupo está escrito multiplicativamente. Seja b um gerador de G; então todo elemento g de G pode ser escrito na forma g = bk para algum inteiro k. Além disso, quaisquer dois inteiros k1 and k2 representando g serão congruentes módulo n. Podemos então definir uma função

\log_b:\  G\ \rightarrow\ \mathbb{Z}_n

(onde Zn denota o anel de inteiros módulo n) atribuindo para cada g a classe de congruência de k módulo n. Esta função é um isomorfismo de grupos, chamado logaritmo discreto na base b.

A fórmula para mudança de base para logaritmos naturais permanece válida: Se c é outro gerador de G, então temos

\log_c (g) = \log_c (b) \cdot \log_b (g).

Algoritmos[editar | editar código-fonte]

Nenhum algoritmo clássico eficiente para computar logaritmo discreto de maneira geral logb g é conhecido. O algoritmo ingênuo é elevar b a maiores e maiores potências k até que o g desejado seja encontrado. Este algoritmo requer um tempo de execução linear no tamanho do grupo G e logo exponencial no número de dígitos do tamanho do grupo. Existe um algoritmo quântico eficiente de acordo com Peter Shor.[1]

Existem algoritmos mais sofisticados, geralmente inspirados em algortimos similares para fatoração de inteiros. Estes algoritmos executam mais rápido do que o algoritmo ingênuo, mas nenhum deles roda em tempo polinomial (no número de dígitos do tamanho do grupo).

Comparação com a fatoração de inteiros[editar | editar código-fonte]

Enquanto o problema de computar logaritmos discretos e o problema da fatoração de inteiros sejam problemas distintos, eles compartilham algumas propriedades:

  • ambos problemas são difíceis (não se conhece algoritmo eficiente para computadores não-quânticos),
  • para ambos, algoritmos eficientes para computadores quânticos são conhecidos,
  • algoritmos de um problema são frequentemente adaptados para o outro, e
  • a dificuldade dos dois problemas vem sendo utilizada para a construção de vários sistemas criptográficos.

Criptografia[editar | editar código-fonte]

Computar logaritmos discretos é aparentemente difícil. Não apenas não se conhece algoritmo eficiente para os piores casos, mas a complexidade para os casos médios é demonstradamente quase tão difícil quanto o pior caso, demonstração esta que pode ser feita utilizando-se random self-reducibility.

Ao mesmo tempo, o problema inverso da exponenciação discreta não é tão difícil (pode ser computado eficientemente utilizando exponenciação por quadrados, por exemplo). Esta assimetria é análoga aquela entre a fatoração e multiplicação de inteiros. Ambas assimetrias tem sido exploradas na construção de sistemas criptográficos.

Escolhas populares para o grupo G na criptografia de logaritmo discreto são os grupos cíclicos (Zp)×; veja a encriptação de El Gamal, a troca de chaves de Diffie-Hellman, e o algoritmo para Assinatura digital.

As aplicações mais recentes da criptografia usam logaritmos discretos em subgrupos cíclicos de curvas elípticas sobre campos finitos; veja Criptografia com curva elíptica.

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]