0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @byks: then try it with $z = rs - 1$ and $\ell = 3$ (say); that should work... $\endgroup$ – poncho Jul 14 '18 at 3:46
  • $\begingroup$ While I am editing the comment, you've got an answer. understand. Thank you. (Previous comment: What if rs-1 is even?) $\endgroup$ – user60208 Jul 14 '18 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy