Elliptic curves over a finite field represented as winding it around a torus.

Question

I have an elliptic curve $E$ in the form $ y ^ 2 = 4x^3 - a x - b $ and a prime number $p$. Now I want to find the integer $(x,y)$ pairs which satisfies the equation $$mod(y ^ 2,p) =mod(4x^3 - a x - b,p)$$ I can see, if I find all the points which are located in the domain $0<=x,y<p$, and I have a solution $(x_1,y_1)$ I can generate easily infinitely many of the solutions just by adding to them the product of $p$ and an integer like: $(x_1+np,y_1+mp)$. Due to this property, I've heard, this domain could be represented as a torus. My question is that, if I start to wind up my original $E$ around this torus (formed by the "base" domain), does $E$ eventually go through all the $(x,y)$ solution pairs? There is a link to the video which made me to think about this question: https://www.youtube.com/watch?v=mFVKuFZ29Fc

Answer 1

Let have an Elliptic Curve over a finite field $K = \mathbb{F}_q$ then the curve is defined as

$$E(\mathbb{K}) := \{ (x, y) \in \mathbb{K}^2 \mid y^2+a_1xy+a_3y = x^3+a_2x^2+a_4x+a_6\} \cup \{\mathcal O\}$$

What is $\{\mathcal O\}$, it is the point of infinity and has no geometric picture and in the algebraic construction, we magically add one with no coordinates.

Bounds on the number of points

Now, if the characteristic is not equal to 2 or 3, then we have the short Weierstrass Equation

$$y ^ 2 = 4x^3 - a x - b $$

As we can see from the algebraic definition we can have at most $q^2+1$ point on the curve (not infinitely many). If you assume that $q$ is a prime (not a prime power) and $4x^3 - a x - b $ attains all $q$ values, then by the quadratic residue theorem on primes, we already know $(p - 1)/2$ of the elements are Quadratic NonResideu, so they are not a solution to the curve equation, i.e. $y^2= a$ has no solution.

For the bound of the number of points we have Hasse's theorem

$$|N - (q+1)| \le 2 \sqrt{q}$$

How to find the exact number of points

To calculate the exact number of points we can use

• Schoof's algorithm, René Schoof, 1985 with complexity $\mathcal{O}(\log^8 q)$, or improved version;
• Schoof–Elkies–Atkin algorithm (SEA) with complexity $\mathcal{O}(\log^6 q)$

In Sagemath calling E.cardinality() is enough to get the number of points.

How to represent the curves over a finite field

In the finite case, we have a discrete plot

This is the plot of curve $E \colon y^2=x^3+4x+20$ over $\mathbb{F}_{29}$ with 37 points. Notice the symmetry $y,-y$!. In this image there is no representation of the $\mathcal{O}$, it can be represented in projective coordinates.

Point addition

Notice the red line passing through $P$ and $Q$ and the third point and the reflected point $ R = P + Q$.

Mapping curve to Torus

Any rectangle can be mapped into a torus with some stretches.

To better view this image use the interactive HTML version, you can zoom and rotate in 3D, you can download it from Github and view it locally. You can also see the mapping method on the code.