Question about why RSA is hard to attack
There are a number of small mistakes in the question. Let's clean up that first.

$\gcd(e,n)=1$ is likely, but neither necessary nor sufficient for RSA to work; the right condition is $\gcd(e,p-1)=\gcd(e,q-1)=1$. Notice this implies $e$ odd for any non-trivial choice of $p$ and $q$.

Even in textbook RSA, the right equation is not $c\equiv m^e \bmod n$, but $c=m^e\bmod n$. The first can be understood as $c\equiv m^e \pmod n$, and only the second implies that $0\le c&lt;n$. The distinction is important: $c'=m^e$ satisfies the first, but (for most $m$) not the second, and would make RSA both unsafe and (except for small $e$ like $e=3$) extremely impractical as an encryption method.

Although that is not directly relevant to the questions, RSA as practiced is PKCS#1. A number of things change. The most important is that $m$ is not the message, but rather a randomized and reversible function of the message. Also, it is used $p≠q$, $1&lt;e&lt;n$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ where the question and the original RSA article uses $\phi(n)=(p-1)⋅(q-1)$, for determining the private exponent $d$ such that $e\cdot d\equiv1\pmod{\lambda(n)}$ and $1&lt;d&lt;n$.



Coming to the question about tactic 1:

An attacker Eve has the choice of means; she do not have to try a particular strategy, as in "in order to find $m$, we'd have to try all $k$'s in the natural numbers.."; she could try that strategy.

If she elected to follow the proposed strategy, try some $k$'s in the natural numbers and compute $m=(c+k\cdot n)^{1/e}$, she'd have a much better option than trying to guess if the resulting $m$ looks like a message; she can conclusively rule out a guess of $k$ when the resulting $m$ is not an integer, which occurs for the overwhelming majority of $k$. And also, she can decide if an integer $m$ in range $[0\dots n-1]$ is the right message by computing $m^e\bmod n$ and comparing that to $c$; they are equal if and only if she guessed the right $k$, and/or otherwise recovered $m$.

Tactic 1 is of course futile because they are too many $k$ to test.



Concerning tactic 2: the assertion is correct, for some loose use of "This is because"; exposing two methods to find $\phi(n)$ does not implies that they are the best ones, much less the only ones.

Notice that if an attacker Eve knew $\phi(n)=(p-1)\cdot(q-1)$, she's done: she can then compute an $f$ such that $f\cdot e\equiv 1\pmod{\phi(n)}$ and that let her decipher using that $m=c^f\bmod n$. Although her $f$ might not be the $d$ used by the legitimate key holder, which is any $d$ such that $d\equiv f\pmod{\lambda(n)}$, she does not care.



Attacking RSA encryption is believed hard when $n$ and $e$ have been properly chosen, and the message $m$ is a random integer in the set $[0\dots n-1]$, and all else that's known about $m$ is $c=m^e\bmod n$, because the best methods we have to solve that problem are of cost as high as factoring $n$, and the best general method known for that is GNFS, and the expected cost for that is prohibitive by definition of "$n$ has been properly chosen". This is circular, loose, and not a mathematical proof that RSA or factoring is hard. Neither is known with certainty. Notably, the definition of "$n$ has been properly chosen" has changed drastically since that original RSA article. That "RSA hard" implies "factoring hard" is obvious, but the converse is an open problem.