How many elements does Bitcoin's secp256k1 have?

Question

I'm wondering whether it is known how many elements does Bitcoin's elliptic curve have? Have not been able to find an answer to this, only for specific subgroups. Is it easy to calculate the number of elements for a given elliptic curve?

Answer 1

There is an efficient point counting algorithm, Schoof's algorithm (Wikipedia) that is used for this purpose. It has been implemented in various packages. The curve equation is $$ y^² = x^³ + 7 $$ over $GF(p)$ with $p = 2256 – 232 – 977,$ a prime. In general we need to do this for any curve since we only have bounds due to Hasse on the number of points $N$ on an elliptic curve, $N$ is within $\pm 2\sqrt{p}$ of the cardinality of the field which is $p.$

The details of how to do this in practice given below are from an answer to a crypto.stackexchange question here:

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??