A naive point counting algorithm
{{{id=8|
def point_count(E):
'''Point counting algorithm using legendre symbols.
Assume E is in form y^2 = x^3 + ax + b.
'''
F = E.base_field()
R. = PolynomialRing(F)
f = X^3 + E.a4()*X + E.a6() # defining equation for E
n = 1 # have to count the point at infinity!
for x in F:
w = f(x)
if w == 0:
n += 1 # only 1 possible y value when f(x) = 0
elif w.is_square():
n += 2 # 2 possible y values when f(x) is a square
return n
///
}}}
Let's test it on a random curve:
{{{id=2|
def random_curve(p):
F = GF(p)
return EllipticCurve([F.random_element(),F.random_element()])
///
}}}
{{{id=19|
E = random_curve(31); E
///
}}}
{{{id=20|
point_count(E)
///
}}}
Did it work? Here's a list of all the points on $E$:
{{{id=21|
L = E.points(); L
///
}}}
{{{id=22|
len(L)
///
}}}
It worked!
However, this method of counting points is very slow.
{{{id=9|
p = next_prime(123456);
E = random_curve(p); E
///
}}}
{{{id=13|
time point_count(E)
///
}}}
The built in method point_count, which uses Schoof's algorithm (Washington section 4.5), is much faster:
{{{id=15|
time E.count_points()
///
}}}
In fact, variations of Schoof's algorithm have been used to count points on curves over fields with more than 5000 digits! See elliptic curve point counting record.
How many points are on a random curve?
{{{id=1|
p = next_prime(10^50); p
///
}}}
{{{id=3|
E = random_curve(p); E
///
}}}
{{{id=4|
E.count_points()
///
}}}
{{{id=5|
for i in range(10):
E = random_curve(p)
print E.count_points()
///
}}}
It looks like the number of points is really really close to the field size -- roughly the first half of the digits are the same (modulo carries). Hasse's theorem says that this is always the case.
{{{id=18|
///
}}}