Subgroups, Generators, Orders, And Cofactors

Elliptic Curves Over Finite Fields constructed the finite group

$$E(\mathbb{F}_{11}): \qquad y^2 \equiv x^3+x+1 \pmod{11}.$$

That construction produced $13$ affine points and the identity point $\mathcal{O}$. It also used the finite-field addition formulas with

$$P=(1,5)$$

to calculate

$$2P=(3,3) \qquad\text{and}\qquad 3P=(8,2).$$

We will now continue those exact scalar multiplications around the point cloud. The resulting cycles give concrete meanings to curve order, point order, subgroup, generator, base point, and cofactor.

The main idea resembles the modular clock from Finite Fields and Modular Arithmetic. Repeatedly adding a fixed number moves around a finite clock; repeatedly adding a fixed curve point moves around a finite set of curve points. In both cases, the chosen step determines which positions we visit before returning to the start.

0.1. Curve Order: The Size of the Complete Group

The curve order is the number of points in the complete curve group, including $\mathcal{O}$. It is written

$$\#E(\mathbb{F}_p).$$

For the running curve, Chapter 6 found $13$ affine points. Therefore,

$$\#E(\mathbb{F}_{11})=13+1=14.$$

This number describes the whole curve group. It is not the field modulus and it is not automatically the order of every point.

Important

In the running example, $p=11$ is the number of field elements, while $\#E(\mathbb{F}_{11})=14$ is the number of curve points. These numbers measure different objects.

0.2. Point Order: The Length of One Scalar Cycle

Scalar multiplication repeatedly adds the same point:

$$kP=\underbrace{P+P+\cdots+P}_{k\text{ copies of }P}.$$

We also define $0P=\mathcal{O}$. Now imagine the $14$ curve points as stops on a circular route. The point $P$ acts like a fixed step: begin at $\mathcal{O}$, add $P$ to move to the next stop, then add $P$ again, and keep going.

$$\mathcal{O} \xrightarrow{+P}P \xrightarrow{+P}2P \xrightarrow{+P}3P \xrightarrow{+P}\cdots$$

This route is an abstract picture of the group operation. It is not a geometric line drawn through the point cloud.

For $P=(1,5)$, Chapter 6 already gave us the first two moves:

$$P=(1,5), \qquad 2P=(3,3), \qquad 3P=(8,2).$$

We do not need to memorize every coordinate encountered after that. Three landmarks reveal the structure of the route:

• At the halfway point, $7P=(2,0)$. This point is its own inverse because its $y$-coordinate is zero.
• One step before completing the route, $13P=(1,6)=-P$.
• Adding $P$ once more gives $14P=(-P)+P=\mathcal{O}$.

No earlier positive multiple is $\mathcal{O}$. The route therefore makes one complete lap after fourteen additions of $P$.

The order of a point $P$, written $\operatorname{ord}(P)$, is the smallest positive integer $n$ for which

$$nP=\mathcal{O}.$$

Equivalently,

$$\operatorname{ord}(P)=\min\{n>0:nP=\mathcal{O}\}.$$

For the running point,

$$\operatorname{ord}(P)=14.$$

The two uses of the word order now answer different questions:

Curve order — total stops

How many points exist in the complete curve group? Here, $\#E(\mathbb{F}_{11})=14$.

Point order — lap length

How many times do we add this point before returning to $\mathcal{O}$? Here, $\operatorname{ord}(P)=14$.

0.3. Generated Subgroups and Generators

The stops reached before a scalar cycle returns to $\mathcal{O}$ form the subgroup generated by $P$:

$$\langle P\rangle = \{\mathcal{O},P,2P,\ldots,(n-1)P\},$$

where $n=\operatorname{ord}(P)$. This subgroup contains exactly $n$ points.

A point is a generator of a group $H$ when its scalar multiples reach every element of $H$:

$$\langle P\rangle=H.$$

In the route analogy, $\langle P\rangle$ is the collection of stops reachable by repeatedly taking the $P$-step. A generator of the whole group is a step that eventually visits every stop.

Every point generates its own subgroup, but it does not necessarily generate the complete curve group. For $P=(1,5)$, one lap visits all $14$ curve points. Thus,

$$\langle P\rangle=E(\mathbb{F}_{11}),$$

and $P$ is a generator of the whole curve group.

0.4. Select a Smaller Prime-Order Subgroup

Cryptographic systems commonly work inside a carefully selected large prime-order subgroup rather than requiring the base point to generate every point on the curve.

Our toy curve can demonstrate the same structure. Select the point already obtained by doubling $P$ in Chapter 6:

$$G=2P=(3,3).$$

Multiples of $G$ are the even multiples of $P$ because

$$kG=k(2P)=2kP.$$

On the fourteen-stop route traced by $P$, adding $G=2P$ is like moving two stops at a time:

$$\mathcal{O} \xrightarrow{+G}2P \xrightarrow{+G}4P \xrightarrow{+G}6P \xrightarrow{+G}\cdots \xrightarrow{+G}12P \xrightarrow{+G}14P=\mathcal{O}.$$

This new route visits every other stop. After seven $G$-steps, the total movement is

$$7G=7(2P)=14P=\mathcal{O}.$$

No earlier $G$-step returns to $\mathcal{O}$, so

$$\operatorname{ord}(G)=7.$$

The seven visited stops form $\langle G\rangle$. This is a proper subgroup: it lies inside the fourteen-point curve group but does not contain every curve point. The odd multiples $P,3P,5P,\ldots$ belong to the complete group but are skipped by the $G$-route.

0.5. Why Subgroup Orders Divide the Curve Order

The route analogy also suggests why subgroup sizes cannot be arbitrary. A subgroup must fit evenly inside the complete finite group: translated copies of the subgroup partition the complete group into equal-sized sets.

Lagrange's theorem states this precisely: in a finite group, the number of elements in a subgroup divides the number of elements in the complete group.

The notation

$$a\mid b$$

is read “$a$ divides $b$.” It means that $b$ can be divided by $a$ without leaving a remainder. Equivalently, there is some integer $c$ such that

$$b=ca.$$

For example,

$$7\mid14$$

because $14=2\cdot7$. In contrast,

$$4\nmid14$$

because no integer multiplied by $4$ equals $14$.

Now apply the theorem to an elliptic-curve point $R$. Repeatedly adding $R$ produces the subgroup $\langle R\rangle$, and that subgroup contains exactly $\operatorname{ord}(R)$ points. The complete curve group contains $\#E(\mathbb{F}_p)$ points. Lagrange's theorem therefore tells us that

$$\operatorname{ord}(R)\mid\#E(\mathbb{F}_p).$$

Read this as:

The order of $R$ divides the order of the complete curve group.

Our curve has $14$ points, whose positive divisors are $1$, $2$, $7$, and $14$. Therefore, a point on this curve can only have one of those orders. Lagrange's theorem rules out an order such as $4$, although it does not guarantee that a point of every possible divisor order must exist.

Our three useful step sizes make this visible:

• Adding $P$ visits all fourteen stops before returning, so $\operatorname{ord}(P)=14$.
• Adding $G=2P$ visits every other stop, so $\operatorname{ord}(G)=7$.
• Adding $T=7P=(2,0)$ jumps halfway around the route each time. The first step reaches $T$ and the second returns to $\mathcal{O}$, so $\operatorname{ord}(T)=2$.

The last example also connects to the doubling rule from Chapter 6. A point with $y=0$ is its own inverse, so

$$2T=\mathcal{O}.$$

The point orders $14$, $7$, and $2$ all divide the curve order $14$, just as Lagrange's theorem requires.

0.6. The Public Base Point

A cryptographic parameter set designates one public generator of its selected subgroup, conventionally written

$$G=(x_G,y_G).$$

This selected generator is called the base point. It is not secret and is not chosen separately by each user. Its exact coordinates are part of the public curve parameters.

The terms describe two related ideas:

Generator — mathematical property

Its multiples reach every point in the group or subgroup being discussed.

Base point — public role

It is the generator that a parameter set designates for everyone to use.

For our toy parameter set, we choose

$$G=(3,3)$$

as the base point of the order-$7$ subgroup above. Its subgroup order is conventionally named

$$n=\operatorname{ord}(G)=7.$$

The base point generates the selected subgroup $\langle G\rangle$; it does not need to generate the entire curve group.

0.7. Cofactor

Because the subgroup order $n$ divides the curve order, the cofactor

$$h=\frac{\#E(\mathbb{F}_p)}{n}$$

is an integer. Equivalently,

$$\#E(\mathbb{F}_p)=hn.$$

For the selected subgroup of the running curve,

$$h=\frac{14}{7}=2.$$

Think of $h$ as answering: How many equal-sized copies of the selected subgroup fit inside the complete curve group? Here, two seven-point cosets fill the fourteen-point group:

$$\underbrace{14}_{\text{complete curve group}} = \underbrace{2}_{\text{cofactor}} \times \underbrace{7}_{\text{selected subgroup}}.$$

The value $h=2$ therefore does not mean that only two curve points lie outside the subgroup. It counts two equal-sized cosets, one of which is $\langle G\rangle$ itself.

Production curves use an enormous prime $n$ and usually a small cofactor. The running values $n=7$ and $h=2$ reproduce that structure at a scale we can enumerate, but they provide no security.

0.8. The Complete Toy Parameter Set

We can now collect the quantities developed across Chapters 5, 6, and 7. Reading down the table moves from the coordinate system, to the complete curve, to the selected route through that curve:

The curve equation and the values

$$(p,a,b,G,n,h) = (11,1,1,(3,3),7,2)$$

form a complete toy analogue of the public domain parameters used by real elliptic-curve systems.

0.9. The Base Field and the Scalar Field

Our parameter set now contains two different prime numbers that play two different roles:

$$p=11 \qquad\text{and}\qquad n=7.$$

The first prime controls the coordinates of curve points. The second prime controls the scalars that act on the selected subgroup. Keeping those roles separate is essential when reading or implementing elliptic-curve cryptography.

0.9.1. The Base Field $\mathbb{F}_p$: Where Coordinates Live

The curve is defined over the base field $\mathbb{F}_p$. Its coefficients and every affine point coordinate are elements of that field:

$$a,b,x,y\in\mathbb{F}_p.$$

For the running curve, $p=11$, so

$$a,b,x,y\in\mathbb{F}_{11}.$$

In particular, the base point

$$G=(3,3)$$

has coordinates

$$x_G=3\in\mathbb{F}_{11} \qquad\text{and}\qquad y_G=3\in\mathbb{F}_{11}.$$

The point $G$ itself is not a field element. It is an ordered pair of field elements that satisfies the curve equation. More precisely,

$$G\in E(\mathbb{F}_{11}),$$

and because we selected the subgroup generated by $G$,

$$G\in\langle G\rangle\subset E(\mathbb{F}_{11}).$$

Whenever we add points, double a point, or calculate new point coordinates, the coordinate formulas use arithmetic in $\mathbb{F}_{11}$: values are reduced modulo $11$.

0.9.2. The Subgroup Order and the Letter $r$

We named the order of the selected subgroup $n$:

$$n=\operatorname{ord}(G)=7.$$

General ECC specifications commonly use $n$ for this quantity. Pairing-based cryptography and many cryptographic libraries commonly use $r$, especially when emphasizing that the subgroup order is prime. The letters differ, but they can describe the same quantity:

$$r=n=\operatorname{ord}(G).$$

For our selected subgroup,

$$r=7.$$

The defining property of this order is

$$rG=\mathcal{O}.$$

No smaller positive scalar sends $G$ back to $\mathcal{O}$. The value $r$ is therefore both the order of the point $G$ and the number of points in the subgroup $\langle G\rangle$.

0.9.3. The Scalar Field $\mathbb{F}_r$: Where Scalars Live

Because the selected subgroup has prime order $r$, integers modulo $r$ form another finite field:

$$\mathbb{F}_r=\{0,1,\ldots,r-1\}.$$

This is called the scalar field. A scalar $k$ used with the base point belongs to this field:

$$k\in\mathbb{F}_r.$$

For the running subgroup,

$$\mathbb{F}_r=\mathbb{F}_7=\{0,1,2,3,4,5,6\}.$$

Why do scalars wrap around modulo $r$? Because $rG=\mathcal{O}$. Adding $r$ to any scalar does not change the resulting point:

$$\begin{aligned} (k+r)G &=kG+rG\\ &=kG+\mathcal{O}\\ &=kG. \end{aligned}$$

With $r=7$, for example,

$$8G=(1+7)G=G$$

and

$$13G=(6+7)G=6G.$$

The scalar values $0$ through $6$ therefore describe every distinct multiple of $G$. Scalar multiplication connects an element of the scalar field to a point in the subgroup:

$$\underbrace{k}_{\in\mathbb{F}_r} \quad\text{acts on}\quad \underbrace{G}_{\in\langle G\rangle} \quad\text{to produce}\quad \underbrace{kG}_{\in\langle G\rangle}.$$

The operation $kG$ does not mean that $k$ is multiplied by the individual coordinates of $G$. It means that the group point $G$ is repeatedly added, using an efficient scalar-multiplication algorithm.

0.9.4. Two Fields, Two Different Jobs

The base field and scalar field use the same kind of modular arithmetic, but they contain different kinds of values and usually have different moduli:

Base field $\mathbb{F}_p$ — coordinates

Contains the curve coefficients and point coordinates. Coordinate arithmetic is reduced modulo $p$.

Scalar field $\mathbb{F}_r$ — scalars

Contains the numbers that multiply subgroup points. Scalar arithmetic is reduced modulo $r=\operatorname{ord}(G)$.

For the toy parameter set,

The relationship between the two primes comes through the size of the curve group:

$$r\mid\#E(\mathbb{F}_p).$$

In our example,

$$7\mid14.$$

There is no requirement that $r$ divide $p$, and the scalar field is not generally a subset of the base field. Here, $7$ does not divide $11$: $\mathbb{F}_7$ and $\mathbb{F}_{11}$ are separate fields with separate jobs.

Important

Coordinates are reduced modulo $p$. Scalars are reduced modulo $r=\operatorname{ord}(G)$. Mixing up these moduli means performing arithmetic in the wrong field.

0.9.5. How This Prepares Us for Pairings

The subgroup $\langle G\rangle$ in this chapter is a general elliptic-curve subgroup. We do not call it $G_1$ yet, because the names $G_1$ and $G_2$ describe specific roles inside a pairing construction.

Later, Pairing-Based Cryptography will build on the same pattern. A pairing setup has a group called $G_1$ whose points commonly have coordinates in $\mathbb{F}_p$, another group called $G_2$ whose points are commonly represented using an extension field, and scalars for both groups in $\mathbb{F}_r$. This chapter supplies the base-field, scalar-field, subgroup, order, and generator concepts needed to distinguish those objects.

0.10. From a Public Point to Protocols

The choice of $G$ gives every participant the same public starting point. In the simplest prime-order model, a private scalar is selected from

$$1\le k\le r-1,$$

and scalar multiplication produces a public point

$$Q=kG.$$

The complete scalar field includes $0$, but a private key must be nonzero: $0G=\mathcal{O}$ would produce the identity instead of a useful public key. For the toy subgroup, only the six nonzero private scalars $1$ through $6$ are possible, so anyone can recover $k$ by trying every option. Production subgroups instead use an enormous prime order $r$. This gives the elliptic-curve discrete-logarithm problem a prohibitively large search space, while prime order avoids nontrivial smaller subgroups inside $\langle G\rangle$.

Construct $E(\mathbb{F}_p)$

Count the complete curve group $\#E$

Follow the scalar cycle of a point

Identify its generated subgroup

Select a public base point $G$

Record its order $r$ and cofactor $h$

Distinguish the base field $\mathbb{F}_p$ from the scalar field $\mathbb{F}_r$

This completes the mathematical foundation. Continue with Elliptic-Curve Protocols to use these objects to build keys, signatures, key agreement, encryption, and threshold protocols.