RSA: Probalistic algorithm to compute $x$ from $y$ and $(n,e)$ with probability $\epsilon>0$ given set of weak ciphertexts?
Let $d_k$ denote decryption and $x = d_K(y)$. I further assume that $\epsilon &lt; 1$.
First note that $A_1$ calculates a randomly chosen cipher text $y$ with probability $\epsilon$.
But the task is to construct a probabilistic algorithm $A_2$ which decrypts a fixed cipher text $y$.
Therefore, proceed as follows:  


choose a random $r \in Z^*_n$
calculate $y' = y* e_K(r)$ 
Use $A_1$ to decrypt $y'$ to $x'$ 
calculate $x = r^{-1}*x'$


This algorithm calculates the decryption of $y$ with probability $\epsilon$:
 - In step 2, $y'$ lands with probability $\epsilon$ in $S$
 - In step 3, the calculation yields
$$x'= d_k(y') = d_k(y*e_K(r)) = d_K(y)*d_K(e_K(r)) = d_K(y)*r = x*r$$