How is the order of a point calculated for elliptic curves over GF(p)

Question

My question is about elliptic curves over $GF(p)$: How is the order of a generating element $G$ (which is to my knowledge also the order of the cyclic subgroup $G^n$) calculated? Taking P-256 as an example, I know basically what the base point $G$ is and also what its order is.

• But how is the order of any point calculated? The order is really a very big number and I think that its value was not found by brute force.
• Under what circumstances is the order of the subgroup $G^n$ the same as the order of the whole group (co-factor = 1) ?
• Why must the order always be prime?
• is each group for elliptic curves over $GF(p)$ group cyclic? In this case there is a generating point G (a base point) and all sub-groups are cyclically, too.
• How are "good" points found and what is the cryprtographic meaning of "good" ?

From group theory I just know, that the order of a subgroup divides the order of the complete group, which gives rise to the definition of the co-factor h, but that doesnt help.

The questions are not of practical interest, but I want to understand what I'm doing. The information I read so far seem to appear from nowhere. If the mathematical background, needed to answer those questions is not totally out of scope for a non-mathematician, where can I read about that?

Answer 1

The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. The complexity of this method is in order ${\log^4 p}$. Using SEA you can easily compute the order of group, then with binary multiplication method you can compute the order of arbitrary points. For the meaning of "good"(and another questions), you should read about attacks against elliptic curves.

For more details you can see "Guide to Elliptic Curve Cryptography, Darrel Hankerson, Alfred Menezes, Scott Vanstone" which is easy and complete book.