# How fast is Factorization reduced to a Discrete Logarithm?

Given a RSA modulus $$n$$, which is the product of two safe primes: \begin{align*} P &= 2p + 1 \quad\quad\quad Q = 2q + 1 \\ n &= P \cdot Q = 4p q + 2 p + 2 q + 1 \end{align*} The hidden group order is then \begin{align*} \Phi(n) &= (P-1)(Q-1) = 4p q \end{align*} Choosing some random element $$z \in \mathbb{F}_n^*$$, then most likely $$z^4 \in C_{p q}$$ (the subgroup of $$\mathbb{F}_n^*$$ that has order $$pq$$). Let's call $$z^4$$ now $$g$$. For every $$g \in C_{pq}$$ it holds that $$g^x = g^{x \bmod p q}$$. We have $$\frac{n-1}{2} = 2p q + p + q$$, so it follows that \begin{align*} g^\frac{n-1}{2} &\equiv g^{p + q} \pmod{n} \end{align*} We define $$p>q$$. Computing the discrete logarithm $$\text{dlog}_g(g^{p+q})=p+q$$ takes $$\mathcal{O}(\sqrt{p})$$ time, which suffices to compute the group order $$\Phi(n)$$, and thus factor $$n$$. Note that the running time of the baby-step giant-step algorithm depends only on the size of $$p$$ here and not on the group size $$\Phi(n)$$.

Question: Is there an algorithm to compute this discrete logarithm faster than factoring $$n$$? Would the running time of index calculus depend on the group size here or would it depend on the size of $$p$$?

• Note that if you can compute a discrete log modulo a composite, then you can factor the composite; this holds true even if the composite is not a product of two safe primes. This implies that there is no algorithm to computing the discrete log that is faster than factoring... Nov 15, 2022 at 11:58

Classically speaking, it will be hard to do better than Pollard's kangaroo method (essentially equivalent to baby-step-giant-step, but with better memory usage), which, as you note, will take time $$O(\sqrt{p+q})$$.
The quantum Fourier transform (i.e. Shor's algorithm) can take advantage of this by requiring $$O(\log(p+q))$$ qubits for the transform rather than $$O(\log(pq))$$. This approach has been noted by Ekerå and Håstad in their paper Quantum algorithms for computing short discrete logarithms and factoring RSA integers.