Logaritmo discreto
Na matemática, para determinados números reais e , o logaritmo é um número tal que . O logaritmo discreto generaliza este conceito para um grupo cíclico. Um exemplo simples é o grupo de inteiros módulo um número primo sob a multiplicação modular de elementos não nulos.
Seja G {\displaystyle G} um grupo qualquer. Denote sua operação de grupo por multiplicação e seu elemento neutro por 1 {\displaystyle 1} . Seja b {\displaystyle b} qualquer elemento de G {\displaystyle G} . Para qualquer inteiro positivo k {\displaystyle k} , a expressão b k {\displaystyle b^{k}} denota o produto de b {\displaystyle b} com ele mesmo k {\displaystyle k} vezes: De forma semelhante, seja b − k {\displaystyle b^{-k}} o produto de b − 1 {\displaystyle b^{-1}} com ele mesmo k {\displaystyle k} vezes. Para k = 0 {\displaystyle k=0} , a k {\displaystyle k} -ésima potência é a identidade: b 0 = 1 {\displaystyle b^{0}=1} . Seja a {\displaystyle a} também um elemento de G {\displaystyle G} . Um inteiro k {\displaystyle k} que resolve a equação b k = a {\displaystyle b^{k}=a} é chamado de logaritmo discreto (ou simplesmente logaritmo, neste contexto) de a {\displaystyle a} na base b {\displaystyle b} . Escreve-se k = log b a {\displaystyle k=\log _{b}a} .
Potências de 10
Para qualquer número a {\displaystyle a} nesta lista, pode-se calcular log 10 a {\displaystyle \log _{10}a} . Por exemplo, log 10 10000 = 4 {\displaystyle \log _{10}{10000}=4} e log 10 0.001 = − 3 {\displaystyle \log _{10}{0.001}=-3} . Essas são instâncias do problema do logaritmo discreto. Outros logaritmos de base 10 nos números reais não são instâncias do problema do logaritmo discreto, porque envolvem expoentes não inteiros. Por exemplo, a equação log 10 53 = 1.724276 … {\displaystyle \log _{10}{53}=1.724276\ldots } significa que 10 1.724276 … = 53 {\displaystyle 10^{1.724276\ldots }=53} . Embora os expoentes inteiros possam ser definidos em qualquer grupo usando produtos e inversos, expoentes reais arbitrários, como este 1.724276…, exigem outros conceitos, como a função exponencial.
Potências de um número real fixo
Um exemplo semelhante vale para qualquer número real não nulo b {\displaystyle b} . As potências formam um subgrupo multiplicativo G = { … , b − 2 , b − 1 , 1 , b 1 , b 2 , … } {\displaystyle G=\{\ldots ,b^{-2},b^{-1},1,b^{1},b^{2},\ldots \}} dos números reais não nulos. Para qualquer elemento a {\displaystyle a} de G {\displaystyle G} , pode-se calcular log b a {\displaystyle \log _{b}a} .
Aritmética modular
Um dos cenários mais simples para logaritmos discretos é o grupo Zp×. Este é o grupo da multiplicação módulo o primo p {\displaystyle p} . Seus elementos são as classes de congruência não nulas módulo p {\displaystyle p} , e o produto de grupo de dois elementos pode ser obtido pela multiplicação inteira comum dos elementos seguida da redução módulo p {\displaystyle p} . A k {\displaystyle k} -ésima potência de um dos números deste grupo pode ser calculada encontrando sua k {\displaystyle k} -ésima potência como um número inteiro e depois encontrando o resto após a divisão por p {\displaystyle p} . Quando os números envolvidos são grandes, é mais eficiente reduzir módulo p {\displaystyle p} várias vezes durante o cálculo. Independentemente do algoritmo específico usado, essa operação é chamada de exponenciação modular. Por exemplo, considere Z17×. Para calcular 3 4 {\displaystyle 3^{4}} neste grupo, calcula-se 3 4 = 81 {\displaystyle 3^{4}=81} e depois divide-se 81 {\displaystyle 81} por 17 {\displaystyle 17} , obtendo um resto de 13 {\displaystyle 13} . Portanto, 3 4 = 13 {\displaystyle 3^{4}=13} no grupo Z17×.
Potências da identidade
No caso especial em que b {\displaystyle b} é o elemento neutro 1 {\displaystyle 1} do grupo G {\displaystyle G} , o logaritmo discreto log b a {\displaystyle \log _{b}a} é indefinido para a {\displaystyle a} diferente de 1 {\displaystyle 1} , e todo inteiro k {\displaystyle k} é um logaritmo discreto para a = 1 {\displaystyle a=1} .
As potências obedecem à identidade algébrica comum b k + l = b k ⋅ b l {\displaystyle b^{k+l}=b^{k}\cdot b^{l}} . Em outras palavras, a função definida por f ( k ) = b k {\displaystyle f(k)=b^{k}} é um homomorfismo de grupos do grupo dos números inteiros Z {\displaystyle \mathbf {Z} } sob a adição sobre o subgrupo H {\displaystyle H} de G {\displaystyle G} gerado por b {\displaystyle b} . Para todo a {\displaystyle a} em H {\displaystyle H} , log b a {\displaystyle \log _{b}a} existe. Inversamente, log b a {\displaystyle \log _{b}a} não existe para valores de a {\displaystyle a} que não estão em H {\displaystyle H} . Se H {\displaystyle H} for infinito, então log b a {\displaystyle \log _{b}a} também é único, e o logaritmo discreto equivale a um isomorfismo de grupos Por outro lado, se H {\displaystyle H} for finito de ordem n {\displaystyle n} , então log b a {\displaystyle \log _{b}a} é único apenas até a congruência módulo n {\displaystyle n} , e o logaritmo discreto equivale a um isomorfismo de grupo
O problema do logaritmo discreto é considerado computacionalmente intratável. Para um computador clássico (ou seja, não quântico), nenhum algoritmo eficiente (de tempo polinomial) é conhecido ainda para o cálculo de logaritmos discretos em geral. Um algoritmo geral para computar log b a {\displaystyle \log _{b}a} em grupos finitos G {\displaystyle G} consiste em elevar b {\displaystyle b} a potências k {\displaystyle k} cada vez maiores até que o a {\displaystyle a} desejado seja encontrado. Esse algoritmo às vezes é chamado de multiplicação por tentativa. Requer um tempo de execução linear no tamanho do grupo G {\displaystyle G} e, portanto, exponencial no número de dígitos do tamanho do grupo. Assim, trata-se de um algoritmo de tempo exponencial, prático apenas para pequenos grupos G {\displaystyle G} . Algoritmos mais sofisticados existem, geralmente inspirados em algoritmos semelhantes para a fatoração de inteiros. Esses algoritmos são executados mais rapidamente do que o algoritmo ingênuo, alguns deles em tempo proporcional à raiz quadrada do tamanho do grupo e, portanto, exponencial na metade do número de dígitos do tamanho do grupo. Entretanto, nenhum deles é executado em tempo polinomial (no número de dígitos do tamanho do grupo).
Embora o cálculo de logaritmos discretos e a fatoração de inteiros sejam problemas distintos, eles compartilham algumas propriedades:
Existem grupos nos quais calcular logaritmos discretos é aparentemente difícil. Em alguns casos (por exemplo, subgrupos de ordem prima grande de grupos Z p × {\displaystyle \mathbf {Z} _{p}^{\times }} ), não apenas não há um algoritmo eficiente conhecido para o pior caso, como a complexidade do caso médio pode ser demonstrada como sendo quase tão difícil quanto o pior caso usando autorredutibilidade aleatória. Ao mesmo tempo, o problema inverso da exponenciação discreta não é difícil (ele pode ser computado eficientemente usando a exponenciação por quadratura, por exemplo). Essa assimetria é análoga àquela existente entre a fatoração de inteiros e a multiplicação de inteiros. Ambas as assimetrias (e outras possíveis funções de via única) têm sido exploradas na construção de sistemas criptográficos. Escolhas populares para o grupo G {\displaystyle G} na criptografia de logaritmo discreto (CLD) são os grupos cíclicos Z p × {\displaystyle \mathbf {Z} _{p}^{\times }} (por exemplo, o sistema ElGamal, a Troca de Chaves Diffie-Hellman e o Algoritmo de Assinatura Digital) e subgrupos cíclicos de curvas elípticas sobre corpos finitos (veja Criptografia de curvas elípticas).
