How to find primitive point on an elliptic curve?

Question

Reading about Elliptic curve cryptography, i came across primitive point's or generator point's but found nothing on how to generate such points any help would be appriciated.

Answer 1

The problems of determining if a group given by reduction of an elliptic curve over a prime $p$ is cyclic, and if so, finding a point $P$ that generates (a "primitive point"), have been extensively investigated. An obvious "brute force" strategy would set a coordinate to successive values $0,1,\ldots,p-1$ and check if the number of points on the reduced elliptic curve matches the order of some point found in this way. This method gives an $O(mp)$ order of complexity, where $m$ is group order.

The literature shows that the first order dependence on $p$ in searching for primitive points can be lowered to a deterministic $O(p^{0.5+\epsilon})$. To discuss the algorithms involved we first recap the framework in which these computations are carried out.

---

Let $E$ be an elliptic curve given by an equation in "Weierstrass form":

$$ y^2 = x^3 + Ax + B \text{ where } A,B \in \mathbb{Z} $$

The rational points on this curve, together with a "point at infinity" $\mathcal{O}$ where all vertical lines intersect, form a geometrically defined abelian group. That is, a straight line through any two rational points on the curve should intersect the curve in a third point, and with a bit of algebraic reasoning (using the integer coefficients of the equation), it is deduced that this third point is also rational. The result of the group operation on the first two points is given by reflecting the third point in the $x$-axis (about which the curve above is symmetric).

By a slight abuse of notation we will refer to this group as $E(\mathbb{Q})$, also taking this to mean the rational points on $E$ together with point $\mathcal{O}$, which works out to be the identity element for this abelian group. There is a famous result, the Mordell-Weil theorem, which says this group is finitely generated. That is:

$$ E(\mathbb{Q}) = E(\mathbb{Q})_{tors} \times \mathbb{Z} \times \mathbb{Z} \ldots \times \mathbb{Z} $$

where the first factor, the torsion subgroup $E(\mathbb{Q})_{tors}$, consists of all the group elements of finite order in $E(\mathbb{Q})$, and the number $r$ of the remaining torsion-free factors (copies of $\mathbb{Z}$) is the rank of $E(\mathbb{Q})$.

---

A similar construction can be carried out using coordinates from prime field $\mathbb{F}_p$. We consider this here only for odd primes $p$ that do not divide the discriminant $\Delta$ of the cubic:

$$ \Delta = -16(4A^3 + 27B^2) $$

Such primes give "good reduction" in that any rational point $P=(x,y)$ on $E$ can be mapped to a point $\tilde{P} = (\tilde{x},\tilde{y}) \in \mathbb{F}_p \times \mathbb{F}_p$ when neither $x,y$ has least denominator divisible by $p$, or to $\mathcal{O}$ otherwise (as then both $x,y$ must have least denominator divisible by $p$. This "reduction modulo $p$" gives a well-defined group homomorphism $E(\mathbb{Q}) \to \tilde{E}(\mathbb{F}_p)$, the details of which verification are touched upon in this 2003 writeup by M. Woodbury. This homomorphism need not be surjective.

While $\tilde{E}(\mathbb{F}_p)$ is not necessarily cyclic, it can always be generated by two elements! This perhaps addresses u_seem_surprised's Comment that asks about the possibility of "more than 1 cyclic group". In any case there are generators $P,Q$ with $M=|P|$ a multiple of $L=|Q|$ so that:

$$ \tilde{E}(\mathbb{F}_p) \cong \mathbb{Z}/M \times \mathbb{Z}/L $$

whose order is $N=ML$, and the exponent of this group is $M$.

---

Let's take the example mentioned in the Comments on the Question, the reduction of:

$$ y^2 = x^3 + 2x + 2 \;\; \text{ over } \;\; \mathbb{Z}/17 $$

and take the "brute force" path, informed by the material above.

The points on the reduced elliptic curve are $(x,\pm y)$ where $x$ gives a right hand side value that is a quadratic residue (and $y$ a corresponding square root), as well as $\mathcal{O}$, the "point at infinity". The set of quadratic residues mod $17$ can be found by simply squaring $0,1,\ldots,8$ mod $17$, or if one feels more energetic by using the law of quadratic reciprocity, or by Googling it if one feels less energetic. With those in hand, I built a quick spreadsheet to evaluate the cubic $x^3 + 2x + 2$ at $x=0,1,\ldots,16$ mod $17$. Checking these results against the list of quadratic residues and their roots gives these $19$ points:

$$ (0,\pm 6), (3,\pm 1), (5,\pm 1), (6,\pm 3), (7,\pm 6), (9,\pm 1), (10,\pm 6), (13,\pm 7), (16,\pm 4), \mathcal{O} $$

Since the prime order $19=ML$ factors with $L|M$ only for $M=19,L=1$, all the points except $\mathcal{O}$ are primitive (i.e. each has order $19$ except the identity). So $(5,1)$ is a primitive point (but so are most of them).

This previous Math.SE Question asks how to tell if the same curve $E$ reduced over the same prime $p=17$ has as primitive point $(0,6)$ instead of $(5,1)$, which of course we know it does. Another Math.SE Question asks about determining cyclicity for same curve $E$ reduced over a different prime, $p=11$. With nine points on the curve, it requires some checking of points to see if any have order $9$ (because this is no longer a prime order). But such a primitive point is found, so the group is cyclic.

Finally an example of an elliptic curve giving a non-cyclic group is in Silverman's tutorial, about a third of the way through (page numbered 29). Take the curve $y^2 = x^3 - 5x + 8$ reduced over prime $p=37$. Plugging and chugging much as we did above, one finds 45 points (including $\mathcal{O}$). Checking how many points there are whose orders divide $3$ (there are nine), it is shown that the group is $\mathbb{Z}/15 \times \mathbb{Z}/3$ rather than the cyclic group $\mathbb{Z}/45$.

---

Reading List

I realize the OP does not wish to be sent off with a long reading assignment, but I'd like to give a plug for a book and a few papers:

• Silverman, J.H. and John Tate, Rational points on elliptic curves. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1992.
• Silverman, J.H. An Introduction to the Theory of Elliptic Curves. Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, 2006. 89 pp.
• Kohel, D.R. and Igor E. Shparlinski, On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields. Proc. Algorithmic Number Theory Symposium, Leiden, 2000, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2000, v.1838, 395-404.