Order and cofactor of the base point? [duplicate]

Question

What is the order and cofactor of a base point? Is it possible to deduct the order and cofactor, given just the basepoint. What about the other way around from order and cofactor to basepoint?

Answer 1

What is the order and cofactor of a base point?

Put simply, the order of the basepoint is the number of points the basepoint generates under repeated addition. If you have point $G$ and you repeatedly add $G$ to itself, you will eventually get the identity element $O$ (where $O + G = G$). The order of $G$ is the smallest $n$ where $nG = O$.

The cofactor is the order of the entire group (number of points on the curve) divided by the order of the subgroup generated by your basepoint. Because of Lagrange's theorm, we know that the number of elements of every subgroup divides the order of the group.

Is it possible to deduct the order and cofactor, given just the basepoint. What about the other way around from order and cofactor to basepoint?

Not easily unless you know the order of the group.

There are algorithms for efficiently computing the order of an elliptic curve. After you know the order of the curve, you can factor it to find the size of its subgroups. Using the factors, you can test each one and find the order of any point.

Answer 2

I suggest you read up on some basic group theory (I recommend the book of Fraleigh).

Let $E$ be an elliptic curve over a (finite) field $K$, $E(K)$ is the group of points of $E$, $\left|E(K)\right|$ is the order of $E(K)$ (i.e., its cardinality). It can be computed in polynomial time (by the SEA algorithm), and for the curves occurring in practice, it can also be factored.

Let $P \in E(K)$ be a point of $E$. The set of multiples of $P$ (i.e., of all points $kP$) forms a subgroup of $E(K)$, which we note $\langle P\rangle$, and we let $r = \left|\langle P\rangle\right|$. $r$ is the order of $P$, and by Lagrange's theorem, $r$ is a divisor of $\left|E(K)\right|$, so we let $h = \frac{\left|E(K)\right|}{r}$. $h$ is the cofactor. $r$ can be computed efficiently (by iterating through the divisors of $\left|E(K)\right|$), and so $h$ can be computed as well.

In practice we often choose $r$ prime, so given a curve $E$ such that $\left|E(K)\right|$ is a multiple of $r$ it is easy to obtain a point of order $r$: choose a point $P$ at random until you find one such that $rP = \infty$ (and $P \ne \infty$ of course).