In the perspective of RSA, given small encryption exponent e (e.g., e = 216 + 1), the top half of the decryption exponent d can be narrowed down within a small search space. This fact has been previously exploited in RSA cryptanalysis. On the contrary, here we propose certain schemes to exploit this fact towards efficient RSA decryption. © 2010 Springer-Verlag.