0
$\begingroup$

Imagine if we were on a mission to try to calculate the order of the cyclic group $n$

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Given the order of the finite field $p$

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Generator point $G$:

G = (
55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424
)

which has the private key of $1$.

Cofactor $h$ is $1$. The equation is $y^2 = x^3 + 7$

We can find the $n$ with Schoof-Elkies-Atkin algorithm

However, it's a bit confusing. Here's the solution in Sage. It presents one code example:

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

What is [0, 7] specifically? These cannot be the coordinates of the G, since we already established that they are different.

And where is the $G$ even used in this calculation?

What if we used instead of $G$, another point on the elliptic curve, that we know for sure that it sits on the curve and is part of our cyclic group? Like this one:

(x,y) = (
44886295857190546091508615621464465421050773292389158775895365558788257183826,
79820197542983972470655013754473404410649480536210503962616926227235987362275
)

The private key for this point sits somewhere between $2^{129}$ and $2^{130}$. What would happen if we use this point, instead of $G$ for our Schoof-Elkies-Atkin to calculate the $n$ (order of the cyclic group)?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The $[a,b]$ in the SageMath code is for the short Weierstrass curve representation $y^2=x^3+ax+b.$ If the prime $p \neq 2,3$ all Weierstrass curves can be represented in the short form. Naturally, SageMath has a short form to define the curves with a short Weierstrass representation.

Curve order and point order may have different values if the curve order is not prime like the Curve448, Curve25519, etc.

Schoof-Elkies-Atkin calculates curve order which doesn't use the points.

$\endgroup$
3
  • $\begingroup$ So the Schoof-Elkies-Atkin just uses the order of the finite field p and the equation $y^2 = x^3 + ax + b$ and nothing else? $\endgroup$ Commented Aug 4 at 8:33
  • $\begingroup$ In short, yes, however, they use Hasse's theorem on elliptic curves, the Chinese remainder theorem, division polynomials, and modular polynomials. Division polynomials is a way to to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. You don't enter a point to Schoof-Elkies-Atkin or Schoof's aclgorithm $\endgroup$
    – kelalaka
    Commented Aug 4 at 9:21
  • $\begingroup$ Ok, I understand. Thank you! $\endgroup$ Commented Aug 4 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.