Hints:
- Your calculation of $6(5,1) = (16,13)$ is correct.
- Your calculation of $6(0,6) = (0,11)$ is incorrect, you should get $6(0,6) = (3,1)$.
Maybe if you show how you did that calculation, I can spot the issue.
Once you fix that, I verified the author's result is correct, that is:
$$(16,13)+(3,1) = (7,11)$$
Update
Here are some additional hints to help you with intermediate calculations:
- $P = (0,6)$
- $2P = (9,1)$
- $3P = (6,3)$
- $4P = (7,6)$
Fix an elliptic curve $E/\Bbb F_q$, where $\Bbb F_q$ is the finite field with $q$ elements. Then the set of points $E(\Bbb F_q)$ form a group, and because $\Bbb F_q$ is finite, $\# E(\Bbb F_q) = n$ is finite. Then
$$
E(\Bbb F_q)\subseteq E[n](\overline{\Bbb F}_q)
$$
($E[n](\overline{\Bbb F}_q)$ denotes the set of $n$-torsion points of the elliptic curve in an algebraic closure of $\Bbb F_q$). This follows from Lagrange's theorem, as $E(\Bbb F_q)\subseteq E(\overline{\Bbb F}_q)$ is a subgroup. However, the structure of $E[n](\overline{\Bbb F}_q)$ is well known. For simplicity, let us assume that $n$ and $q$ are relatively prime. Then
$$
E[n](\overline{\Bbb F}_q)\cong\Bbb Z/n\Bbb Z\times\Bbb Z/n\Bbb Z.
$$
Using this, we get the following more precise version of what you stated:
Theorem: Let $E/\Bbb F_q$ be an elliptic curve, and suppose that $\#E(\Bbb F_q) = n$ is relatively prime to $q$. Then $E(\Bbb F_q)$ is either cyclic or isomorphic to the direct product of two cyclic groups.
In fact, one can even remove the hypothesis that $\#E(\Bbb F_q) = n$ is relatively prime to $q$ above. Of course, you wanted to know when this group is in fact cyclic. I don't know a complete classification, but this will at least provide you with some specific cases in which the group is cyclic.
Theorem: Let $E/\Bbb F_q$ be an elliptic curve, with $q = p^r$ for some prime $p$. Then $E(\Bbb F_q)$ is cyclic if one of the following conditions hold:
$\# E(\Bbb F_q) = p^k$ for some integer $k$. (This is because $\# E[p^k](\overline{\Bbb F_q})$ is either trivial or isomorphic to $\Bbb Z/p^k\Bbb Z$, unlike when you look at $n$-torsion for $n$ prime to the characteristic of the field.)
$E/\Bbb F_q$ is supersingular and $q = p\geq 5$ is prime with $q\equiv 1\pmod{4}$. (This is an exercise in Silverman's "The Arithmetic of Elliptic Curves.")
As for the importance of the cardinality, there are certain types of curves which are particularly vulnerable to attack:
- Curves over $\Bbb F_{2^m}$ with $m$ composite are vulnerable to Weil descent attacks.
- Curves such that $n$ divides $p^{B}-1$ (where $p$ is the characteristic of the field your curve lives over) for sufficiently small $B$ are vulnerable to Menezes–Okamoto–Vanstone (MOV) attack which applies usual Discrete Logarithm Problem (DLP) in a small degree extension field of $\mathbb {F} _{p}$ to solve the ECDLP. The bound $B$ should be chosen so that discrete logarithms in the field $\mathbb {F} _{p^{B}}$ are at least as difficult to compute as discrete logs on the elliptic curve $E(\mathbb {F} _{q})$.
- Curves such that $\#E(\mathbb {F} _{q}) = q$ are vulnerable to the attack that maps the points on the curve to the additive group of $\mathbb {F} _{q}$.
As you can see, the last condition is a condition on the cardinality of $E(\Bbb F_q)$ (which in this case would be cyclic as I noted above, so it's both the cardinality of the group of points and the cyclic group in question). In general, one needs to know the cardinality of both $E(\Bbb F_q)$ and the cyclic subgroup you use, so I think you can assume that both cardinalities are important.
(Note: I'm not an expert in elliptic curve cryptography, and I'm stealing this information from the Wiki page on ECC. I suggest reading that page and the relevant sources for more information on this topic.)
Best Answer
The rational points on an elliptic curve with rational coefficients form an Abelian group. A theorem of Mordell proves that this group is finitely generated. Thus it is isomorphic to $T\times\Bbb Z^r$ where $T$ is a finite group (the torsion subgroup) and $r$ is a non-negative integer, the rank. So $r$ is positive iff the curve has infinitely many rational points.