How fast is Factorization reduced to a Discrete Logarithm?

Question

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$?

Answer 1

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})$.

Index calculus algorithms need to know the order of the subgroup being solved during the linear algebra phase (and if we knew the order of the subgroup, we would be able to factor without the discrete logarithm). In any event, the runtime would depend on the group size rather than the exponent size.

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.