How to find p,q in this problem? Suppose

\begin{align*}
  g^r &amp;\equiv h \pmod N, \\
  h^s &amp;\equiv g \pmod N,
\end{align*}

for known $g$, $h$, $r$, $s$, and $N$, but not $\phi(N)$.

Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.


Is $g$'s order $(r\cdot s - 1)/k$?

I think g's real order to be divided $\phi(N)$.

But $k$ is so big that I do not know what to do anymore.
How can I factorize N?


Note. In this case, we also have $g^{(r\cdot s-1)/3} \equiv 1 \pmod N$.
Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.


Actually, we have $r \cdot s - 1 = a / b \cdot \lambda(N)$, where $\lambda(N) = \text{lcm}(p-1, q-1)$, and $b$ is likely to be small if $g$ was chosen randomly (example what can happen if $g$ is not chosen randomly, consider $g=h=r=s=1$).

With that, here is a randomized procedure that will find the factorization of $n$ with decent probability if $b$ is not too large:


Compute $z \cdot 2^{\ell}= r \cdot s - 1$ with $z$ odd
Select a random value $u$ and compute $v = u^z \bmod n$; if $v = 1$ or $v = n-1$, this iteration fails to find the factors; try again with another value of $u$
For $\ell$ times,


Compute $w = v^2 \bmod n$.
If $w = 1$, then this iteration succeeds, the factors are $\gcd( v-1, n)$ and $\gcd(v + 1, n)$
If $w = n-1$, then this iteration fails, try again with another value of $u$
Set $v := w$



If we went through $\ell$ loops without hitting 1 or $n-1$, this iteration fails to find the factors, try again with another value of $u$.