Factor Groups

The fundamental theorem of finite cyclic groups

If $G$ is a finite cyclic group of order $n$, then every subgroup $G'$ of $G$ is finite and cyclic, and the order $G'$ is a factor of $n$. Moreover for each factor $k$ of $n$, $G$ has exactly one subgroup of order $k$.

Notation

If $G$ is a finite cyclic group of order $n$ and $k$ is a factor of $n$, then we write $G[k]$ for the unique finite cyclic group which is the order $k$ subgroup of $G$, and call it a factor group of $G$.

Cofactor Clearing

Cryptographic protocols often assume the existence of finite cyclic groups of prime order. However some real-world implementations of those protocols are not defined on prime order groups, but on groups where the order consist of a (usually large) prime number that has small cofactors. In this case, a method called cofactor clearing has to be applied to ensure that the computations are not done in the group itself but in its (large) prime order subgroup.

To understand cofactor clearing in detail, let $G$ be a finite cyclic group of order $n$, and let $p$ be a factor of $n$ with associated factor group $G[p]$. We can project any element $g ∈ G[p]$ onto the neutral element $e$ of $G$ by multiplying $g$ $p$-times with itself:

$$g^p = e$$

Consequently, if $h = n / p$ is the cofactor of $p$ in $n$, then any element from the full group $g ∈ G$ can be projected into the factor group $G[p]$ by multiplying $g$ $h$-times with itself. This defines the following map, which is often called cofactor clearing in cryptographic literature:

$$(·)^h : G → G[p] : g → g^h$$