How to Find the Order of a Point on an Elliptic Curve

The order of a point on an elliptic curve is a group-theoretic quantity: it tells you how many times you must add the point to itself to reach the identity. The identity is the point at infinity, usually written $O$.

The method depends on the field over which the curve is defined. Over a finite field every point has finite order, so you can search by repeated addition. Over the rationals or reals, a point may have infinite order.

Definition

Let $E$ be an elliptic curve and let $P$ be one of its points. The order of $P$ is the least positive integer $n$ such that

$$nP=\underbrace{P+P+\cdots+P}_{n\text{ copies}}=O.$$

If no such positive integer exists, $P$ has infinite order. A point with finite order is called a torsion point.

Elliptic-curve addition is not ordinary coordinate-wise addition. It is defined by the curve’s group law, and calculations over a finite field are carried out in that field. For a prime field $\mathbb{F}_p$, this means reducing coordinates modulo $p$; extension fields require their own field arithmetic.

A direct method over a finite field

For a point $P$ on a curve over a finite field, repeatedly add $P$ to itself:

1. Start with $P$.
2. Compute $2P=P+P$.
3. Continue with $3P=2P+P$, $4P=3P+P$, and so on.
4. Stop at the first multiple equal to $O$. Its multiplier is the order.

This search always terminates over a finite field because the curve has finitely many points. In practice, you use efficient scalar multiplication—repeated doubling and addition—rather than adding one copy at a time when the multiplier is large.

Worked example: a point of order 4

Consider the curve over the finite field $\mathbb{F}_5$:

$$E: y^2=x^3-x$$

and the point $P=(2,1)$. It lies on the curve because $1^2=2^3-2=6\equiv1\pmod 5$.

For a nonsingular short Weierstrass curve $y^2=x^3+ax+b$ over a field of characteristic other than 2, doubling a point $(x,y)$ with $y\ne0$ uses the slope

$$\lambda=\frac{3x^2+a}{2y},\qquad x(2P)=\lambda^2-2x,\qquad y(2P)=\lambda\bigl(x-x(2P)\bigr)-y.$$

Here $a=-1\equiv4\pmod5$. Thus

$$\lambda=\frac{3(2)^2-1}{2(1)}=\frac{11}{2}\equiv\frac{1}{2}\equiv3\pmod5,$$

because $2\cdot3\equiv1\pmod5$. The doubled coordinates are

$$x(2P)=3^2-2(2)=5\equiv0\pmod5,$$ $$y(2P)=3(2-0)-1=5\equiv0\pmod5.$$

So $2P=(0,0)$. A point with $y=0$ is its own inverse on a short Weierstrass curve, so $(0,0)+(0,0)=O$. Therefore $4P=O$, while neither $P$ nor $2P$ is $O$. The smallest positive multiplier giving $O$ is 4, so $P$ has order 4.

Making the search faster

If the curve is over $\mathbb{F}_q$, its total number of points, written $\#E(\mathbb{F}_q)$, is finite. The order of any point divides this group size. Hasse’s bound gives

$$\left|\#E(\mathbb{F}_q)-(q+1)\right|\le 2\sqrt q.$$

If you know the group size $M=\#E(\mathbb{F}_q)$, you can use its prime factors to reduce the work. Start with $n=M$. For each prime $\ell$ dividing $n$, test whether $(n/\ell)P=O$. If it is, replace $n$ by $n/\ell$ and test again. When no prime factor can be removed, $n$ is the order of $P$.

This works because the order of $P$ divides $M$, and the tests remove factors that are not needed. The group size must be known correctly; a bound on the group size alone is not a substitute for knowing a multiple of the point’s order.

What changes over the rationals?

For a curve over $\mathbb{Q}$, the field is infinite, but the set of rational points on a particular curve may be finite or infinite. A point need not return to $O$. Repeatedly adding a point can suggest that it has infinite order, but failure to reach $O$ in a finite number of steps does not prove that. Proving finite or infinite order generally uses additional results about rational torsion or the structure of the curve’s rational points.

Common mistakes

• Stopping at any multiple, rather than the first one: If $nP=O$, the order may be a proper divisor of $n$. Check smaller candidate multiples.
• Forgetting the identity: The identity is $O$, not the coordinate pair $(0,0)$. A point such as $(0,0)$ is usually an ordinary point on the curve.
• Using ordinary real arithmetic over a finite field: Carry out arithmetic in the correct finite field; in $\mathbb{F}_p$, reduce modulo $p$, and interpret division as multiplication by the inverse in that field.
• Assuming every point has finite order over every field: This is guaranteed over finite fields, but not over $\mathbb{Q}$ or $\mathbb{R}$.
• Using the wrong curve equation: The formulas shown apply to a short Weierstrass equation $y^2=x^3+ax+b$; other curve models have different addition formulas.

For a specific curve and point, the essential calculation is to determine the least positive $n$ for which scalar multiplication gives $nP=O$.