What is a primitive point on an elliptic curve?

While working with elliptic curves for cryptography reasons, I found the notion of a primitive point, but no definition.
For example, $P(0,6)$ is a primitive point on the elliptic curve $y^2\equiv x^3+2x+2 \mod 17$. What does that mean? How can I tell if a point is primitive or not?

• It seems to mean that the point generates the group. I guess there are algorithms for checking this. – Qiaochu Yuan Feb 9 '11 at 16:40

The points on an elliptic curve (plus a 'point at infinity') form a group under a certain addition law, explained in this Wikipedia article. (You probably know this already.) A primitive point $P$ is simply a generator of this group: all elements of the group can be expressed as $P+P+...+P$ ($k$ times) for some $k$. If the elliptic curve has a prime number of points, then all its points (except the point at infinity) are primitive; but in general, the elliptic curve may or may not have a primitive point.

• I have a question from Tonyk... you mentioned that "If the elliptic curve has a prime number of points, then all its points (except the point at infinity) are primitive;" Can anyone give a reason why is that so. I mean what difference does it make if the order of the group is a prime number? thanks – user9462 Apr 11 '11 at 22:36
• Because a point on the curve always generates a subgroup of the full elliptic curve group - just think of P, (-P), P+P, etc. with the obvious group structure; it's easy enough to see that this is a subgroup. (Indeed, this is true for any group, not just for elliptic curves). The order of a subgroup divides the order of a group, so if the order of the group is prime then any subgroups are either trivial or the full group. – Steven Stadnicki Apr 11 '11 at 22:54
• How can you find the primitive point of a curve? – curious Dec 3 '13 at 15:16
• @curious This might be a good, separate question (rather than a comment). – Niels Abildgaard May 12 '14 at 17:52

Yes, primitive point means the group is cyclic and that P is a generator.

Let E be an elliptic curve over a finite field F_q. The group E( F_q ) is cyclic if gcd( #E( F_q ), q-1 ) = 1. To test whether a point P generates E( F_q ) it is necessary to factorise #E( F_q ). The case when #E( F_q ) is prime is an easy special case.

If M = gcd( #E( F_q ), q-1 ) > 1 then one can determine whether E( F_q ) is cyclic or not (both cases can arise) in expected (randomised) polynomial time using the Weil pairing. This algorithm is due to Victor Miller and is explained in his paper in the Journal of Cryptology, volume 17 (2004).

• PS. I should have said: non-cyclic elliptic curve group structures can only arise if there is a prime dividing gcd( #E( F_q ), q-1 ) whose square divides #E( F_q ). – user7095 Feb 15 '11 at 1:13