Suppose we have an RSA groug $G=\mathbb{Z}^{*}_{N}$, where $N=pq$ , where $p,q$ are primes. Let $g$ be a random element of $G$ and $t\in \mathbb{Z}^{*}_{N}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$, supposing discrete logarithm problem (DLP) is hard. My question is that is this really hard?

In a prime order group, let's say in $\mathbb{Z}^{*}_p$ , $g^{t^{-1}}$ = $g^{p-2}$ : here we don`t have to face DLP, so finding $g^{t^{-1}}$ is easy.

  • 2
    $\begingroup$ Actually, in a prime order group, computing $g^{t^{-1}}$ is known to be equivalent to the computational Diffie-Hellman problem; that is believed to be a hard problem in some prime-order groups. $\endgroup$
    – poncho
    Commented Dec 2, 2015 at 23:14
  • $\begingroup$ Just adding a reference to @poncho: citeseerx.ist.psu.edu/viewdoc/…. However, it appears to me that the reduction works in prime-order groups where all values are generators (except for the unity). It doesn't appear to work otherwise (unless you can show that a non-negligible number are generators). $\endgroup$ Commented Dec 3, 2015 at 11:32
  • $\begingroup$ Multiplication modulo an RSA number is not a group, because multiples of $p$ and $q$ are not invertible mod $N$. RSA numbers instead form a ring. $\endgroup$
    – Myria
    Commented May 11, 2020 at 19:09
  • $\begingroup$ Also, isn't this question equivalent to the RSA problem? If $t^{-1}$ exists mod $\phi(n)$, then $t$ is an RSA public exponent and $t^{-1}$ is its matching private exponent. $\endgroup$
    – Myria
    Commented May 11, 2020 at 19:16

1 Answer 1


I know that I am not exactly answering your question, but I am pointing you in a potentially interesting research direction. Your question is not standard in the area of discrete log and Diffie-Hellman problems since you are considering a cyclic group of order $p\cdot q$ where $p$ and $q$ are primes. (Typically, we like looking at group of prime order.)

Your question is actually asking whether you can reduce this problem to solving the discrete log problem. I don't have any answer to that, but it reminds of an old paper by Biham, Boneh and Reingold that shows that the Diffie-Hellman problem modulo $N=pq$ (for Blum integers) is actually equivalent to factoring. This isn't the same thing, but there's something similar. The paper is here: https://omereingold.files.wordpress.com/2014/10/cgdh.pdf.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.