How to find p,q in this problem?

Question

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

1. 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.

2. How can I factorize N?

Note. In this case, we also have $g^{(r\cdot s-1)/3} \equiv 1 \pmod N$.

Answer 1

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