How hard is finding the discrete logarithm?

Problem Detail: 

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.

I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what approaches (i.e. algorithms) are the best for accomplishing this task.

The wikipedia link above doesn't really give very concrete runtimes. I'm hoping for something more like what the best known methods are for finding such.

Asked By : Matt Groff

Answered By : Niel de Beaudrap

Short answer.
If we formulate an appropriate decision problem version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes NP, coNP, and BQP.

A decision problem version of Discrete Log.
The discrete logarithm problem is most often formulated as a function problem, mapping tuples of integers to another integer. That formulation of the problem is incompatible with the complexity classes P, BPP, NP, and so forth which people prefer to consider, which concern only decision (yes/no) problems. We may consider a decision problem version of the discrete log problem which is effectively equivalent:

Discrete Log (Decision Problem). Given a prime $N$, a generator $a \in \mathbb Z_N^\times$ of the multiplicative units modulo $N$, an integer $0 < c < N$, and an upper bound $b \in \mathbb N$, determine whether there exists $1 \leqslant L \leqslant b$ such that $a^L \equiv c \pmod{N}$.

This would allow us to actually compute log_a(c) modulo N by binary search, if we could efficiently solve it. We may then ask to which complexity classes this problem belongs. Note that we've phrased it as a promise problem: we can extend it to a decision problem by suspending the requirements that $N$ be prime and $a \in \mathbb Z_N^\times$ a generator, but adding the condition that these restrictions hold for any 'YES' instance of the problem.

Discrete Log is in  BQP.
Using Shor's algorithm for computing the discrete logarithm (Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer), we may easily contain Discrete Log in BQP. (To test whether or not $a \in \mathbb Z_N^\times$ actually is a generator, we may use Shor's order-finding algorithm in the same paper, which is the basis for the discrete logarithm algorithm, to find the order of $a$ and compare it against $N-1$.)

Discrete Log is in  NP ∩ coNP.
If it is actually the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, a sufficient certificate either for a 'YES' or a 'NO' instance of the decision problem is the unique integer $0 \leqslant L < N-1$ such that $a^L \equiv c \pmod{N}$. So it suffices to show that we can certify whether or not the conditions on $a$ and $N$ hold. Following Brassard's A note on the complexity of cryptography, if it is both the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, then it is the case that $$ r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$} $$ by definition (using the fact that $\mathbb Z_N^\times$ has order $N-1$).

• A certificate that the constraints on $N$ and $a$ both hold would be a list of the prime factors $q_1, q_2, \ldots$ dividing $N-1$, which will allow us to test the above congruence constraints. (We can test whether each $q_j$ is prime using AKS test if we wish, and test that these are all of the prime factors of $N-1$ by attempting to find the prime-power factorization of $N-1$ with only those primes.)

• A certificate that one of the constraints on $N$ or $a$ fail would be an integer $q$ which divides $N-1$, such that $a^{(N-1)/q} \equiv 1 \pmod{N}$. It isn't necessary to test $q$ for primeness in this case; it immediately implies that the order of $a$ is less than $N-1$, and so it is a generator of the multiplicative group only if $N$ fails to be prime.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2658