1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Aug 22 '21 at 10:31
  • $\begingroup$ @fgrieu what is the neutral $\mathcal{O}$ of secp256k1? $\endgroup$
    – Andy
    Aug 22 '21 at 14:43
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Aug 23 '21 at 6:33
2
$\begingroup$

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??
$\endgroup$

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.