Suppose
\begin{align*} g^r &\equiv h \pmod N, \\ h^s &\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$.
