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