In textbook RSA with low public exponent, how big does a random message needs to be?
Related messages. If you have (the encryptions of) a pair of messages that differ by a known fixed difference, then the Franklin-Reiter related message attack can be used to recover both messages.  The running time of the attack is something like $O(e^2 n^2)$.  This does not apply if the messages are independent and there are no known relationships between them.

Coppersmith's theorem. Coppersmith's theorem might be relevant.  Roughly speaking, it says that if you have a monic polynomial $f(x)$ of degree e, then you can find all solutions to $f(x)=0 \pmod N$ satisfying $0 \le x &lt; X=N^{1/e}$ in polynomial time, using a lattice technique.  By defining $f(x)=x^e-C$, this can be used to recover $M$ if it is known that $M&lt;N^{1/e}$.  Therefore, it looks like this does not improve upon the trivial $e^{\textrm{th}}$ root extraction root method.  I don't know if the attack can be improved by continuing to use his lattice methods even for a larger value of $X$.

Square-root attack. There is also a meet-in-the-middle style attack whose running time is $O(2^{m/2})$.  If $e=3$ it will be dominated by other attacks, but it may be more relevant for larger values of $e$.  The meet-in-the-middle attack is described by Boneh et al. (see below); basically, we hope that $M$ can be written as $M=M_1 M_2$ where $M_1,M_2 \le 2^{m/2}$, and we try to find $M_1,M_2$.  To find them, we build a table of $C/M_1^e \bmod N$ for all candidate $M_1$ values, then for each candidate at $M_2$, we look up $M_2^e$ to see if it is present in the table.

This is described in Section 5 of the following paper:


Textbook ElGamal and RSA Encryption are Insecure, Dan Boneh, Antoine Joux, Phong Q. Nguyen, ASIACRYPT 2000.


Published work. A good summary of the above attacks can be found in this paper:


Twenty years of attacks on the RSA cryptosystem, Dan Boneh, Notices of the AMS, vol 46 no 2, pp.203-213, 1999.