Logaritmo discreto

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

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. Visto 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, visto 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

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   →   Z n {\displaystyle \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 ) ⋅ log b ⁡ ( g ) . {\displaystyle \log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g).}

Algoritmos

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).

  • Baby-step giant-step
  • Pollard's rho algorithm for logarithms
  • Pollard's kangaroo algorithm (aka Pollard's lambda algorithm)
  • Pohlig-Hellman algorithm
  • Index calculus algorithm
  • Number field sieve
  • Function field sieve

Comparação com a fatoração de inteiros

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

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

Referências

  1. ↑ http://arxiv.org/abs/quant-ph/9508027
  • Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
  • Stinson, Douglas Robert (2006), Cryptography: Theory and Practice, ISBN 978-1-58488-508-5 3rd ed. , London: CRC Press