4
$\begingroup$

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?
$\endgroup$
5
$\begingroup$

No one knows, but:

  • 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.)

  • It is suspected that there is no polynomial-time algorithm for factoring or discrete logarithm, but we have no proof. (Evidence for the suspicion: we haven't been able to find a polynomial-time algorithm for either, despite a lot of trying.)

  • There is no known (classical) reduction between discrete log and factoring. However, I personally wouldn't be shocked if one were found, or if both were found to be instances of some broader problem, or something. For instance, when we find an algorithm technique that works against one, historically often we've been able to adapt it to the other as well. So, they seem to be connected or related in some deep way.

$\endgroup$
  • $\begingroup$ So, when there is no known reduction between both problems, how can the same algorithm (Shor's Algorithm) solve both of them on a quantum computer? I know how Shor's Algorithm works for factorization (by using QFT = Quantum Fourier Transformation to find the order of a cyclic group), but I couldn't find an intelligible description of Shor's Algorithm for solving the discrete logarithm. I just think that Shor also reduces the discrete log problem to QFT. $\endgroup$ – Hubert Schölnast Aug 28 at 6:50
  • $\begingroup$ @HubertSchölnast the reduction you are talking about works by preparing an exponentially large superposition and then looking for the period in that monster. We know how to do this efficiently on a quantum computer only. $\endgroup$ – Dmitri Urbanowicz Aug 28 at 9:41
  • 1
    $\begingroup$ I would like to note that, some instance of the DLog problem can be easy. How can there be insecure elliptic curves if the discrete logarithm problem is hard? $\endgroup$ – kelalaka Aug 29 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.