I'm trying to follow a youtube explanation of elliptic curves, and at this point the presenter defines the following elliptic curve:
E = EllipticCurve([2,5])
and proceeds to find the number of solutions over Fp with p = 5, which I supposed it means Z/5Z (i.e. modulo 5) as
E.Np(5)
Since there are two solutions, I don't think I understand what is going on. I only see (0,0) as a possible integer over the field Z/5Z.
Naturally, I want to see the solutions, but the closer I get is to print out the points after redefining the function as follows:
print(EllipticCurve(Zmod(5),(2,5)).points())
The output is:
[(0 : 0 : 1), (0 : 1 : 0)]
Now this I think, means the point (0,0). I found online that the second point is the point at infinity. In this case the number of solution is really 1, not 2, and the function E.Np(5) would be overcounting (most likely not).
How can I extract all the points in a simpler way, and make sure that E.Np(5) makes sense?
When discussing points on elliptic curves, we really mean projective points on elliptic curves. That is, instead of considering the curve E: Y^2 = X^3 + 2X + 5, we really consider the curve E: Y^2 Z = X^3 + 2 X Z^2 + 5 Z^3, a homogenous expression where every term has degree 3. And in this form, we consider two points (a : b : c) and (A : B : C) to be the same if one tuple is a multiple of the other (where these mean the x, y, z coordinates of a point).
This is a "smooth projective elliptic curve", where I emphasize that the word projective is what means that we homogenize and consider three-variable points. The alternative, without homogenizing, is called an affine curve.
It turns out that the properties of elliptic curves are much nicer and more uniform when considered as projective curves. When a mathematician talks about an elliptic curve, it is common to flip between projective and affine coordinates. Unfortunately, it is also common to abuse notation and refer to the projective curve by its affine model. But the "true" object is typically the projective object. This is happening implicitly in your video.
Every elliptic curve will have a point at infinity, given by the coordinate (0 : 1 : 0). We can check that this is a point on the curve by checking that setting X = 0, Y = 1, Z = 0 in projective coordinates. The other coordinate is indeed (0 : 0 : 1), which corresponds to the affine coordinate (0, 0).
In sage, you have identified the right way to count solutions over a finite field:
E5 = EllipticCurve(GF(5), [2, 5])
E5.points()
# [(0 : 0 : 1), (0 : 1 : 0)]
One can check that the underlying data is stored projectively too. We take the affine point (0, 0) and compute its point. Then we have sage print it back to us (it gives it to us in projective coordinates). One reason is that the rational points form a group and can be added together: and adding this point to itself gives the point at infinity!
P = E5([0, 0]) # the point (0, 0)
print(P)
# (0 : 0 : 1)
print(P + P)
# (0 : 1 : 0)
To restrict only to affine points, you need to ignore the point (0 : 1 : 0). If you compare affine point counts to the others in the video, you'll find that you're always off by one, due to the projective point (0 : 1 : 0).
For example, we can directly compare.
def naive_find_points_mod(modulus):
i = 1
for x in range(modulus):
for y in range(modulus):
if (y^2 - (x^3 + 2*x + 5)) % modulus == 0:
print(f"{i}: (x, y) = ({x}, {y})")
i += 1
print(E.Np(7)) # 7 points
naive_find_points_mod(7)
# prints out
# 1 (x, y) = (1, 1)
# 2 (x, y) = (1, 6)
# 3 (x, y) = (4, 0)
# 4 (x, y) = (5, 0)
# 5 (x, y) = (6, 3)
# 6 (x, y) = (6, 4)
# Only 6 points! The missing point is the point at infinity
Finally, the simple algorithm in naive_find_points_mod is one possible answer to your last question, looking for a direct algorithm. The point here is that there are only p^2 affine points mod p, and one could check them all if p isn't too large. As p gets larger, there are some very nontrivial algorithms that one can use, but that's a different subject.