Group
Tags: 100daystooffload, math, cryptography, fsharp
Published: 2023-07-28 05:18:50

In group theory there is an algebraic structure called [group](https://en.wikipedia.org/wiki/Group_(mathematics)). This is a building block when trying to understand cryptography because of the [discrete logarithmic problem](https://en.wikipedia.org/wiki/Discrete_logarithm).

One of the more familiar groups is the set of integers, Z = {..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ...} together with addition, however lets use another set to explain and define the group term. To guide us through this we will use some F# code.

First a group (the math symbol for a group is G) needs to be a set of elements and can't be empty;

```fsharp
let g = Set({ 0 .. 5 })
// val g: Set<int> = set [0; 1; 2; 3; 4; 5]

// or
let g = Set.ofList [-2; 3; 7]
// val g: Set<int> = set [-2; 3; 7]

// or
let g = Set.ofList [0; 1; 2]
// val g: Set<int> = set [0; 1; 2]

// not a valid set
let g = Set.ofList List.empty<int>
// val g: Set<int> = set []
```

__Note:__ The code examples above shows a special type of groups, _finite group_, it's simpler to represent them in code than the set of integers, Z, which is non-finite.

The set is not enough, there needs to be a binary operator (group operator) together with the set, like addition for example. The character, •, represents the group operator in math literature. A group could therefore be expressed like this, G •.

There are also some rules/facts for the group (the group axioms) that needs to be defined.

* __Closure:__ If we apply the group operation with any of the elements in the group, then the result must be an element in the group set.

```fsharp
let g = Set({ 0 .. 5 })
let a = 1
let b = 2

let c = a + b  // + is used here as the group operator, •

// Check the closure axiom
g |> Set.contains c
// val it: bool = true
```

* __Associativity:__ The order the group operator is applied should not matter.

```fsharp
let a = 0
let b = 1
let c = 2

(a + b) + c = a + (b + c)
//val it: bool = true
```

* __Identity element:__ There has to exist an element in the set that can be used with the operator and all other elements so that the result will equal the other element.

```fsharp
let g = Set({ 0 .. 5 })
let e = 0 // the identity element

g |> Set.forall (fun elem -> elem + e = elem)
// val it: bool = true
```

* __Inverse element:__ There has to exist an inverse element for each element so that when these two elements are applied together with the operator it will produce the identity element.

```fsharp
let g = Set({ -2 .. 2 })
let e = 0 // the identity element

-2 + 2 = e
// val it: bool = true
-1 + 1 = e
// val it: bool = true
```

As we can see some of these examples will not comply 100% to the axioms, closure and inverse element has some problems in the examples above. This is because of the sets we have been using, the addition operator works fine when the group is the set of integers mentioned in the beginning.

```fsharp
let g = Set({ 0 .. 4 })
let c = 3 + 4

// Check the closure axiom, c = 7 which is not in the set
g |> Set.contains c
// val it: bool = false

let e = 0 // identity element
let a = 1

// What about the inverse element
// a + b = e
// there is no value for b here to make this true
```

To solve this we need to change how we implement the group operator. In this case addition. The solution is to use [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic) instead.

```fsharp
let g = Set({ 0 .. 4 })                   
// val g: Set<int> = set [0; 1; 2; 3; 4]

// redefine addition to use modular arithmetic
let (+) x y = (x + y) % g.Count

let c = 3 + 4
// val c: int = 2

// Check the closure axiom
g.Contains(c)
// val it: bool = true

let e = 0 // identity element
let a = 1
let b = 4

// Check the inverse element axiom
a + b = e
// val it: bool = true
```

Now it looks better and the code comply to all axioms. The  code above has worked with an additive group. There are also some groups that has an extra condition, __commutative__, which makes it an [abelian group](https://en.wikipedia.org/wiki/Abelian_group).

```fsharp
let g = Set({ 0 .. 4 })                   

// redefine addition to use modular arithmetic
let (+) x y = (x + y) % g.Count

let a = 1
let b = 4

// Check the commutative condition
a + b = b + a
// val it: bool = true
```

We could change the group operator to multiplication (modular multiplication) instead and then it is a multiplicative group (it needs to use another identity element too, 1), but there is a gotcha here. The set has to be integers modulo p, where p is any prime number. This is one of the reason that prime numbers are so common in cryptography. The code below shows an example of a set that would not work in a group.

```fsharp
let g = Set({ 0 .. 5 }) // g.Count = 6 which is not a prime                 

// redefine multiplication to use modular arithmetic
let (*) x y = (x * y) % g.Count
```

The problem would arise when trying to fulfill the inverse element axiom.

The multiplicative groups are crucial to public-key cryptography, for example, the [Diffie–Hellman](https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange) protocol uses the discrete logarithm.