Let $E$ be an elliptic curve defined over a finite field $F(q)$. Let $G\in E(F(q))$ be a point of order $n$, where $n$ is a prime number and $n>2^{160}$.
The elliptic curve discrete logarithm problem (ECDLP) is the following: given $E, G, Q \in E(F(q))$, determine the integer $l$, $0 \le l \le n-1$, such that $Q = lG$, is computationaly difficult.
My question is:
Why must $n$, the order of basepoint of this elliptic curve, be prime?
On
The short answer is that it doesn't have to be a prime, and for most elliptic curves (in a suitable sense of "most") and for most choices $G$ $n$ is not a prime.
However, for practical EC-cryptosystems we design the curve, and select the point $G$ in such a way that the group generated by $G$ is of prime order. Often it then also happens that the group generated by $G$ consists of all the $F(q)$-rational points. This latter requirement is not necessary, but having it means that we are in a way using the elliptic curve very efficiently, we don't have to constrain our selves to a subset of the available points.
The former property that we prefer groups of prime order comes from the fact that such elliptic curves tend to be safer. If $n$ were a product of small prime powers, we could relatively easily solve the DLP problem on that curve with the aid of easy to generate smallish look-up-tables and the Chinese Remainder Theorem. For the the curve to be safe, it is not sufficient that $n$ is a prime, but it helps for this reason (and may be deemed necessary).
So to summarize: these properties do not hold for all elliptic curves. But they do hold for those curves that are recommended for cryptographi standards.
Because, if $n$ is not a prime, then there may not exist such an $l$.
To understand this, consider the following simpler situation. Consider the finite group $\mathbb Z/n\mathbb Z$ where $n$ is a prime number. Let $j, k$ be integers such that their congruence classes modulo $n$ are nonzero. Then, if $n$ is a prime number, there always exists an $l$ such that $lj \equiv k\ (\textrm{mod}\ n)$. This is a basic fact and easily follows from Langrange's theorem in group theory. Also for each composite number $n$, you can construct examples of $j,k$ that don't satisfy such an equation.
So $n$ being a prime number makes the situation neater and also contributes to computational complexity -- the composite case can be reduced further depending on prime factorization, which simplification is not possible for numbers which are already primes.