In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:
FACT
Given: A composite number, i.e. a positiv integer which is the product of some prime numbers: $x = p_1 \cdot p_2 \cdot \ldots \cdot p_n$ You know only $x$.
Wanted (calculation problem): At least one factor of this composite number.
As a decision problem: For a given $k \le x$: Is there a factor $p_i \le k$?
(You just need to solve the decision problem $\log x$ times to solve the calculation problem. So, as long as the complexity of the decision problem is polynomial or harder, both flavors of the problem belong to the same time-class.)DISCRETE LOG
Given: $x = a^n \mod p$. There $p$ is prime and you know $x$, $a$ and $p$.
Wanted (calculation problem): Find $n$.
As a decision problem: Is there some $n \le k$ such that $x=a^n \mod p$?
(Also here you need to solve the decision problem only $\log p$ times to solve the calculation problem.)
I know, that both problems, as far as we know, are not in the complexity class $P$, i.e. for both problems there is no algorithm know that could solve them in polynomial time on a deterministic Turing Machine.
I know, that both problems can be solved in polynomial time on a non-deterministic Turing machine, which, per definition means, that both of them are in the class $NP$.
Let's suppose, that $P \ne NP$. Under this assumption $NP$ is partitioned into three sub-classes:
- $P$
All problems which are solvable in polynomial time on a deterministic Turing Machine - $NPC$
NP-complete.
The subset of $NP$ to which all problems in $NP$ can be reduced, i.e. the subset of $NP$ that is NP-hard. - $NPI$
NP-intermediate
All problems which are in $NP$ but neither in $P$ nor in $NPC$.
It is known, than $NPI$ is not empty if $P \ne NP$ (Ladner's theorem).
(If $N=NP$, then also $NPC=P$, which means, that $NPI$ must be empty.)
I know, that under the assumption that $P \ne NP$, FACT seems to be in $NPI$, since until now nobody could prove that FACT $\in NPC$.
But I could not find similar statements about DISCRETE LOG.
Here are my questions:
- Is DISCRETE LOG know to be in $NPC$? Or is it thought to be in $NPI$?
- If it is in $NPI$:
- Is there a know algorithm to reduce FACT to DISCRETE LOG?
- Or is there an algorithm to reduce DISCRETE LOG to FACT?
- Are they maybe even equivalent, i.e. reduzibel in both directions?