# Learn you Galois Fields for Great Good (03)

Navigation | first | previous | next

## Implementing GF(p)

This is part 3 of a series on Abstract Algebra. In this part, we'll implement the GF(p) fields we discussed last time.

### Source Code: `src/gf_p.rs`

#### An implementation of GF(p) where p is a prime number

We will implement addition, subtraction, multiplication, and division using operator-overloading so we can use the normal operators: +, -, *, /

``````use std::ops::{Add, Mul, Sub, Div};
``````

Rust supports Const Generics, but that adds a lot of extra syntax noise which may be distracting for readers without a background in Rust or C++.

Instead, we'll just define a simple constant. If you'd like to explore a `GF(p)` field for a different prime, just change the number below. You are responsible for ensuring that the number is actually prime. By default, we'll use `GF(5)`:

``````pub const P: u8 = 5;
``````

The type we use to represent a number in `GF(p)` is just an unsigned 8-bit integer (`u8`). This design will allow for prime fields up to size `251` (the largest prime that fits in 8-bits). We will also tell Rust that its okay to copy (`Clone` & `Copy`) and to compare two numbers via equality (`PartialEq`)

``````#[derive(Debug, Clone, Copy, PartialEq)]
pub struct GF(u8);
``````

Constructing a new number in `GF(p)` is easy: we just need to ensure it's within the set `{0, 1, ..., p-1}`

``````impl GF {
pub fn new(val: u8) -> GF {
assert!(val < P);
GF(val)
}
pub fn value(&self) -> u8 {
self.0
}
}
``````

Now we implement addition via simple modular arithmetic: `(a + b) % p`. But we need to take care to avoid 8-bit overflow, so we do the math in 16-bit (`u16`) and then apply the modulus operation.

``````impl Add<GF> for GF {
type Output = GF;
fn add(self, rhs: GF) -> GF {
let a = self.0 as u16;
let b = rhs.0 as u16;
let p = P as u16;
GF::new(((a + b) % p) as u8)
}
}
``````

Negation (or additive-inverse) is fairly straight-forward also.

Given `a`, we want to solve for `neg(a)` in:

`a + neg(a) == 0 (mod p)`

It seems like the answer would be:

`neg(a) = p - a`

But if `a == 0`, then we'd compute `neg(a) = p` which is not a valid number.

This has an easy fix though:

`neg(a) = (p - a) % p`

``````impl GF {
pub fn negate(self) -> GF {
GF::new((P - self.0) % P)
}
}
``````

Now, we can easily implement subtraction in terms of addition and negation since: `a - b = a + (-b)`

``````impl Sub<GF> for GF {
type Output = GF;
fn sub(self, rhs: GF) -> GF {
self + rhs.negate()
}
}
``````

#### Multiplication and Division

Now we implement multiplication via simple modular arithmetic: `(a * b) % p`. But we need to take care to avoid 8-bit overflow, so we do the math in 16-bit (`u16`) and then apply the modulus operation.

``````impl Mul<GF> for GF {
type Output = GF;
fn mul(self, rhs: GF) -> GF {
let a = self.0 as u16;
let b = rhs.0 as u16;
let p = P as u16;
GF::new(((a * b) % p) as u8)
}
}
``````

Multiplicative inverses are the trickiest operation in this field. We will implement them by brute force. If we've constructed a proper field, then each number will have an inverse. If we try all numbers, one will succeed.

Notice the `Result<>` type here. This is Rust's way of returning errors. We need to use a `Result<>` here since the number 0 has no inverse and need to communicate that the operation has failed.

Faster approaches exist (e.g. The Extended Euclidean Algorithm), but for a first implementation we will avoid adding that complexity. We'll discuss faster methods in later sections.

``````impl GF {
pub fn invert(self) -> Result<GF, String> {
// Important: Zero has no inverse, it's invalid
if self.0 == 0 {
return Err("Zero has no inverse".to_string());
}
// Scan the numbers {1, 2, ..., P-1} until we find the inverse
for x in 1..P {
let candidate = GF::new(x);
if self * candidate == GF::new(1) {
return Ok(candidate); // Found!
}
}
unreachable!("Every non-zero number has an inverse");
}
}
``````

Similarly to subtraction, we can implement division in terms of multiplication and inversion since: `a / b = a * inv(b)`

Notice again that we use a `Result<>` to communicate that division by zero will fail

``````impl Div<GF> for GF {
type Output = Result<GF, String>;
fn div(self, rhs: Self) -> Result<GF, String> {
// Important: Cannot divide by zero
if rhs.0 == 0 {
return Err("Cannot divide by zero".to_string());
}
Ok(self * rhs.invert().unwrap())
}
}
``````

#### Some final things

Rust as a language doesn't implicitly assume much about new types so we have to explicitly tell it how to do a few more-or-less trivial things.

We need to tell Rust how to print these new numbers to the screen. We will just print them out as ordinary integers.

``````impl std::fmt::Display for GF {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
``````

And, we need to tell Rust how to convert strings into our field's numbers.

``````impl std::str::FromStr for GF {
type Err = String;
fn from_str(s: &str) -> Result<GF, String> {
let num: u8 = s.parse().map_err(|_| format!("Not an 8-bit integer"))?;
// Return an error if the number is too big for the field
if num >= P {
return Err(format!("Number too large, got {}, but limit is {}", num, P-1));
}
Ok(GF::new(num))
}
}
``````

Finally, we'll tell rust that that our implementation can be treated as a Field in any code that is written for Fields! This will come in handy for our calculator.

``````impl crate::field::Field for GF {
fn number_of_elements() -> usize {
P as usize
}
}
``````

#### Testing Time

Note that these tests assume `GF(5)`. If you change the size of the field, they are not expected to pass.

``````#[cfg(test)]
mod tests {
use super::*;

// TEST: We shouldn't be able to construct numbers out of the range
#[should_panic]
#[test]
fn test_invalid_numbers() {
GF::new(5);
}

#[test]
// GF(5) | 0 + 1 = 1
assert_eq!(GF::new(0) + GF::new(1), GF::new(1));
// GF(5) | 1 + 1 = 2
assert_eq!(GF::new(1) + GF::new(1), GF::new(2));
// GF(5) | 1 + 2 = 3
assert_eq!(GF::new(1) + GF::new(2), GF::new(3));
// GF(5) | 2 + 2 = 4
assert_eq!(GF::new(2) + GF::new(2), GF::new(4));
// GF(5) | 1 + 3 = 4
assert_eq!(GF::new(1) + GF::new(3), GF::new(4));
// GF(5) | 2 + 3 = 0
assert_eq!(GF::new(2) + GF::new(3), GF::new(0));
// GF(5) | 3 + 3 = 1
assert_eq!(GF::new(3) + GF::new(3), GF::new(1));
// GF(5) | 2 + 4 = 1
assert_eq!(GF::new(2) + GF::new(4), GF::new(1));
// GF(5) | 4 + 4 = 3
assert_eq!(GF::new(4) + GF::new(4), GF::new(3));
}

// TEST: Subtraction
#[test]
fn test_sub() {
// GF(5) | 1 - 0 = 1
assert_eq!(GF::new(1) - GF::new(0), GF::new(1));
// GF(5) | 0 - 1 = 4
assert_eq!(GF::new(0) - GF::new(1), GF::new(4));
// GF(5) | 1 - 1 = 0
assert_eq!(GF::new(1) - GF::new(1), GF::new(0));
// GF(5) | 1 - 2 = 4
assert_eq!(GF::new(1) - GF::new(2), GF::new(4));
// GF(5) | 2 - 2 = 0
assert_eq!(GF::new(2) - GF::new(2), GF::new(0));
// GF(5) | 1 - 3 = 3
assert_eq!(GF::new(1) - GF::new(3), GF::new(3));
// GF(5) | 2 - 3 = 4
assert_eq!(GF::new(2) - GF::new(3), GF::new(4));
// GF(5) | 3 - 3 = 0
assert_eq!(GF::new(3) - GF::new(3), GF::new(0));
// GF(5) | 2 - 4 = 3
assert_eq!(GF::new(2) - GF::new(4), GF::new(3));
// GF(5) | 4 - 4 = 0
assert_eq!(GF::new(4) - GF::new(4), GF::new(0));
}

// TEST: Multiplication
#[test]
fn test_mul() {
// GF(5) | 0 * 1 = 0
assert_eq!(GF::new(0) * GF::new(1), GF::new(0));
// GF(5) | 0 * 2 = 0
assert_eq!(GF::new(0) * GF::new(2), GF::new(0));
// GF(5) | 1 * 1 = 1
assert_eq!(GF::new(1) * GF::new(1), GF::new(1));
// GF(5) | 1 * 2 = 2
assert_eq!(GF::new(1) * GF::new(2), GF::new(2));
// GF(5) | 2 * 2 = 4
assert_eq!(GF::new(2) * GF::new(2), GF::new(4));
// GF(5) | 2 * 3 = 1
assert_eq!(GF::new(2) * GF::new(3), GF::new(1));
// GF(5) | 3 * 3 = 4
assert_eq!(GF::new(3) * GF::new(3), GF::new(4));
// GF(5) | 2 * 4 = 3
assert_eq!(GF::new(2) * GF::new(4), GF::new(3));
// GF(5) | 3 * 4 = 2
assert_eq!(GF::new(3) * GF::new(4), GF::new(2));
// GF(5) | 4 * 4 = 1
assert_eq!(GF::new(4) * GF::new(4), GF::new(1));
}

// TEST: Division
#[test]
fn test_div() {
// GF(5) | 0 / 1 = 0
assert_eq!(GF::new(0) / GF::new(1), Ok(GF::new(0)));
// GF(5) | 0 / 2 = 0
assert_eq!(GF::new(0) / GF::new(2), Ok(GF::new(0)));
// GF(5) | 1 / 0 = ERROR
assert!(matches!(GF::new(1) / GF::new(0), Err(_)));
// GF(5) | 2 / 0 = ERROR
assert!(matches!(GF::new(2) / GF::new(0), Err(_)));
// GF(5) | 1 / 1 = 1
assert_eq!(GF::new(1) / GF::new(1), Ok(GF::new(1)));
// GF(5) | 1 / 2 = 3
assert_eq!(GF::new(1) / GF::new(2), Ok(GF::new(3)));
// GF(5) | 2 / 2 = 1
assert_eq!(GF::new(2) / GF::new(2), Ok(GF::new(1)));
// GF(5) | 2 / 3 = 4
assert_eq!(GF::new(2) / GF::new(3), Ok(GF::new(4)));
// GF(5) | 3 / 3 = 1
assert_eq!(GF::new(3) / GF::new(3), Ok(GF::new(1)));
// GF(5) | 2 / 4 = 3
assert_eq!(GF::new(2) / GF::new(4), Ok(GF::new(3)));
// GF(5) | 3 / 4 = 2
assert_eq!(GF::new(3) / GF::new(4), Ok(GF::new(2)));
// GF(5) | 4 / 4 = 1
assert_eq!(GF::new(4) / GF::new(4), Ok(GF::new(1)));
}
}
``````

### Building and Testing

The above code can be built and tested the normal rust ways:

``````cargo test
cargo build
``````

### A `GF(p)` Calculator

Finally, we provide a little interactive calculator to explore these `GF(p)` fields. The calculator implementation is out of the scope for this series and uses more advanced Rust features so we won't explain it. If you're interested in this kind of thing, go read about Recursive Descent Parsers, and check out my other work on compilers (here and here).

The calculator looks like:

``````\$ ./target/debug/gf_p_calc
================================================================================
A Calculator for GF(5)
================================================================================

+  |   0    1    2    3    4
--------------------------------
0  |   0    1    2    3    4
1  |   1    2    3    4    0
2  |   2    3    4    0    1
3  |   3    4    0    1    2
4  |   4    0    1    2    3

Subtraction Table:

-  |   0    1    2    3    4
--------------------------------
0  |   0    4    3    2    1
1  |   1    0    4    3    2
2  |   2    1    0    4    3
3  |   3    2    1    0    4
4  |   4    3    2    1    0

Multiplication Table:

*  |   0    1    2    3    4
--------------------------------
0  |   0    0    0    0    0
1  |   0    1    2    3    4
2  |   0    2    4    1    3
3  |   0    3    1    4    2
4  |   0    4    3    2    1

Division Table:

/  |   0    1    2    3    4
--------------------------------
0  |   -    0    0    0    0
1  |   -    1    3    2    4
2  |   -    2    1    4    3
3  |   -    3    4    1    2
4  |   -    4    2    3    1

Enter any expression for evaluation (e.g. (1 + 2) * 4)

> 2 + 4
1
> 2 * 4
3
> 2*(1 + 3)
3
> 2*1 + 2*3
3
>
``````

Exercise: Play around with the calculator. Change `P` to a different prime and explore that field too.

Exercise: Do your own implementation of `GF(p)` fields in your preferred programming language.

### Next Up

Hopefully this section helps put a lot of pieces together.

Is it a little weird that `2*4 = 3`? Maybe.

But that's why I say that the numbers are weird but everything just works like normal. It's a Field because it behaves like a Field. And, that's all we care about in Abstract Algebra.

The work we've done so far is already quite useful, but for computing, this restriction to prime numbers is awkward. We really want fields like `GF(4)`, `GF(16)`, `GF(64)`, `GF(256)`, etc that map well to the binary numbers implemented by transistors on a piece of silicon.

To do this we'll need more abstraction and get reacquainted with an old friend: Polynomials

Let's get curvy.