I am trying to solve the following problem:
Alice generates a RSA key $(n, \phi)$, she shares with Bob the value $n$, and $y = g^{2^{t}}\;\text{mod}\; n$ for $g$ a generator of the group $\left(\mathbb Z/n\mathbb Z\right)^{*}$ and $t$ a very large number for example $2^{512}$. She then asks Bob for an input $z$ ($\neq y$) and sends him a relatively small random prime (challenge) $\ell$ and $\pi$ a proof of $y$ such that $$\pi = g^{\left\lfloor\frac{2^t}{\ell}\right\rfloor}\;\text{mod}\; n$$ and so $$y = \pi^{\ell} g^r\; \text{mod} \; n$$ where $r = 2^t \; \text{mod}\; \ell$. Now Bob needs to find a proof $\psi$ for $z$ such that: $$z = \psi^{\ell} g^r\; \text{mod} \; n.$$
It is clear that if Bob has an access to $\phi$ he can find $d = \ell^{-1}\;\text{mod}\; \phi$ and solve the problem by chosing $\psi = \left(z g^r\right)^d \;\text{mod}\; n$. However in my case $n$ is large that it is almost impossible for me to compute the prime factorization of $n$ to find $\phi$. Can any one help me to find an idea of how to find $\psi$?
