In my previous post I introduced the idea of a group, which is an abstract mathematical concept that is defined as a set with a binary operation fulfilling a few mathematical properties. Many cryptography primitives are based on the mathematics of groups such as asymmetric encryption, digital signatures and zero knowledge proofs, which we will cover later. In this post I introduce rings and fields and explain how they relate to groups.
Definition of a Ring
A ring is an an algebraic type that is defined over addition, subtraction and multiplication but not division. It is also a group and therefore is also a set with a binary operation (specifically over addition). More precisely a ring is an abelian group over addition and a monoid under multiplication and distributive for multiplication with respect to addition. It fulfils the mathematical properties defined in the comments below. In the sample code below I define a Rust trait Ring which extends AbelianGroup and Monoid and which defines the add, substract and multiply methods. Each method takes an element type E which represents an element in the set and returns another element after applying the operation.
/// A Ring is an abelian group over addition, a monoid under multiplication and distributive
/// for multiplication with respect to addition.
///
/// It has the following properties over multiplication:
/// Closure - a x b = c where a, b, and c are in the set
/// Associativity - a x (b x c) = (a x b) x c
/// Identity - a x I = a
///
/// Multiplication is distributive with respect to addition:
/// Left distributive - a x (b + c) = (a x b) + (a x c)
/// Right distributive - (b + c) x a = (b x a) + (c x a)
trait Ring<E>: AbelianGroup<Addition, E> + Monoid<Multiplication, E> {
/// Supports addition
fn add(&self, e1: E, e2: E) -> E;
/// Supports subtraction which is the same as adding the inverse
fn subtract(&self, e1: E, e2: E) -> E;
/// Supports multiplication
fn multiply(&self, e1: E, e2: E) -> E;
}Example of a Ring
Here is an example of a ring, the natural numbers mod n. The natural numbers are basically the non-negative numbers and mod n means we are using modular arithmetic to restrict the numbers in the set to have elements less than n. You can read more about modular arithmetic here for a more detailed explanation. Note that we are not always able to divide the natural numbers mod n because when n is not prime some elements in the set may not have an inverse and so calculating a modular inverse would not always be possible.
In the code below we create a struct NaturalNumbersModN which has a single parameter representing the size of the ring n. Next we implement the Group trait for addition, setting the identity element to zero and the Monoid trait setting the identity element to 1. The add method is implemented by calling the Group apply method, substract is implemented similarly except we add the inverse. multiply is implemented by calling the Monoid apply method.
/// The natural numbers mod n form a ring.
struct NaturalNumbersModN(u32);
impl AbelianGroup<Addition, u32> for NaturalNumbersModN {}
impl Group<Addition, u32> for NaturalNumbersModN {
fn apply(&self, e1: u32, e2: u32) -> u32 {
(e1 + e2) % self.0
}
fn identity(&self) -> u32 {
0
}
fn inverse(&self, e: u32) -> u32 {
self.0 - e % self.0
}
}
impl Monoid<Multiplication, u32> for NaturalNumbersModN {
fn apply(&self, e1: u32, e2: u32) -> u32 {
(e1 * e2) % self.0
}
fn identity(&self) -> u32 {
1
}
}
impl Ring<u32> for NaturalNumbersModN {
fn add(&self, e1: u32, e2: u32) -> u32 {
<dyn AbelianGroup<Addition, u32>>::apply(self, e1, e2)
}
fn subtract(&self, e1: u32, e2: u32) -> u32 {
<dyn AbelianGroup<Addition, u32>>::apply(self, e1, self.inverse(e2))
}
fn multiply(&self, e1: u32, e2: u32) -> u32 {
Monoid::apply(self, e1, e2)
}
}Next we test out the code using the natural numbers mod 4, which means our ring has a set with elements 0, 1, 2 and 3. The code below tests the add, substract and multiply methods. Notice that when we add 3 and 2 we get 1 instead of 5 because the numbers wrap around. The substract and multiply methods work similarly always returning an element in the set between 0 and 3.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn run_natural_numbers_modn() {
let ring = NaturalNumbersModN(4);
let result = ring.add(3, 2);
assert_eq!(1, result);
let result = ring.subtract(3, 3);
assert_eq!(0, result);
let result = ring.multiply(2, 3);
assert_eq!(2, result);
}
}So now you have a basic idea of what a ring is and the operations it defines. Next I introduce fields and explain how they relate to rings and groups.
Definition of a Field
A field is an an algebraic type that is defined over addition, subtraction, multiplication and division. It is also a group and therefore is also a set but in this case with two binary operations (specifically over addition and multiplication). Put another way, a field is a ring which is also defined over division. More precisely a field is an abelian group over addition and an abelian group over multiplication and is distributive for multiplication with respect to addition.
It fulfils the mathematical properties defined for a group under both addition and multiplication. In the sample code below I define a Rust trait Field which extends AbelianGroup for both the Addition and Multiplication operations and which defines the add, substract, multiply and divide methods. Each method takes an element type E which represents an element in the set and returns another element after applying the operation.
/// A Field is an abelian group over addition and multiplication and distributive
/// for multiplication with respect to addition.
trait Field<E>: AbelianGroup<Addition, E> + AbelianGroup<Multiplication, E> {
/// Supports addition
fn add(&self, e1: E, e2: E) -> E;
/// Supports subtraction which is the same as addition with the inverse
fn subtract(&self, e1: E, e2: E) -> E;
/// Supports multiplication
fn multiply(&self, e1: E, e2: E) -> E;
/// Supports division where the divisor is not equal to zero
fn divide(&self, e1: E, e2: E) -> E;
}Example of a Field
In this example we create a prime field using the natural numbers mod p where p is a prime. This is an example of a finite field because the number of elements in the set are bounded. It just so happens that if a prime number is selected for the modulus we have a field. This is because division is always defined due to every element in the set having an multiplicative inverse. In the code below I define a new struct PrimeField which has a single parameter for the modulus p. The new method is used to construct new instances of the type and uses a library to check if the number is a prime.
Next we implement the Group traits for addition and multiplication. The inverse method for multiplication is defined using a trial and error approach which is not efficient, where we check if each inverse candidate multiplied by the number is equal to 1 until we get a match. In a future post I will show a better way to calculate multiplicative inverses using the Extended Euclidean algorithm. We then implement the add, subtract, multiply and divide methods for the Field trait which each call their respective additive and multiplicative group operations which have already been defined.
/// The natural numbers mod p where p is a prime form a field.
struct PrimeField(u32);
impl PrimeField {
fn new(modulus: u32) -> Self {
if !primes::is_prime(modulus.into()) {
panic!("modulus is not a prime")
}
PrimeField(modulus)
}
}
impl AbelianGroup<Addition, u32> for PrimeField {}
impl Group<Addition, u32> for PrimeField {
fn apply(&self, e1: u32, e2: u32) -> u32 {
(e1 + e2) % self.0
}
fn identity(&self) -> u32 {
0
}
fn inverse(&self, e: u32) -> u32 {
self.0 - e % self.0
}
}
impl AbelianGroup<Multiplication, u32> for PrimeField {}
impl Group<Multiplication, u32> for PrimeField {
fn apply(&self, e1: u32, e2: u32) -> u32 {
(e1 * e2) % self.0
}
fn identity(&self) -> u32 {
1
}
fn inverse(&self, e: u32) -> u32 {
if e % self.0 == 0 {
panic!("Cannot calculate inverse for zero")
}
// This trial and error method to calculate the inverse is not efficient.
// In another post we will use the Extended Euclidean Algorithm to solve this instead.
for i in 0..self.0 {
if (e * i) % self.0 == 1 {
return i;
}
}
panic!("No inverse found");
}
}
impl Field<u32> for PrimeField {
fn add(&self, e1: u32, e2: u32) -> u32 {
<dyn AbelianGroup<Addition, u32>>::apply(self, e1, e2)
}
fn subtract(&self, e1: u32, e2: u32) -> u32 {
let inverse = <dyn AbelianGroup<Addition, u32>>::inverse(self,e2);
<dyn AbelianGroup<Addition, u32>>::apply(self, e1, inverse)
}
fn multiply(&self, e1: u32, e2: u32) -> u32 {
<dyn AbelianGroup<Multiplication, u32>>::apply(self, e1, e2)
}
fn divide(&self, e1: u32, e2: u32) -> u32 {
let inverse = <dyn AbelianGroup<Multiplication, u32>>::inverse(self,e2);
<dyn AbelianGroup<Multiplication, u32>>::apply(self, e1, inverse)
}
}In the sample code below we test out the PrimeField using 11 as the prime modulus. We test the add, substract, multiply and divide methods which each behave as expected and return elements in the set after applying the respective group operation under addition or multiplication. Finally we test that we can divide by any number in the field by looping through all possible divisors from 1 to 10 and verify that the code doesn’t panic with ‘No inverse found’, which would occur if a particular element had no multiplicative inverse.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn run_prime_field() {
let field = PrimeField::new(11);
let result = field.add(3, 10);
assert_eq!(2, result);
let result = field.subtract(1, 3);
assert_eq!(9, result);
let result = field.multiply(2, 10);
assert_eq!(9, result);
let result = field.divide(10, 2);
assert_eq!(5, result);
// Every element in the field apart from zero has an inverse
for i in 1..11 {
let _result = field.divide(10, i);
}
}
}Conclusion
In this post we continued on the topic of group theory by introducing two new algebraic types; rings and fields. We defined a Ring trait to help explain the concept of a ring and created an example implementation using the natural numbers mod n which is always defined over addition, subtraction and multiplication. We then defined a Field trait while explaining the definition of a field and how it relates to groups and rings. We then created an example field over the natural numbers mod p by defining a new type PrimeField which implements the respective group operations over addition and multiplication. In a future post I will show how prime fields are used to implement certain cryptographic primitives such as the Diffie-Hellman key exchange so stay tuned for more updates.