# Is DISCRETE LOG a NP hard problem?

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?

• It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $$\cap$$ coNP. See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring. It's similarly easy to prove that discrete log is in NP $$\cap$$ coNP; see, e.g., How hard is finding the discrete logarithm?. Moreover, if any problem in NP $$\cap$$ coNP is NP-complete, it follows that NP = coNP. This would be an unexpected result.)