6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It would be helpful if you said what books or articles you are reading, and what mathematical background (esp. in number theory) is already known. $\endgroup$ – hardmath Jul 14 '14 at 11:53
  • $\begingroup$ Primitive point or generator point of what? The Poincare group isn't usually cyclic. $\endgroup$ – Timbuc Jul 14 '14 at 12:03
  • 1
    $\begingroup$ @Timbuc: Although the elliptic curve may not always give us a cyclic group, the cases when it does are important in cryptography. See this related (but not duplicative) Question. $\endgroup$ – hardmath Jul 14 '14 at 13:46
  • 2
    $\begingroup$ @hardmath I was reading a book called understanding cryptography by christof paar it consisted of an example that had an elliptic curve E : y^2 ≡ x^3 + 2x + 2 mod 17 and primitive pt (5,1) but no explination how they got this point.So my question is do we have to brute force all points that satisfy this curve and then look for cyclic group's or something else??? $\endgroup$ – uSeemSurprised Jul 14 '14 at 15:14
  • $\begingroup$ @u_seem_surprised: I think there is typically a certain amount of brute force involved in searching for a primitive point, although one can "cherry pick" the elliptic curve $E$ and prime modulus $p$ over which to reduce it, to make things easy. The general difficulty of doing so seems to be the key ingredient that make cryptography attractive in this setting, similar to the difficulty of cracking public key cryptography hinging on finding a generator in $\mathbb{Z}_{pq}$ when the distinct primes $p,q$ are known only by their product. I'll try to put up an Answer for you. $\endgroup$ – hardmath Jul 14 '14 at 23:06
9
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ You wrote "While E(Fp) is not necessarily cyclic, it can always be generated by two elements". Assuming these "elements" you refer to are cyclic groups, so does that mean that an elliptic curve always has a cyclic group , but in your earlier comment you said that "elliptic curve may not always give us a cyclic group" please clarify am I missing something here or mixing up some concepts?? $\endgroup$ – uSeemSurprised Jul 16 '14 at 8:17
  • $\begingroup$ The elements I refer to are group elements, points on the curve or the point at infinity. I meant that the full group defined by the elliptic curve reduced over a prime may not be cyclic; it may require two generators rather than just one (cyclic group = one generator). We talk above about two cyclic subgroups into which the full group is decomposed as a direct product. This requires, not that these two subgroups are disjoint (that never happens), but that their intersection is the trivial subgroup $\{\mathcal{O}\}$. $\endgroup$ – hardmath Jul 16 '14 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.