2048-bit RSA Decryption If a message is encoded with 2048 bit RSA. The ciphertext is $M^e mod N$. In some cases, the message is short, $ M \approx 10^{20} $. With a high probability, $M$ can be written as $M = ab$ with $a, b \leq 4\sqrt{M}$. 

Can you explain to me how I can find the initial message $M$ given $N, e,$ and the ciphertext using a computation with no more than $\approx$ $4*10^{20}$ total operations?

I heard that there was some relation between small a's and b's and being able to do a trick.
So if $M \approx 10^{20}$, and you have $4 * 10^{20}$ operations, why not just bruteforce it?

For more efficient solution, consider meet-in-the-middle technique. For all $1 \le a \le 4\sqrt{M} \approx 10^{20}$, make a hash table with values $a^e \mod{N}$. Then for all $1 \le b \le 4\sqrt{M} \approx 10^{20}$ check if $M^e/b^e \mod{N}$ is in the table.

Indeed, $M^e / b^e \equiv (ab)^e / b^e \equiv a^e \pmod{N}$ so it should be in the table (of course b must be invertible, otherwise it contains a factor of N and you can simply factorize N).

So total number of operations is $\approx 8\sqrt{M}$.