Suppose that Bob discovers a polynomial-time algorithm that, given
Ea(M) for any (possible random) M, has a 1% probability of returning
"Success: M" and a 99% probability of returning "Sorry, I failed to
break it for this input". (The same input produces the same output,
i.e, if the algorithm fails to obtain M for a particular Ea(M) then it
will fail again if given that same Ea(M) as input.) Here Ea(M) denotes
encryption of M with Alice's public key in a cryptosystem that has the
multiplicative property, i.e.,
Ea(M*R) = Ea(M) * Ea(R).

Explain how Bob can use this algorithm to consturct another algorithm
that runs in polynomial time with extremely high probability (close to
1) and, when it terminates, it always obtains M from Ea(M).

Well, find some Ea(R) for which you know R - after a few tries with
Bob's algorithm you should find one.

Now, for a given Ea(M), try the algorithm, if you find M - done.
Otherwise, try Ea(M*R), which is just Ea(M)*Ea(R). Now if you find
M*R, you can figure M from it, since you already know R. Still no
luck?
Next try Ea(M*R*R), which is ... and so on.
The probability for not finding a solution after n tries is
exp(0.99,n), so by setting n to the desired probability you still get
a polynomial algorithm (it is just the original one times a constant
[i.e. n]).

Enjoy.