Groups


Algebraic groups

An algebraic group is a fundamental concept in mathematics, especially relevant in cryptography. Security of many cryptographic schemes relies on a good choice of a group and all its parameters.

This is the first post in a series about algebraic groups. In this post, we explore the definition of group and present several easily approachable examples of all group axioms.

In the next posts, we will discuss group generators and algorithms allowing to find them.

Definition

We define a group as a nonempty, finite or infinite set $ G $ equipped with a binary operation $ \cdot $ that satisfies the following group conditions (axioms):

Closure

If $ a $ and $ b $ belongs to $ G $, then the result of $ a \cdot b $ also belongs to $ G $.

Associativity

For all $ a, b, c \in G $, the binary operation $ \cdot $ is associative: $ (a \cdot b) \cdot c = a \cdot (b \cdot c) $

Identity element

There exists an element $ I \in G $, called identity element, such that $ I \cdot a = a \cdot I = a $ for all $ a \in G $.
In other words, it is a neutral element of a set which leaves other elements unmodified when combined with them.

Inverse element (Invertibility)

For each $ a \in G $ there exists an element $ a^{-1} \in G $ such that $ a \cdot a^{-1} = a^{-1} \cdot a = I $, where $I$ is an identity element.

Finite groups and element order

A group is called $ finite $ if it has a finite number of elements. The number of elements in a group $ G $ is called the order of a group (or cardinality of a group) and is denoted by $ |G| $.

The order of an element $ a $, where $ a \in G $ is the least positive integer $ n $ such that $ a^n = I $, where $ I $ denotes the identity element of the group and $ a^n $ is the application of the operation $ \cdot $ to $ n $ copies of $ a $.

Examples

Below are some examples to help illustrate all of the group properties. Some examples present algebraic groups and some examples presents sets which are not algebraic groups because not all group axioms are satisfied.

Set $ S = \{ 1, 0, 1 \} $ under addition

Let’s first create a Cayley table for our finite set $ S $:

| +    | 1 | 0 | 1 |
| ---  | - | - | - |
| 1    | 2 | 1 | 2 |
| 0    | 1 | 0 | 1 |
| 1    | 2 | 1 | 2 |

Closure condition is not satisfied because $ 1 + 1 = 2 $ and $ 2 \notin S $. Thus, $ S = \{ 1, 0, 1 \} $ under addition is not a group.

Set $ S = \{ -1, 0, 1 \} $ under multiplication

Let’s start with a Cayley table for the finite set $S$:

| *     | -1 |  0 |  1 |
| ---   | -- | -- | -- |
| -1    |  1 |  0 | -1 |
|  0    |  0 |  0 |  0 |
|  1    | -1 |  0 |  1 |

Closure condition is satisfied. We can see that for any $ a, b \in S $, the result of $ a * b $ also belongs to $ S $.

Associativity condition is satisfied:

  • $(-1 * 0) * 1 = -1 * (0 * 1)$
  • $(0 * -1) * 1 = 0 * (-1 * 1)$
  • $(1 * 0) * (-1) = 1 * (0 * (-1))$

Identity element condition is satisfied. There is an identity element $I = 1$:

  • $1 * (-1) = -1$
  • $1 * 0 = 0$
  • $1 * 1 = 1$

Invertibility condition is not satisfied, though:

  • $-1 * (-1) = I = 1$
  • $1 * 1 = I = 1$
  • However, there is no $ a = 0^{-1} $ such that $ 0 * a = 1 = I $

We see that $ S = \{ -1, 0, 1 \} $ under multiplication does not meet Invertibility condition, hence it is not a group.

Set $ S = \{ 5, 15, 25, 35 \} $ under multiplication modulo 40

As always, let’s start with a Cayley table for the finite set $S$:

| *mod 40 |  5  |  15  |  25 | 35  |
| ---     | --- | ---  | --- | --- |
| 5       | 25  | 35   | 5   | 15  |
| 15      | 35  | 25   | 15  | 5   |
| 25      | 5   | 15   | 25  | 35  |
| 35      | 15  | 5    | 35  | 25  |

Closure condition is satisfied. For any $ a, b \in S $, the result of $ (a * b) \pmod{40} $ also belongs to $ S $.

Associativity condition is satisfied. We can prove multiplication modulo $n$ is associative from the definition of congruence relation:

Two integers $a$ and $b$ are called congruent modulo $n$, written $ a \equiv b \pmod n $, if they have the same remainder when divided by $ n $. Since the multiplication is associative: $ x(yz) = (xy)z $, then for $ a = x(yz) $ and $ b = (xy)z $ we know that $a$ and $b$ have the same remainder modulo $n$, thus $ x(yz) \equiv (xy)z \pmod n $.

Here are a few examples:

  • $(5 * 15) * 25 \equiv 5 * (15 * 25) \mod 40$
  • $(15 * 5) * 25 \equiv 15 * (5 * 25) \mod 40$
  • $(25 * 15) * 5 \equiv 25 * (15 * 5) \mod 40$
  • $(5 * 15) * 35 \equiv 5 * (15 * 35) \mod 40$
  • $(15 * 5) * 35 \equiv 15 * (5 * 35) \mod 40$

Identity element condition is satisfied. There is an identity element $ I = 25 $:

  • $(25 * 5) \bmod 40 = 5$
  • $(25 * 15) \bmod 40 = 15$
  • $(25 * 25) \bmod 40 = 25$
  • $(25 * 35) \bmod 40 = 35$

Invertibility condition is satisfied. For each $ a \in S $ there exists an inverse element. In the case of this group, $ a^{-1} = a $:

  • $(5 * 5) \bmod 40 = 25$
  • $(15 * 15) \bmod 40 = 25$
  • $(25 * 25) \bmod 40 = 25$
  • $(35 * 35) \bmod 40 = 25$

We can see that all the conditions (closure, associativity, identity element, invertibility) are satisfied. Therefore, our set $ S = \{5, 15, 25, 35\} $ under multiplication modulo 40 is a group. There are four elements in S, so the group order $|G| = 4$. The order of an element $ a \in S $ is the least positive integer n, such that $ a^n = I $. Since $ a^{-1} = a $, then order $ n = 2 $ applies for all the elements in this group.

  • $5^2 \bmod 40 = 25$
  • $15^2 \bmod 40 = 25$
  • $25^2 \bmod 40 = 25$
  • $35^2 \bmod 40 = 25$

Group under addition and multiplicative group modulo N

Among the groups that are used in cryptography, we should distinguish two special kind: a group under addition modulo $N$ and a multiplicative group modulo $N$.

We associate to any positive integer N the following two sets:

$ Z_N = \{ 0, 1, 2 … N - 1 \}$

$ Z_N^* = \{ i \in Z : 1 \le i \le N-1 : gcd(i, N)=1 \}$ where $ gcd $ stands for greatest common divisor.

For any positive integer $ N $, $ Z_N $ is a group under addition modulo $ N $, and $ Z_N^* $ is a group under multiplication modulo $ N $ and is called a multiplicative group of integers modulo $ N $.

For example, for $ N = 12 $, we have:

$ Z_N = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \} $

$ Z_N^* = \{1, 5, 7, 11 \} $

And for $N=9$ we have:

$ Z_N = \{0, 1, 2, 3, 4, 5, 6, 7, 8 \} $

$ Z_N^* = \{1, 2, 4, 5, 7, 8 \} $

What’s next

This post is the first one in the series about algebraic groups. As you might already notice, we need some mathematical tools to operate on larger groups.

In the next posts, we will cover group generators and algorithms allowing to find those generators along with some source code snippets.