I’m planning to do a set of posts on the mathematics used in cryptography and so I will be covering topics such as group theory, number theory, modular arithmetic, polynomials and eventually elliptic curves. This is the first post in the series which will give a very basic introduction to group theory and groups.
What is Group Theory?
Group theory is a branch of mathematics in the area of abstract algebra that studies the symmetries that recur throughout mathematics. A group is a very abstract concept and a generalisation of some other algebraic types such as rings and fields which I will explain more in a future post. It turns out that the patterns and laws described by group theory show up in number theory, algebraic equations and geometry. Most importantly cryptography relies on group theory and finite fields for primitives such as the Diffie-Hellman key exchange, RSA encryption and also for zero knowledge proofs.
So what is a group?
Definition of a Group
A group is defined as a set with a binary operation that satisfies a few properties; closure, associativity, identity and invert-ability. A set is just a collection of elements and the binary operation is not yet defined. It could be addition or multiplication but the definition of a group is more abstract than that and so it could also be geometric rotations over a shape for example.
In the sample code below I define a Rust trait Group which models a group. It takes a type T which must implement the Operation marker trait. The comments describe the properties which much be satisfied by the group. I represent the binary operation as ‘.’ in the comments which is implemented by the apply method which takes two elements and returns another element. The identity method should return the identity element for the group and the inverse method should return the inverse of the given element.
/// A group is a set and a binary operation (denoted by '.') which satisfies the following properties:
/// Closure - a . b = c where a, b, and c are in the set
/// Associativity - a . (b . c) = (a . b) . c
/// Identity - a . I = a
/// Inverse - a . a^-1 = I
pub trait Group<T: Operation, E> {
/// The binary operation which takes elements e1 and e2 of type E and returns the result
fn apply(&self, e1: E, e2: E) -> E;
/// Returns the identity element
fn identity(&self) -> E;
/// Returns the inverse of element e
fn inverse(&self, e: E) -> E;
}Definition of an Abelian Group
An abelian group is a group that also supports the commutativity property (in addition to the other group properties) which basically means the binary operation can be applied in any order to the elements a and b and the result will be the same. I define it here as a marker trait for completeness which extends the Group trait even though no additional methods are required.
/// A type which supports commutativity in addition to the standard group properties:
/// Commutativity - a . b = b . a
pub trait AbelianGroup<T: Operation, E>: Group<T, E> {}Definition of a Monoid
A monoid is similar to a group except that elements may not have an inverse and it only supports the associativity and identity properties. It once again is a very abstract concept having a set and a binary operation. I define the Monoid trait below with an apply and identity method but no inverse method. I will be using this type later when defining a trait for a ring in a future post.
/// A monoid is a set and a binary operation (denoted by '.') which satisfies the following properties:
/// Associativity - a . (b . c) = (a . b) . c
/// Identity - a . I = a
pub trait Monoid<T: Operation, E> {
/// The binary operation which takes elements e1 and e2 of type E and returns the result
fn apply(&self, e1: E, e2: E) -> E;
/// Returns the identity element
fn identity(&self) -> E;
}Example Operations
Next I define the Operation marker trait and implement Addition and Multiplication types to be used as markers. This is required so that a type can implement the trait over multiple operations. For example we might want to implement the Group trait under both Addition and Multiplcation.
/// Marks the Monoid and Group traits with a type
pub trait Operation {}
pub struct Addition;
pub struct Multiplication;
impl Operation for Addition {}
impl Operation for Multiplication {}Example of a Group
Finally here is a very simple example of a group, the set of integers under addition. In mathematics the set of integers is defined as the whole numbers, positive and negative, including zero. With addition the set of integers forms a group because all the group properties are for-filled. The identity element is zero and the inverse is the negation of the given element. We also implement the AbelianGroup trait for our new AdditiveIntegers type because integer addition is commutative. You can check for yourself to verify that each of the group properties are for-filled with this implementation.
/// Integers under addition form a group where plus (+) is the group operation, zero is the identity
/// and negation (-) can be used to get the inverse of an element
struct AdditiveIntegers();
impl Group<Addition, i32> for AdditiveIntegers {
fn apply(&self, a: i32, b: i32) -> i32 {
a + b
}
fn identity(&self) -> i32 {
0
}
fn inverse(&self, a: i32) -> i32 {
-a
}
}
// Integers under addition supports commutativity
impl AbelianGroup<Addition, i32> for AdditiveIntegers {}Next we test out the code by creating a new instance of the AdditiveIntegers group. Then we test each of the methods to confirm that they each work as expected and for-fill the required properties, closure, associativity, identity, invert-ability and commutativity.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn run_additive_integers() {
let group = AdditiveIntegers();
let a: i32 = 10;
let b: i32 = 20;
let c: i32 = 30;
// Closure - a . b = c where a, b, and c are in the set
let result: i32 = group.apply(a, b);
assert_eq!(c, result); // result is an integer so in the set
// Associativity - a . (b . c) = (a . b) . c
assert_eq!(group.apply(a, group.apply(b, c)),
group.apply(group.apply(a , b), c));
// Identity - a . I = a
assert_eq!(group.apply(a, group.identity()), a);
// Inverse - a . a^-1 = I
assert_eq!(group.apply(a, group.inverse(a)), group.identity());
// Commutativity - a . b = b . a
assert_eq!(group.apply(a, b), group.apply(b, a));
}
}Conclusion
This post introduced group theory and explained the definition of a group, abelian group and monoid. We then created an example group, the integers over addition and showed an example usage. Future posts will cover topics such as rings and fields which will help explain why I’ve created these group types and will further explain these group theory concepts.