Stefan AlfboIn group theory there is an algebraic structure called group. This is a building block when trying to understand cryptography because of the discrete logarithmic problem.
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;
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.
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.
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.
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.
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.
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 instead.
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.
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.
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 protocol uses the discrete logarithm.
