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.

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

• Logaritmo
• Teoria dos grupos
• Aritmética modular
• Diffie-Hellman
• Criptografia com curva elíptica

Referências

• 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