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?
What is a primitive point on an elliptic curve?
-
2It seems to mean that the point generates the group. I guess there are algorithms for checking this. – 2011-02-09
2 Answers
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.
-
0@curious This might be a good, separate question (rather than a comment). – 2014-05-12
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).
-
0PS. 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 ). – 2011-02-15