5
$\begingroup$

I have taken elliptic curve $E\colon y^2=x^3-4x+20$, defined over $\mathbb{F}_{29}$. The number of points on the curve, $\left|E(\mathbb{F}_{29})\right|=37$.

I took base point $P=(1,5)$, and got following results:

Array of scalar multiples of point (1,5)

I want the results graphically to know the behaviour of the curve.

Is there any tool for this to show results graphically by giving input as curve points?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Well, you could simply plot them as Cartesian pairs, but why do you want a graphical representation? Any way you try plotting them will loose information, since they are pairs in $\mathbb{F}_{29}\times\mathbb{F}_{29}$. $\endgroup$
    – Cryptographeur
    Dec 3, 2013 at 11:29
  • $\begingroup$ side question: How can you find a base point of a curve?Or because the underlying field is of prime order so all the points of the curve they do form a basis? $\endgroup$
    – curious
    Dec 3, 2013 at 17:20
  • $\begingroup$ @curious: In this case it is simple because the curve has a prime number of points. $\endgroup$
    – Cryptographeur
    Dec 3, 2013 at 17:30
  • $\begingroup$ What does this mean? $\endgroup$
    – curious
    Dec 3, 2013 at 17:32
  • 2
    $\begingroup$ @curious: Because the curve has a prime number of points, then (since the points on elliptic curves form groups) the curve must be isomorphic to $C_{37}$, which means any point (other than the point at infinity) is a generator. $\endgroup$
    – Cryptographeur
    Dec 10, 2013 at 16:00

3 Answers 3

Reset to default
8
$\begingroup$

None of the above answers see the mistake in the question. The point $P=(1,5)$ is not on the curve $E\colon y^2=x^3-4x+20$ over $\mathbb{F}_{29}$. To see this, place $x=1$ and $y=5$ into the curve equation.

\begin{align} 5^2&=1^3-4+20\\ 25& = 1-4+20\\ 25& \neq 15\\ \end{align}

Therefore $P = (1,5)$ is not on the curve. But it is on the curve $E'\colon y^2=x^3\color{red}{+}4x+20$ over $\mathbb{F}_{29}$.

Now, let us continue to the second equation as $E \colon y^2=x^3\color{red}{+}4x+20$

The curve $E$ has 37 points; the below lists them in projective coordinates;

$[(0 : 1 : 0), (0 : 7 : 1), (0 : 22 : 1), \color{red}{P =(1 : 5 : 1)}, (1 : 24 : 1), (2 : 6 : 1), (2 : 23 : 1), (3 : 1 : 1), (3 : 28 : 1), (4 : 10 : 1), (4 : 19 : 1), (5 : 7 : 1), (5 : 22 : 1), (6 : 12 : 1), (6 : 17 : 1), (8 : 10 : 1), (8 : 19 : 1), (10 : 4 : 1), (10 : 25 : 1), (13 : 6 : 1), (13 : 23 : 1), (14 : 6 : 1), (14 : 23 : 1), (15 : 2 : 1), (15 : 27 : 1), (16 : 2 : 1), (16 : 27 : 1), (17 : 10 : 1), (17 : 19 : 1), (19 : 13 : 1), (19 : 16 : 1), (20 : 3 : 1), (20 : 26 : 1), (24 : 7 : 1), (24 : 22 : 1), (27 : 2 : 1), (27 : 27 : 1)]$

Visualizing a curve is easy when the curve is defined over the Rational Field.

enter image description here

Where all the arithmetic-geometric relations work almost flawlessly; that is $$P+Q-R$$ is on the same line;

When we turn in to finite field case, we have a discrete plot;

enter image description here

The blue line is drawn to show the symmetry since if $(x,y)$ satisfies the curve equation (a point on the curve) then $(x,-y)$ ( in the plot $ = (x,29-y)$) also satisfies the equation ($y^2$).

Now we can see the point addition with $P=(1,5), Q=(5,7)$ and $R = P+Q = (16,2)$ is drawn on the figure.

enter image description here

The proof of the connection of this figure with the ECC point addition is performed by Fgrieu for this question : Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

As we can see from these figures, the point of infinity is missing here. Consider the summation of $R$ and $-R$, there it should be $\mathcal{O}$ on the vertical line! nope!.

Another visualization is the Torus shape. Any rectangle image can be map into a torus shape.

enter image description here

This is a vector image with Asymptote and the points that cannot be seen directly are set to be opaque. This is calculated by ray-tracing. The $R$ and $-R$ on the background. This 3D can be best viewed within HTML. A snapshot from the bottom;

enter image description here

The HMTL is interactive, you can zoom and rotate in 3D, you can download it from Github and view it locally.

Improve this answer
$\endgroup$
2
$\begingroup$

The point is an elliptic curve doesn't actually look anything like a curve when evaluated over a finite field, and indeed there's no real way of visualising points in $\mathbb{F}_{29}\times\mathbb{F}_{29}$ that doesn't loose some of the structure anyway.

The best I can think of would be to plot them simple as points in a $29\times29$ grid and join the dots, but even this would be painfully unclear, since for example when would you 'join' them by overflowing the grid (eg: would the line from $(1,5)\to(4,19)$ go straight from one to the other, or would it go out one side and reappear on the opposite side?).

If you were to evaluate $E(\mathbb{R})$ then the resulting points would form a curve in $\mathbb{R}^2$, which you could then plot.

Improve this answer
$\endgroup$
2
$\begingroup$

As already told the elliptic curve over a finite field is not "really" a curve, but you could find this link (http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography) interesting. In particular, in page 2, an elliptic curve is drawn twice: the first time over the real numbers and the second one over the finite field. There is also an animation of the doubling operation over the finite field. (Hope it helps, even if is not a tool you can use to draw your curve)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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