Inverting RSA using an oracle Say you are given an efficient deterministic algorithm 'I' that can invert the RSA
function on 1% of the points in $Z^*_{N}$. That is to say that if y $ \in $ $Z^*_{N}$ is a "good" point for 'I', then
$(I(N, e, y))^e$ = y. (You don't know what these "good" points for 'I' are, however.) Show that you can use 'I' to build an algorithm 'A' that inverts the RSA function on any input, and that is fast on average. That is, if x $ \xleftarrow{$} Z^*_{N}$ and y $\xleftarrow{$} x^e$ mod N, then A(N, e, y) returns x. Give a description of your 'A', and explain why it is always correct and fast on average.
As a hint, consider using randomization and exploiting the multiplicative property of the RSA function.

My idea was to come up with an algorithm which picks $y_1$ and $y_2$, which when multiplied together get y and then proceed to invert both those points.

$y_1 \xleftarrow{$} Z^*_{N}-\lbrace{1,y\rbrace} $
$y_2 \xleftarrow{$} y.y^{-1} mod N $
$x_1 \leftarrow I(n, e, y_1) $
$x_2 \leftarrow I(n, e, y_2) $
$x \leftarrow x_1.x_2 $ mod N
Ret y, x

Now, x has to be the inverse of y because
$ x^e \equiv (x_1.x_2)^e \equiv x_1^e.x_2^e \equiv y_1.y_2 \equiv y $
But, the problem is the probability that I can successfully invert $y_1$ or $y_2$ is less than 1% with algorithm I(?). So, this algorithm probably fails in 99 out of 100 cases. Even if I repeat it until I get &quot;good&quot; set of points, it is going to be horribly slow. How do I solve this problem and make the new algorithm fast? And, how do I prove its fast?
This is homework, and so I won't give you the answer outright; I will give hints:

Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle?

Hint 2: how could you use the above observation to accelerate your algorithm?