How to find out what the order of the base point of the elliptic curve is?

Question

I wanted to use https://github.com/AntonKueltz/fastecdsa library and the function parameters for creating curve are:

p,  # (long): The value of p in the curve equation.
a,  # (long): The value of a in the curve equation.
b,  # (long): The value of b in the curve equation.
q,  # (long): The order of the base point of the curve.
gx,  # (long): The x coordinate of the base point of the curve.
gy,  # (long): The y coordinate of the base point of the curve.

The curve I need is this one: https://docs.starkware.co/starkex-docs-v2-deprecated/crypto/stark-curve It gives info about $p, a, b, gx, gy$. But not the $q$

How to infer the $q$ parameter?

Answer 1

Theoretical answer here

• How to determine the order of an elliptic curve group from its parameters?

  • Schoof's algorithm, René Schoof, 1985 with complexity $\mathcal{O}(\log^8 q)$
  • Schoof–Elkies–Atkin algorithm (SEA) with complexity $\mathcal{O}(\log^6 q)$

Practically, one can use SageMath to find it;

a = 1
b = 3141592653589793238462643383279502884197169399375105820974944592307816406665
p = 2^251 + 17*2^192 +1

E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())

card = E.cardinality()
print("cardinality =",card)
factor(card)

G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
print("Generator order q=", G.order())

This outputs

    Elliptic Curve defined by y^2 = x^3 + x + 3141592653589793238462643383279502884197169399375105820974944592307816406665 over Finite Field of size 3618502788666131213697322783095070105623107215331596699973092056135872020481
Additive abelian group isomorphic to Z/3618502788666131213697322783095070105526743751716087489154079457884512865583 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 3141592653589793238462643383279502884197169399375105820974944592307816406665 over Finite Field of size 3618502788666131213697322783095070105623107215331596699973092056135872020481
cardinality = 3618502788666131213697322783095070105526743751716087489154079457884512865583
Generator order q= 3618502788666131213697322783095070105526743751716087489154079457884512865583

Since the order of the curve is prime we have a prime curve, every element, except the identity, is a generator, therefore the order of the basepoint is equal to the order of the curve group.

Also, the cofactor $h$ is 1 since the curve order is prime. Cofactor is defined as the number of the $k$ rational points of the curve $h = \#E(k)/n $ divided by the order of the chosen base element $n$

I couldn't find any information about the magic number (nothing-up-in-my-sleeve). The reason for the choice of $G$ is not clear. Although it is psychological, one should provide it.

---

SageMath uses sea.gp which is a fast implementation of the SEA algorithm. This library is implemented in pari/GP. A good slide about sea.gp is The SEA algorithm in PARI/GP.