What makes RSA secure by using prime numbers? I am just learning about the RSA algorithm. Looking at the first two steps:


Choose two distinct prime numbers $p$ and $q$.
Compute $n = pq$. 


I have some probably stupid questions:


Why do $p$ and $q$ have to be prime numbers? Why couldn't they be any integers or odd integers? Or does that break the whole algorithm?
Because prime numbers are rare in comparison to regular integers, does restricting the algorithm to only prime numbers reduce security? It would seem easier to find the private key if an attacker knows it's only going to be some prime number?
In order to generate a RSA key pair, you are to find a public exponent $e$ and a private exponent $d$ such that, for all $m \in \mathbb Z_n^*$, i.e. $m$ is relatively prime to $n$, $(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if $e, d$ satisfy the equation $ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent pair. 

The fundamental theorem of arithmetic says that every integer has a factorization into powers of prime numbers that is unique to the integer, save for the order of the factors. 

The definition of Euler's $\phi$ function is that $\phi(n)$ equals the number of integers less than $n$ and relatively prime to $n$. In order to determine this number, you have to know the factorization of $n$.

Consequently, if you select a number $n = pq$ where $p, q$ are both prime, you will have selected a number you can factor, but, if it is large enough, no one else can factor. The reason for this is because, using known factorization algorithms for arbitrary integers, the running time of such algorithms depends on the relative size of the second largest prime factor of the input. This means that given the public exponent $e$ only you can determine the private exponent $d$.

(Note: The hardness of performing the RSA private key operation $m \equiv c^d \mod n$ given only the public key $e, n$ as above, is known as the RSA problem, which hasn't been proved to be as hard as factoring the modulus. The best known method is however by factoring the modulus $n$ in order to determine $d$ given $e$.)

It also means that if you were to select $p, q$ just as odd integers, you would make it harder for yourself to find $\phi(n)$, while at the same time decreasing the relative size of the second largest prime factor, and thereby making it easier for everyone else to factor $n$. In fact, it would be as hard for you to factor $n$ as it would be for everyone else, so you would completely loose the trapdoor component of your scheme (if not making it completely infeasible to find a pair $e, d$).

Regarding your second question, for large $x$, the number of primes less than $x$ equals $\pi(x) \approx \frac x {log(x)}$. Hence, the number of primes roughly equal to $\sqrt n$ is, for large $n = pq$, large enough to make factorization algorithms faster than a brute force search. Besides, by the arithmetic theorem above, the adversary is really only interested in prime numbers anyway, so the question is moot.