Cryptography RSA system I everyone, 
I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$
of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.
I assume that $H=\{x^4|x\in G\}$ is a subgroup of $G$.
Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?
by using Lagrange I have concluded that $|H|/|G|=\frac{1}{16}$.
But how can I interpretate anything from that? 
 A: An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.


*

*Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.

*If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $c\ell^{-e}$, $\ell\in D$ will be in the subgroup $H$. This is because $xH=\ell H$
for one $\ell\in D$ (as per the wishful assumption).

*So for each candidate $\ell\in D$ we try the algorithm $A$ with the input $c\ell^{-e}$. If successful we move to step 4. Otherwise try another $\ell$.

*If $x$ is the plaintext corresponding to $c\ell^{-e}$. Then $x'=x\ell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.



I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $\ell\equiv1\pmod4$ such that $\left(\dfrac n\ell\right)=-1$. Then either $\left(\dfrac p\ell\right)=-1$ or $\left(\dfrac q\ell\right)=-1$ and, by quadratic reciprocity, either $\left(\dfrac \ell p\right)=-1$ or $\left(\dfrac \ell q\right)=-1$. If we find enough such primes $\ell_i, i=1,2,\ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $\prod_{j=1}^m\ell_j^{a_j}, 0\le a_j<4$ can serve in the role of $D$.

An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $\ell$ in step 3.
