I am attempting to understand ElGamal Encryption on Elliptic Curves (beginnning of this paper)

I have an elliptic curve $E\left( \mathbb{F}_{11} \right)$ defined by $y^2 = x^3 + 2x + 3$

I need to choose a point $P$ on $E\left(\mathbb{F}_{11}\right)$ of prime order $n$

I haven't been able to find anything to help me understand what is meant by 'prime order $n$'. Can someone point me in the direction of anything useful or explain to me how to find such a point $P$ please?

I am a computer scientist, so assume limited knowledge of any complex maths/theorems - all my knowledge on elliptic curves is self-taught through Googling...

  • 1
    $\begingroup$ $E(\mathbb{F}_{11})$ is a finite abelian group whose elements are the points of the curve. $P$ has order $n$ means that $n$ is the least integer such that $\underbrace{P\oplus\ldots\oplus P}_n = 0$ where $0$ is the identity of the group. You have an example there $\endgroup$ – reuns Feb 13 '17 at 12:01
  • $\begingroup$ Thanks @user1952009, this makes sense - so saying it has prime order $n$ just means $n$ has to be prime in your definition, right? $\endgroup$ – lioness99a Feb 13 '17 at 12:37

You were already given a nice answer in comments, but lets add a little detail.

We find all of the points on the curve (Note that $O$ is the point at infinity)

$$(x, y) = O, (0, 5), (0, 6), (2, 2), (2, 9), (3, 5), (3, 6), (4, 3), (4, 8), (6, 0), (8, 5), (8, 6), (10, 0)$$

You can verify each of these by checking that

$$y^2 = x^3 + 2x + 3 \pmod{11}$$

If we take a point $P$ and write out $P, P+P, \ldots$, we get

  • $1P = (2, 2)$
  • $2P = (0, 5)$
  • $3P = (3, 5)$
  • $4P = (4, 3)$
  • $5P = (8, 6)$
  • $6P = (10, 0)$
  • $7P = (8, 5)$
  • $8P = (4, 8)$
  • $9P = (3, 6)$
  • $10P = (0, 6)$
  • $11P = (2, 9)$
  • $12P = O$

Compare this list of points with the list above. What do you notice? Every one of the points must be a point on the curve.

Next, how many points did we cycle through, which is the order?

This elliptic curve has order $\#E = |E| = 12$ since it contains $12$ points in its cyclic group.

There is a theorem called Hasse‘s Theorem: Given an elliptic curve module $p$, the number of points on the curve is denoted by $\#E$ and is bounded by $$p+1-2\sqrt{p} ≤ \#E ≤ p+1+2 \sqrt{p}$$

Interpretation: The number of points is close to the prime $p$.

  • $\begingroup$ Thanks, this makes sense, but if I choose $P=\left(4,3\right)$ then I get $\# E=3$ as $3P=\mathcal{O}$. What made you choose $P=\left(2,2\right)$? $\endgroup$ – lioness99a Feb 13 '17 at 15:13
  • $\begingroup$ I actually calculated all of them to see how many there were since the list of valid points was short. I chose one that had full period. Note there are algorithms to count the number of points on an EC: en.wikipedia.org/wiki/Counting_points_on_elliptic_curves. You might also want to read: math.stackexchange.com/questions/331329/… $\endgroup$ – Moo Feb 13 '17 at 15:53

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.