Equação exponencial modular sobre os inteiros sem algoritmo eficiente para a solução.
O Problema do Logaritmo Discreto (PLD ou, em inglês, DLP) consiste em, dado um número \(p\) primo, um gerador \(g\) de \(\mathbb{Z}_p\) e um inteiro \(t<p\), encontrar o inteiro \(s\) tal que \[ t = g^s \text{ mod }p \] em outras palavras, encontrar um inteiro que seja o logaritmo de \(t\) na base \(g\), módulo \(p\).
Até hoje não foi desenvolvido nenhum algoritmo clássico eficiente (i.e. de complexidade polinomial) para resolver o PLD. Por outro lado, na computação quântica, o algoritmo de Shor pode ser usado para resolver o PLD de forma eficiente.
A dificuldade de se resolver o problema do logaritmo discreto é contrastada pela facilidade da checagem de uma resposta, pois a exponenciação modular pode ser feita de forma muito eficiente. Dessa maneira, o problema do logaritmo discreto serve como uma ferramenta para a construção de criptosistemas assimétricos.
Alguns algorítmos que empregam esse problema em sua segurança são o 9 ElGamal e o Menezes-Vanstone.
Seja \(p=17\), \(g=7\) e \(t=10\). O PLD diz que é dificil encontrar um inteiro \(s\) tal que \[ 10 = 7^s \text{ mod }17 \] No caso, esse número é \(s=9\).
Uma vez que Curvas Elípticas sobrem \(\mathbb{Z}_p\) definem um grupo abeliano, podemos definir multiplicação (\(a \cdot b = \underbrace{ a +\dots+ a }_{ b \text{ vezes} }\)). Dessa maneira, o problema do logaritmo discreto está igualmente definido sobre curvas elípticas: dados \(Q\) e \(P\) pontos de uma curva elíptica, encontrar um inteiro \(s\) tal que
\[ Q = sP \]
Por exemplo, seja a curva \(E: y^2=x^3+2x+4\) sobre \(\mathbb{Z}_{11}\). Dados \(Q=(9,5)\) e \(P=(3,2)\), encontrar \(s=11\) de forma que \(sP = \underbrace{ (3,2)+\dots+(3,2) }_{ 11 \text{ vezes} } = (9,5)\).
Esse problema é conhecido como Problema do Logaritmo Discreto sobre Curvas Elípticas (PLD-CE ou, em inglês, DLP-EC ou EC-DLP).
Acredita-se que este problema seja ainda mais difícil que o PLD e fatoração em primos. Até hoje o algoritmo mais rápido para o PLD-CE tem complexidade \(O(\sqrt{ p })\) (D. M. Gordon e K. S. McCurley).
Por conta disso, existe uma grande diferença no tamanho de chaves entre problemas baseados em PLD e em PLD-CE: um sistema de 1024 bits sobre PLD em geral oferece a mesma segurança que um sistema de 160 bits sobre o PLD-CE.