Every Element Is Subgroup Generator

EC Cryptography Tutorials - Herong's Tutorial Examples

∟Every Element Is Subgroup Generator

This section describes the fact that every element in an finite Abelian group is a subgroup generator. The order of the generated subgroup is the same as the order of the element.

Another nice fact of an finite Abelian Group is that every element is a subgroup generator, which can be used to generate a subgroup.

To prove this fact, let's express it as:

Given an finite group G and any element P,
the following element set is a subgroup generated by P:
   S = {P, 2P, 3P, ..., (n-1)P, nP=0}
where n is the order of the element P.

Now we can verify if subgroup S satisfies the 5 rules of Abelian Group or not.

1. Closure:

If I = iP and J = jP are in S,
Then K = I + J = iP + jP = (i+j)P is in S

Proof:
   If i+j <= n, K = (i+j)P is in S by definition
   If i+j > n and i+j < 2n, we have:
      k = n - (i+j), where k > 0 and k < n
      i+j = n+k
      K = (i+j)P = (n+k)P = nP + kP = kP, since nP = 0
      K = kP must be in S, because k < n

2. Commutativity:

If I = iP and J = jP are in S,
Then I + J = J + I

Proof:
   I and J are elements in the parent group, so:
      I + J = J + I, Commutativity of the parent group

3. Associativity:

If I = iP, J = jP and K = kP are in S,
Then (I + J) + K = I + (J + K)

Proof:
   I, J and K are elements in the parent group, so:
      (I + J) + K = I + (J + K), Associativity of the parent group

4. Identity Element:

If I = iP is in S,
Then iP = nP = iP

Proof:
   iP is an element in the parent group and 0 is the identity element, so:
      iP + nP = iP + 0 = iP, where i = 1, 2, ..., n-1

5. Symmetry:

If I = iP is in S, there is j exists, such that:
   iP + jP = 0

Proof:
   i <= n by definition
   If i = n, then
      j = n, and
      iP + jP = nP + nP = 0 + 0 = 0
   If i < n, then
      j = n - i,
      iP + jP = iP + (n-i)P = nP = 0