Logaritmo discreto

Na matemática, para determinados números reais a {\displaystyle a} e b {\displaystyle b} , o logaritmo log b ⁡ ( a ) {\displaystyle \log _{b}(a)} é um número x {\displaystyle x} tal que b x = a {\displaystyle b^{x}=a} . O logaritmo discreto generaliza este conceito para um grupo cíclico. Um exemplo simples é o grupo de inteiros módulo um número primo (como 5) sob a multiplicação modular de elementos não nulos. Por exemplo, considere b = 2 {\displaystyle b=2} no grupo multiplicativo módulo 5, cujos elementos são { 1 , 2 , 3 , 4 } {\displaystyle \{1,2,3,4\}} . Então: 2 1 = 2 , 2 2 = 4 , 2 3 = 8 ≡ 3 ( mod 5 ) , 2 4 = 16 ≡ 1 ( mod 5 ) . {\displaystyle 2^{1}=2,\quad 2^{2}=4,\quad 2^{3}=8\equiv 3{\pmod {5}},\quad 2^{4}=16\equiv 1{\pmod {5}}.} As potências de 2 módulo 5 percorrem todos os elementos não nulos, portanto, os logaritmos discretos existem e são dados por: log 2 ⁡ 1 = 4 , log 2 ⁡ 2 = 1 , log 2 ⁡ 3 = 3 , log 2 ⁡ 4 = 2. {\displaystyle \log _{2}1=4,\quad \log _{2}2=1,\quad \log _{2}3=3,\quad \log _{2}4=2.} Mais genericamente, em qualquer grupo G {\displaystyle G} , as potências b k {\displaystyle b^{k}} podem ser definidas para todos os inteiros k {\displaystyle k} , e o logaritmo discreto log b ⁡ ( a ) {\displaystyle \log _{b}(a)} é um inteiro k {\displaystyle k} tal que b k = a {\displaystyle b^{k}=a} . Na aritmética modular em relação a um inteiro m {\displaystyle m} , o termo mais comumente usado é índice: Pode-se escrever k = i n d b a ( mod m ) {\displaystyle k=\mathbb {ind} _{b}a{\pmod {m}}} (lê-se "o índice de a {\displaystyle a} na base b...