# Quantum algorithm to get $d$ (private exponent) directly without factoring first

Shor's algorithm is for finding period $$r$$ such that $$a^r\equiv 1\bmod N$$. Knowing period we can factor $$N$$.

In RSA we encrypt message $$m$$ by $$m^e\bmod N$$ ($$e$$ and $$N$$ are public keys).

Let us pick the message (and so we know $$m$$) and encrypt to get $$y\equiv m^e\bmod N$$.

Can Shor's algorithm be modified to get $$d$$ (the private decryption key) directly such that $$y^d\equiv m\bmod N$$ without factoring $$N$$? (the equation $$y^d\equiv m\bmod N$$ looks similar to $$a^r\equiv 1\bmod N$$)

If so, is there any advantage in terms of the number of qubits needed?

To clarify: I want to learn $$d$$ before learning any other information which will factor on a classical computer in $$BPTIME$$. Casting the problem as a discrete logarithm problem requires knowledge of order of $$m$$ which already factors $$N$$ without finding $$d$$. I want to find $$d$$ without knowing other information which can factor $$N$$ before learning $$d$$.

First, welcome to the quantum stack exchange. Please find below an answer, in two parts:

1. Given $$m \in \mathbb Z_N^*$$ and $$y = m^e$$, computing $$d$$ so that $$m = y^d$$ is the discrete logarithm problem (DLP).

Shor's quantum algorithm for the DLP — that is also described in [Shor94] alongside Shor's order-finding and factoring algorithms — solves this problem (when slightly generalized as in e.g. [E19p] to work in the cyclic subgroup of $$\mathbb Z_N^*$$ that is generated by $$m$$).

However, it is not more efficient than Shor's order-finding algorithm. Furthermore, it requires the order $$r$$ of $$m$$ to be known, and if you know $$r$$ or a multiple thereof then you can factor $$N$$ classically (with probability very close to one via [E21b], provided that you select $$m$$ uniformly at random from $$\mathbb Z_N^*$$ at the outset, and this is easy).

Another possible option is of course to compute the order $$r$$ of $$m$$, or a multiple thereof, and to use that $$d \equiv e^{-1} \text{ mod } r$$, if this is what you are looking for? This would not save qubits. It may perhaps save runs when using Shor's original reduction, but not when using [E21b]. Yet another option is to use the variation in [E21a] that computes $$d$$ without requiring $$r$$ to be known beforehand, but this variation is also less efficient (and it in fact computes both $$d$$ and $$r$$ even if you need not explicitly compute $$r$$ in the post-processing to compute $$d$$). In short, I think that this all boils down to a question of semantics, because once you learn $$d$$, you know that $$ed - 1$$ is a multiple of $$r$$, and so you can use [E21b] to factor $$N$$ classically.

2. If you are looking to achieve an advantage by phrasing the RSA integer factoring problem (IFP) as a DLP, then you may instead wish to have a look at [EH17]. In this work, we pick $$g$$ uniformly at random from $$\mathbb Z_N^*$$, for $$N = pq$$ a random RSA integer, compute $$x = g^{(N+1)/2} = g^{(p+q)/2},$$ classically, and then compute the logarithm $$d = \log_g x$$ using a quantum algorithm that leverages that $$d$$ is short in relation to the order of $$g$$ with overwhelming probability, and which critically does not require the order to be known. With high probability of success, this algorithm yields $$d = (p+q)/2$$, and since we also know that $$N = pq$$ it is then trivial to solve for $$p$$ and $$q$$ classically.

This DLP-based algorithm is more efficient than Shor's order finding-based approach [E20], but it only works for RSA integers (it can be extended to other special forms, but factoring RSA integers is arguably the interesting case).

(Note that $$d$$ in the second part of this answer is different from $$d$$ in the first part, and that the order $$r$$ of $$m$$ is also the order of $$y$$ by construction since $$e$$ is coprime to $$\lambda(N)$$ in RSA. Note also that $$d$$ in the first part of this answer would typically be on $$[0, r)$$, in which case $$d$$ is not the full private key, although it will decrypt $$y$$.)

• I thought for Shor's discrete log algorithm modulo $N$, the factorization of $N$ has to be known. And so solving $y^d\equiv m\bmod N$ is not quite possible by Shor's algorithm for discrete log as factorization of $N$ is unknown. Am I wrong? Jul 27, 2023 at 0:27
• @Turbo You would need to know the order $r$ of $m$, but to compute $r$ classically without the complete factorization of $N$ is hard. You would also need the complete factorization of $p - 1$ for $p$ the prime factors of $N$. (If you had an efficient classical algorithm for computing $r$, then you could use it to factor $N$.) Jul 27, 2023 at 0:36
• So we cannot compute $d$ as discrete logarithm problem without factoring using your idea? Jul 27, 2023 at 0:42
• @Turbo Maybe without explicitly factoring $N$, if you count the "Another possible option (..)" paragraph in the first part of my answer as a valid solution? It depends on what you mean by "without factoring". Once you learn $d$, then $ed - 1$ is a multiple of the order $r$, and so you can factor $N$ completely via E21b. Jul 27, 2023 at 0:53
• I want to learn $d$ before learning any other information which will factor on a classical computer. Jul 27, 2023 at 1:16