patternMajor
How hard is finding the discrete logarithm?
Viewed 0 times
thehowdiscretehardfindinglogarithm
Problem
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.
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.
Solution
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 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
-
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.
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 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
-
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.
Context
StackExchange Computer Science Q#2658, answer score: 23
Revisions (0)
No revisions yet.