For an elliptic curve over a finite field, the curve cardinality, written #E, is the total number of curve points, including the point at infinity. Group order is the number of points in a particular cyclic group or subgroup. These numbers coincide for a prime-order curve, but they differ when the cardinality has several factors. section 4.1.1 section 2.2
Write an ordinary curve as E: y² = x³ + a₄x + a₆ mod p. Its cardinality follows #E = p + 1 − t, where t is the trace of Frobenius and |t| ≤ 2√p. Point counting is mathematically deep, so practical curve searches use PARI/gp routines to compute the cardinality before examining its factors. section 6.2 section 6.0
Factorization determines the useful group structure:
- If #E has factors a·b·c, cyclic subgroups can have orders a, b, c, ab, ac, bc, and abc; a point can belong to more than one subgroup. section 2.2
- Multiplying a random point by complementary small factors can move it into a desired smaller subgroup; for #E = 2·5·c, multiplying by 10 yields a point in the subgroup of order c. section 2.2
- For cryptographic use, select a curve with a large prime factor r and a small cofactor h. A cofactor of 1 makes every point have the same order and removes small-factor shortcuts. section 6.3 section 14.6
- Choose a base point G whose order is the large prime n. On a prime-cardinality curve, every non-infinity point has that same prime order and can serve as a generator. section 4.1.1 section 5.3
Counting a small curve
Over p = 43, the curve y² = x³ + 23x + 42 mod 43 has 55 points when the point at infinity is included. Of its 54 finite points, 4 have order 5, 10 have order 11, and 40 have order 55. Selecting an order-11 point avoids mixing with points of other orders. section 13.3.2
? E.group %2 = [1148, [1148], [[Mod(702, 1187), Mod(1007, 1187)]]]
PARI/gp group output reports a curve with 1148 points, cyclic structure [1148], and a generator point (702, 1007). section 6.1.2
A practical search computes #E, removes powers of 2, tests small factors, and checks whether the remaining value is prime. Curves are retained when their factorization leaves a large prime with only an acceptable small cofactor; curves with many small factors are rejected. section 6.2.2 section 6.5
Over extension fields, cardinality changes with the field size: #Eₖ = pᵏ + 1 − tₖ. A large prime r from the base-curve cardinality must also divide the extension-curve cardinality for pairings, and the smallest suitable k is the embedding degree. section 13.1
For pairing-oriented curves, the full group may be a product of two cyclic groups, Z/d₁Z × Z/d₂Z with d₁ dividing d₂. This differs from the usually single cyclic base-curve structure and requires the large prime to occur in both group factors. section 15.1
