1
$\begingroup$

In Curve25519 we typically have this generator point or base point:

Gx = 9
Gy = 14781619447589544791020593568409986887264606134616475288964881837755586237401
or:
Gy' = p - Gy 
   = 43114425171068552920764898935933967039370386198203806730763910166200978582548

Where p = 2^255-19, the dimension of the prime field Fp in which we evaluate the curve.

What is the order of this generator point?

i.e. what is the smallest n so nG = 0.

Before actually thinking about it, I just assumed that would be p since p is prime. But obviously that's wrong as we're dealing with elliptic curve point addition here, not just scalar multiplication in modular arithmic.

So I'm wondering what is G's order, and perhaps more difficult: how can I find this myself? (once I have the value I can easily verify it, that's much less complicated)

$\endgroup$
4

1 Answer 1

5
$\begingroup$

According to this source, the points of this curve are a group of cardinality $8\cdot p'$ with $p':=2^{252}+27742317777372353535851937790883648493$.

This number can be computed by using the Schoof algorithm or the more efficient Schoof–Elkies–Atkin algorithm.

Then, by Lagrange theorem, and because $p'$ is prime (can be check with any efficient Primality test), it implies all the points $P$ can only have order $o_P= 2^{i_P}\cdot p^{\prime j_P}$, with $0\leq i_P\leq 3$ , and $0\leq j_P\leq1$.

We can compute $p'\cdot G$ with the fast exponentiation (Square and multiply algorithm called also Double-and-Add in a elliptic curve context), and notice it's equal to $\mathcal{O}$ the neutral element of the curve.

We deduce that $o_G$ the order of $G$ divides $p'$. Then $i_G= 0$.

Because $G\neq \mathcal{O}$, $o_G\neq 1$, then $j_G=1$.

We conclude that $G$ is of order $o_G = p'$.

$\endgroup$
0

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.