Score:1

Crypto

How to calculate the order of secp256k1?

Andy

12/21/22, 9:16 PM

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?

407

1 + 3

elliptic-curves

finite-field

secp256k1

fgrieu

12/22/22, 10:31 AM

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](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves)). 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.

Andy

12/22/22, 2:43 PM

@fgrieu what is the neutral $\mathcal{O}$ of `secp256k1`?

fgrieu

12/23/22, 6:33 AM

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$.

Score:2

Crypto

djao

12/22/22, 5:02 AM

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