0
$\begingroup$

I have a question from Stinson: 7.14. The question states:

Suppose that $p > 3$ is an odd prime, and $a,b$ is an element of $\mathbb Z_p$. Further, suppose that the equation $x^3 + ax + b$ is congruent to $0$ ($\mod p$) has 3 distinct roots in $\mathbb Z_p$. Prove that the corresponding elliptic curve group $(E, +)$ is not cyclic. Hint: Show that the points of order two generate a subgroup of $(E, +)$ that is isomorphic to $\mathbb Z_2 \times\mathbb Z_2$.

I've read through the elliptic curve material in the chapter preceding this question but I'm still a little hopeless. Can anyone explain or push me in the right direction on how to show/answer this?

I understand that points of order two (from the hint) follow the formula: $[2]P = \mathcal{O}$ but I'm not sure how this relates.

$\endgroup$
3
$\begingroup$

Can anyone explain or push me in the right direction on how to show/answer this?

The first obvious thing to ponder is "what does it mean that a 'group is cyclic'? What properties does a cyclic group have, that noncyclic groups do not?"

(Broader hint: a cyclic group has a generator; noncyclic (finite) groups do not)

I understand that points of order two (from the hint) follow the formula: 2P = 0 but I'm not sure how this relates.

It relates quite a bit, actually. Can a cyclic group have two different elements of order 2?


Update: since Dexter has solved the problem, I'll lay out the proof I was originally trying to suggest.

One fundamental property of all finite groups is that, if $n$ is the number of group elements, we have $xP = (x \bmod n)P$ (for any integer $x$ and any element $P$).

In addition, a finite group is cyclic if it has a generator, that is, an element $G$ for which all elements can be expressed as $xG$ (for some $x$). In addition, for any $P$, we always have $xG = P$ for some $0 \le x < n$. In particular, $xG \ne 0$ for any $0 < x < n$.

Now, for the group in question, we have two distinct elements $P_1$ and $P_2$, both of order two (actually, we have three, we only need two). That is, $P_1 \ne P_2 \ne 0$, and $2P_1 = 2P_2 = 0$.

Now, suppose the group is cyclic; if so, we have a generator $G$. We know $P_1$ can be expressed as $P_1 = x_1G$ for some $0 \le x_1 < n$. We also have $2P_1 = 0$, that is, $2 (x_1 G) = (2 x_1)G = 0$. We know that $(2x_1)G = (2x_1 \bmod n)G$, and if that is the neutral element, we must have $2x_1 \bmod n = 0$. The only value $0 < x_1 < n$ that can satisfy that is $x_1 = n/2$ (which implies that $n$ must be even).

However, by the same reasoning, if we have $P_2 = x_2G$, we have $x_2 = n/2$, but that would mean that $P_1 = (n/2)G = P_2$, and so the two points of order two were the same, but we know they aren't.

Hence, there cannot be a generator, and hence the group cannot be cyclic.

This proof may sound a bit lengthy, however, that's mostly because I spelled out the logic quite explicitly, listing the various assumed properties of groups. Once you get more acquainted with group theory, this logic would be more natural.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So a group is cyclic if it contains an element that, when raised to powers, calculates all of the other elements of that group... So I have to show that the group (E, +) is not cyclic by showing it has no generators? $\endgroup$ – Dexter Mar 24 at 21:25
  • $\begingroup$ @Dexter: that would work - how could you use the existence of two elements of order two to show that there cannot be a generator? $\endgroup$ – poncho Mar 24 at 21:26
  • $\begingroup$ What is the group (E, +)? $\endgroup$ – Dexter Mar 24 at 21:26
  • $\begingroup$ Well I think that if two elements have both order two, would they have to equal because they both equal 0? Suppose 2P = 0 and 2Q = 0, that means 2P = 2Q => P = Q, but this can't be true correct? $\endgroup$ – Dexter Mar 24 at 21:33
  • $\begingroup$ The question says that the elliptic curve is mod p, which is an odd prime. If this is true, then the possible cycle length of generators is either 1 or of length p... Wouldn't this prove that the group is cyclic instead of not cyclic? $\endgroup$ – Dexter Mar 24 at 21:35

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.