## 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.