0

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 :)

  • What you're looking for is Schoof's algorithm. – Pieter Wuille Mar 18 at 21:36
4

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.

0

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.

  • 1
    While correct, this is not how the number of points on the curve is computed (counting to 2^256 is rather infeasible). – Pieter Wuille Mar 18 at 21:45
  • True. I tried to provide more of a qualitative commentary around that. – Ugam Kamat Mar 18 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.