How to calculate the order of secp256k1?

The elliptic curve secp256k1 is defined as $$y^2 = x^3 + 7$$. The prime for the field is set to:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

So now, one should be able to calculate the order by using the Schoof's Algorithm. There is a Python implementation provided here: https://github.com/pdinges/python-schoof

However, it seems to be too time consuming to calculate the order for large primes. Furthermore, the implementation seems not to be capable to calculate it for such a large prime.

root@78774381cc80:/home/python-schoof# python3 reduced_computation_schoof.py 17 0 7
Counting points of y^2 = x^3 + 0x + 7 over GF<17>: 18
root@78774381cc80:/home/python-schoof# python3 reduced_computation_schoof.py 115792089237316195423570985008687907853269984665640564039457584007908834671663 0 7
Counting points of y^2 = x^3 + 0x + 7 over GF<115792089237316195423570985008687907853269984665640564039457584007908834671663>: Traceback (most recent call last):
File "reduced_computation_schoof.py", line 268, in <module>
runner.run()
File "/home/python-schoof/support/running.py", line 498, in run
result = self.__algorithm( *item, output=self.__output)
File "reduced_computation_schoof.py", line 258, in reduced_computation_schoof_algorithm
order = p + 1 - frobenius_trace( EllipticCurve( FiniteField(p), A, B ) )
File "reduced_computation_schoof.py", line 55, in frobenius_trace
len(search_range),
OverflowError: Python int too large to convert to C ssize_t

Does someone know it was calculated and how to reproduce it? Is there a better implementation of the Schoof's Algorithm for such large numbers?

• Note: The order $n$ of secp256k1 is well-known, and it's easy to verify it: pick any point $T$ (other than the neutral $\mathcal O$) and check $n\,T=\mathcal O$, which proves the order of $T$ divides $n$. Now check $n$ is prime and close to $p$ (within 30% will do; or Hasses' bound). Independently: we have a close reason on the tune of "Requests for literature, software or similar recommendations are off-topic", so the question is in hot waters; we'll see if the question's interest outweigh that general prohibition.
– fgrieu
Aug 22 '21 at 10:31
• @fgrieu what is the neutral $\mathcal{O}$ of secp256k1?
– Andy
Aug 22 '21 at 14:43
• The neutral $\mathcal O$ is the neutral element of the group of points of the curve. Equivalently, for all points $T$ of the curve, $T+\mathcal O=T=\mathcal O+T$. It is also called the point at infinity and noted $\infty$. It does not have coordinates $x$, $y$ satisfying the curve's equation $y^2\equiv x^3+7\pmod p$.
– fgrieu
Aug 23 '21 at 6:33

PARI includes (among many other things) an implementation of Schoof's algorithm (more specifically the Schoof-Elkies-Atkin algorithm).

? p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
%1 = 115792089237316195423570985008687907853269984665640564039457584007908834671663
? ellcard(ellinit([0,7], p))
%2 = 115792089237316195423570985008687907852837564279074904382605163141518161494337

It's open source, so you can easily look inside.

If you don't want to install PARI, CoCalc lets you run PARI (or Sage) in a browser. Just start up a new project, and inside that a new Linux terminal, enter "gp" and you're off and running in PARI.

Alternatively you can do the computation directly in Sage (which you can also run via CoCalc: New → Sage worksheet), but this doesn't give you any new implementation since Sage just calls PARI for this function:

sage: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: EllipticCurve(GF(p), [0,7]).order()
115792089237316195423570985008687907852837564279074904382605163141518161494337

For documentation in PARI:

? ?ellcard
ellcard(E,{p}): given an elliptic curve E defined over a finite field Fq,
return the order of the group E(Fq); for other fields of definition K, p must
define a finite residue field, (p prime for K = Qp or Q; p a maximal ideal for
K a number field), return the order of the (non-singular) reduction of E.

For documentation in Sage:

sage: E = EllipticCurve(GF(p), [0,7])
sage: E.order?
sage: E.order??