Breaking RSA (small e)

As far as I know, $e = 3$ is not demonstrably unsafe in general. But if your message $m$ happens to be smaller than $n^{1/e}$ , then $m^e$ will be less than $n$ , so $c$ will actually equal $m^e$ and we can just recover $m$ by taking $m = c^{1/e}$ . This is what happens in this case: $(309717089812744704)^{1/3} = 676584$ , or "cat."

There might be a problem with this question: $\gcd(\phi(n),\:e)=3\neq 1$ , so $e$ could not have been chosen as the second part of the public key: $\begin{aligned} n&=pq,&p&=726,455,342,971,&q&=9,450,896,075,377&&&\Rightarrow &&&&\phi(n)&\equiv (p-1)(q-1)\equiv (p-1)\cdot 0\equiv 0\mod 3 \end{aligned}$ The problem is there are now multiple messages $m$ Alice could have encoded that all lead to the same codeword $c$ . Another one is $\begin{aligned} m&=5,470,551,817,239,310,886,953,747,&&&m^e&\equiv c\mod n \end{aligned}$