Suppose you have an elliptic curve
y² = x³ + ax + b
over a finite field Fp for prime p. How many points are on the curve?
Brute force
You can count the number of points on the curve by brute force, as I did here. Loop through each of the p possibilities for x and for y and count how many satisfy the curve’s equation, then add one for the point at infinity. This is the most obvious but slowest approach, taking O(p²) time.
Here’s a slight variation on the code posted before. This time, instead of passing in the function defining the equation, we’ll assume the curve is in the form above (short Weierstrass form) and pass in the parameters a and b. This will work better when we refine the code below.
def order(a, b, p):
c = 1 # The point at infinity
for x in range(p):
for y in range(p):
if (y**2 - x**3 - a*x - b) % p == 0:
c += 1
return c
Better algorithm
A better approach would be to loop over the x values but not the y‘s. For each x, test determine whether
x³ + ax + b
is a square mod p by computing the Legendre symbol. This takes O(log³ p) time [1], and we have to do it for p different values of x, so the run time is O(p log³ p).
from sympy import legendre_symbol
def order2(a, b, p):
c = 1 # The point at infinity
for x in range(p):
r = x**3 + a*x + b
if r % p == 0:
c += 1 # y == 0
elif legendre_symbol(r, p) == 1:
c += 2
return c
Schoof’s algorithm
There’s a more efficient algorithm, Schoof’s algorithm. It has run time O(logk p) but I’m not clear on the value of k. I’ve seen k = 8 and k = 5. I’ve also seen k left unspecified. In any case, for very large p Schoof’s algorithm will be faster than the one above. However, Schoof’s algorithm is much more complicated, and the algorithm above is fast enough if p isn’t too large.
Comparing times
Let’s take our log to be log base 2; all logs are proportional, so this doesn’t change the big-O analysis.
If p is on the order of a million, i.e. around 220, then the brute force algorithm will have run time on the order of 240 and the improved algorithm will have run time on the order of 220 × 20³ ≈ 233. If k = 8 in Schoof’s algorithm, its runtime will be on the order of 208 ≈ 234, so roughly the same as the previous algorithm.
But if p is on the order of 2256, as it often is in cryptography, then the three algorithms have runtimes on the order of 2512, 2270, and 264. In this case Schoof’s algorithm is expensive to run, but the others are completely unfeasible.
[1] Note that logk means (log q)k, not log applied k times. It’s similar to the convention for sine and cosine.
