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 log_a(b) é a solução de uma equação a^x = 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 g^x = h é chamada logaritmo discreto na base g de h no grupo G.

Exemplo

Logaritmos discretos são talvez mais simples de entender no grupo (Z_p)^×. 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 (Z₁₇)^×. Para calcular 3⁴ neste grupo, primeiro calculamos 3⁴ = 81, e então dividimos 81 por 17, obtendo o resto 13. Logo 3⁴ = 13 no grupo (Z₁₇)^×.

Logaritmo discreto é apenas a operação inversa. Por exemplo, pegue a equação 3^k ≡ 13 (mod 17) para k. Como mostrado acima k=4 é uma solução, mas não é a única. Visto que 3¹⁶ ≡ 1 (mod 17), segue que se n é um inteiro então 3^{4+16 n} ≡ 13 × 1ⁿ ≡ 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 3^m ≡ 1 (mod 17), i.e. 16 é a ordem multiplicativa de 3 em (Z₁₇)^×, 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 = b^k para algum inteiro k. Além disso, quaisquer dois inteiros k₁ and k₂ representando g serão congruentes módulo n. Podemos então definir uma função

\log _{b}:\ G\ \rightarrow \ \mathbb {Z} _{n}

(onde Z_n 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

Nenhum algoritmo clássico eficiente para computar logaritmo discreto de maneira geral log_b 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 (Z_p)^×; 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

↑ 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

[1] ttp://arxiv.org/abs/quant-ph/9508027

[1]