The order of an elliptic-curve point P is the smallest positive integer m for which mP is the point at infinity. Repeatedly adding P eventually reaches infinity because the curve has finitely many points; the multiples of P therefore form a cyclic subgroup. A point of order c belongs to the c-torsion subgroup. section 3.1.4
For cryptographic base points, the important order is n: choose a base point B with a large prime order, so nB is infinity and no smaller positive multiple reaches it. This n is distinct from the field prime: it is the largest prime factor of the elliptic-curve cardinality selected as the base point’s order. section 3.1.4 section 5.3
Treat point order as an operational parameter in elliptic-curve arithmetic:
- Generate a public key as Pp = spB, where the private scalar sp is interpreted relative to B’s prime order n. section 5.1.1
- Choose each signing nonce k in the range 1 through n - 1, compute kB, and perform scalar and hash arithmetic modulo n. section 5.1.1 section 5.2
- Require an input P to have order m for a Tate pairing; the other paired point need only have m as a factor of its order. section 17.2
Finding an order on a tiny curve
When the curve order has already been factored, test candidate factors one at a time: compute factor × P and stop at the first result equal to infinity. For a base curve of cardinality 55, the candidate orders are 5, 11, and 55. This brute-force approach depends on having the possible factors in advance and is not suitable for very large extension fields. section 16.3
Figure 16.2 Subroutine to find the order of a point with known factors
Follow the factor-testing flow: multiply the point by each known candidate, recognize infinity, record that factor as the order, or report a missing factor. section 16.3
Order-based classification also supports pairing tests. Points can be sorted into groups by their computed orders, then selected from the required group for experiments. A tiny extension-curve test finds orders 3, 5, 11, 15, 33, 55, and 165, with the largest group containing 960 points. section 17.3
