Counting Points on Elliptic Curves over Finite Field: Order of Elliptic Curve Group

ECDSA enables to produce signatures faster. Besides, its both signatures and keys are much smaller than adopted alternative options offering similar security levels. However, this algorithm introduces a new thing called order of group. Point addition operations are handled on a public modulo whereas signing and verification could be handled on order of elliptic curve group. This states total number of points over that finite field.

Vlog

Elliptic Curve over Finite Field

If we use a modulo in our elliptic curve equation, we are able to modify the calculations with denominators with their multiplicative inverse values. In that we will just have integer points. Also, we will have limited number of points instead of infinite number of points as illustrated below. That is why, we are saying elliptic curves over finite fields. Besides, number of points describes the order of that elliptic curve group.

---

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

---

Brute Force Method

Curve equation, base point and modulo are publicly known information. The easiest way to calculate order of group is adding base point to itself cumulatively until it throws exception.

Suppose that the curve we are working on satisfies y² = x³ + 7 mod 199 and the base point on the curve is (2, 24). The following python code checks all alternatives until faced with an exception. BTW, all subsidiary functions can be found on GitHub.

print("P: (", x0,", ",y0,")")

new_x, new_y = pointAddition(x0, y0, x0, y0, a, b, mod)
print("2 P: (",new_x,", ",new_y,")")

for i in range(3, 1000):
   try:
      new_x, new_y = pointAddition(new_x, new_y, x0, y0, a, b, mod)
      print(i,"P: (",new_x,", ",new_y,")")
   except:
      print("order of group: ",i)
      break

This code will produce the following results and returns exception while calculating 211P. This means that order of this elliptic curve group is 211 because 211P is infinite.

P: ( 2 , 24 )
2 P: ( 108 , 49 )
3 P: ( 72 , 166 )
4 P: ( 18 , 80 )
5 P: ( 42 , 35 )
…
206 P: ( 42 , 164 )
207 P: ( 18 , 119 )
208 P: ( 72 , 33 )
209 P: ( 108 , 150 )
210 P: ( 2 , 175 )

We can show the order of this elliptic curve group as

F(199) = 210

Notice that x coordinates are equal for point P-210P, 2P – 209P, 3P – 208P, …

This way is easy to understand but it is really hard to run. Because complexity of this operation is O(n) in big O notation whereas n is the public modulo and it should be very large integer. For example, bitcoin protocol works on 256-bit integer as calculated below.

---

---

#modulo for bitcoin
mod = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)
print("modulo: ", mod)

The modulo of bitcoin protocol is equal the following value. You can imagine how hard to check all points whether it is infinite or not for the following one.

modulo: 115792089237316195423570985008687907853269984665640564039457584007908834671663

Hasse Theorem

Suppose that elliptic curve satisfies the equation y² = x³ + ax + b mod p. In other words, order of the elliptic curve group over GF(p) must be bounded by the following equality. BTW, √p comes from the probability theory.

p + 1 – 2 * √p ≤ order ≤ p + 1 + 2 * √p

Let’s subtract the boundaries. This reveals the complexity.

p + 1 + 2 * √p – (p + 1 – 2 * √p) = p + 1 + 2 * √p – p – 1 + 2 * √p = 4 * √p = 4 * p^1/2

Big O notation says that complexity of (4 * √p) is still equal to O (√n). It is still too many operations to run.

Baby Step Giant Step

This is not the fastest way but it is my favorite method to find the order of elliptic curve group. Complexity of this approach is O(⁴√n) or O(n^1/4) in big O notation. It means that complexity reduces dramatically when compared to brute force and Hasse theorem.

from math import sqrt

Q = applyDoubleAndAddMethod(x0, y0, mod + 1, a, b, mod)
print("(mod + 1)P = ", mod + 1,"P = ",Q)

m = int(sqrt(sqrt(mod))) + 1
print("1 + (mod^1/4) = 1 + (",mod,")^1/4 = ",m)
print()

terminate = False

for j in range (1, m+1):
   jP = applyDoubleAndAddMethod(x0, y0, j, a, b, mod)
   print(j,"P = ",jP, ": ", end="")

   for k in range (-m, m+1):
      checkpoint = applyDoubleAndAddMethod(x0, y0, m*2*k, a, b, mod)
      checkpoint = pointAddition(checkpoint[0], checkpoint[1], Q[0], Q[1], a, b, mod)
      print(checkpoint," ", end="")

      if checkpoint[0] == jP[0]: #check x-corrdinates of checkpoint and jP

         orderOfGroup = mod + 1 + m*2*k
         print("\norder of group should be ", orderOfGroup ," ± ", j)

         try:
            applyDoubleAndAddMethod(x0, y0, orderOfGroup + j, a, b, mod)
         except:
            orderOfGroup = orderOfGroup + j
            terminate = True
            break

          try:
             applyDoubleAndAddMethod(x0, y0, orderOfGroup - j, a, b, mod)
          except:
             orderOfGroup = orderOfGroup - j
             terminate = True
             break

   print()
   if terminate == True:
      break

print("order of group: ", orderOfGroup)

Notice that 3P (72, 166) and 208P (72, 33) are negative points of each other because their x-coordinates are same. Now we need to calculate both (208+3)P and (208-3)P. Which one throws exception, then it would be order of group!

In this way, 12 calculations are enough to find the order of an elliptic curve over GF(199) group as shown below. In contrast, brute force method requires 211 calculation to do same duty. This approach is 17 times faster than the brute force on GF(199).

---

---

Of course, there is always better way to do it! Order of group calculation can be handled in a less complex way with Schoof Method. Its compexity is O(log⁸n). But its mathematical background is much more complex than mentioned one. That’s why, I would skip it for now.

So, we’ve mentioned how to calculate order of an elliptic curve group. Order of group should be calculated once and announced publicly. There are a lot of common elliptic curves and their both mod and order of group are publicly available. Mostly, you do not have to calculate the order of group. However, we researchers are suspicious ones and feel safe when know the background!

I pushed the source code of this study to GitHub. Also, you can find the brute force method in this notebook.

If the topic draws your attention, you can enroll the Elliptic Curve Cryptography Masterclass online course to dig deeper.

---

Support this blog if you do like!

    

---