# Given $g,g^t$ in an RSA group modulo $N=pq$, is it hard to compute $g^{t^{-1}}$?

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.

• 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. Dec 2 '15 at 23:14
• 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). Dec 3 '15 at 11:32
• 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. May 11 '20 at 19:09
• 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. May 11 '20 at 19:16

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.