The order of the generator point G used in bitcoin

Question

Hi I was just wondering how the order of the generator point G used in bitcoin was actually calculated.

From the specification listed http://www.secg.org/SEC2-Ver-1.0.pdf for secp256k1 I can see listed is the generator point G along with its order, however I am unsure how this was actually calculated.

In one of the books I was looking through it was mentioned that Hasse's Theorem was used to calculate this value, however upon looking up this theorem this seems to only provide a bound. Any insight would be appreicated thanks :)

Answer 1

It's easy to verify the order (n): Multiply G by n and find that you get the point at infinity. This proves that n is either the order or a multiple of it. Then convince yourself n is prime using a Baillie-PSW primality test, so it must be the order itself and not a multiple of it.

Finding the order is not quite so simple as verifying it. To do so you would use Schoof's_algorithm, which requires quite a bit of number-theory complexity. The Wikipedia article on Schoof's explains how Hasse's theorem is critical to this process by restricting the range of orders that could possibly be the correct one.

Answer 2

The order of G is the number of time you will have to add G to get a point at infinity. You start at G, then add G you get 2G. If you add G a total of n times, you will get a point at infinity. This order n will tell you how many times you can add G before you reach infinity or how many distinct points are there on the curve.