galois_2p8/
lib.rs

1// lib.rs: part of the galois_2p8 Crate.
2// Copyright 2018 Daniel Sweet. See the COPYRIGHT file at the top-level
3// directory of this distribution.
4
5//! Provides operations over all `GF(2^8)` extensions.
6//!
7//! # Fields
8//!
9//! Fields are sets of values over which addition, subtraction, multiplication
10//! and division are defined, such that the results of these operations are
11//! still members of the defined set and the following properties hold:
12//!
13//! 1. Associativity: `a + (b + c) == (a + b) + c`.
14//! 2. Commutativity: `a + b` == `b + a` and `a * b == b * a`.
15//! 3. Identity: There exists a `0` and `1` element such that
16//!    `a + 0 == a` and `a * 1 == a`.
17//! 4. Additive inverse: For every `a` there is some `-a` such that
18//!    `a + -a == 0`.
19//! 5. Multiplicative inverse: For every `a` there is some `a^-1` such that
20//!    `a * a^-1 == 1`.
21//! 6. Distributivity: `a * (b + c) == a * b + b * c`.
22//!
23//! The set of real numbers constitutes a field, but said set is not the only
24//! possible field.
25//!
26//! # Galois Fields
27//!
28//! Galois fields are finite fields: a limited number of possible members are
29//! defined. The number of unique members of a Galois field is called the order
30//! of the field. Galois fields only exist for integers that are also powers
31//! of prime numbers. The prime base of an order is called the characteristic
32//! of the field. For any Galois field with a characteristic of `c`, for all
33//! members of the field `m`, `let sum = 0; for i in 0..c { sum += m };
34//! sum == 0`.
35//!
36//! Galois fields with non-prime orders are defined in terms of polynomials with
37//! the coefficients being members of the field defined by the characteristic as
38//! the order. This maps directly to the representation of numbers in terms of
39//! their base. The resulting field is considered an _extension_ of the field
40//! generated by the characteristic.
41//!
42//! For example, a Galois field with an order of 256 necessarily has a
43//! characteristic of 2, because 2 is the least prime base of 256. As a result,
44//! `GF(256) == GF(2^8)` is defined in terms of an order 8 polynomial, taking
45//! the form
46//!
47//! `k_8*x^8 + k_7*x^7 + k_6*x^6 + k_5*x^5 + k_4*x^4 + k_3*x^3 + k_2*x^2 + k_1*x + k_0`
48//!
49//! where `k_n in [0, 1] for n in [0..8]`.
50//!
51//! Similar to non-extension fields being defined over prime numbers, extensions
52//! are defined over prime polynomials, that is, multiplication and division are
53//! performed modulo some polynomial that cannot be represented as the result
54//! of the multiplication of two polynomial factors. These prime polynomials are
55//! known as _irreducable polynomials_, because they cannot be reduced to
56//! factors.
57//!
58//! # Primitive Polynomials
59//!
60//! Consider the exponential operation `a ^ b`. In Galois fields, this is still
61//! defined in terms of repeated multiplication of `a` times itself over `b`
62//! iterations. Consider also a Galois field defined over an irreducable
63//! polynomial `p`. If `a` is prime, but also the member of a given field, and
64//! for every member `b` in the field, `a ^ b` corresponds to exactly one other
65//! member of the field, then we say that `p` is a _primitive polynomial_,
66//! because the entirety of the field members can be represented in terms of
67//! exponents and logarithms about the base `a`.
68//!
69//! # `GF(2^x)` on Hardware
70//!
71//! The definition of finite fields with a characteristic of 2 results in addition
72//! and subtraction mapping directly to bitwise XOR. Consider that:
73//!
74//! - `0 +/- 0 == 0; 0 XOR 0 == 0`
75//! - `1 +/- 0 == 1; 1 XOR 0 == 1`
76//! - `0 +/- 1 == 1; 0 XOR 1 == 1`
77//! - `1 +/- 1 == 0; 1 XOR 1 == 0`
78//!
79//! Multiplication and division are slightly more difficult. Multiplication is
80//! still defined as repeated addition of coefficients within the field, but
81//! is performed modulo the primitive polynomial, which requires taking the
82//! remainder of divison. Division within the field is purely defined as the
83//! inverse of multiplication, with no canonical polynomial-time algorithm.
84//! (This ostensible incongruity of computational complexity between
85//! multiplication and division forms the basis of several areas of study
86//! in cryptography).
87//!
88//! If the size of the field is small enough, multiplication and division can
89//! be performed by way of table lookups. For non-primitive polynomials, the
90//! size of the lookup tables can be reduced by decomposing operations
91//! according to the field properties. For example, `a * b == (a_1 + a_2) * b
92//! == a_1 * b + a_2 * b`, where a_1 represents the upper bits of `a` and `a_2`
93//! represents the lower bits of `a`. As a result, the required storage space
94//! is reduced by a factor of `2 ^ (x - 5)`. For primitive polynomials,
95//! the operations can be performed in terms of exponentials and logarithms,
96//! which only requires two to five times as many entries as members of the
97//! field, depending on the implementation. `galois_2p8` currently uses
98//! tables requiring three times the size of the field for multiplication
99//! and division for primitive polynomials.
100//!
101//! # The `galois_2p8` Crate
102//!
103//! This crate implements `GF(2^8)` arithmetic for all possible irreducable
104//! polynomials. The possible irreducable polynomials are represented as members
105//! of the [`IrreducablePolynomial`] enumeration. Each [`IrreducablePolynomial`]
106//! is passed as an argument to the constructor of a struct implementing the
107//! [`Field`] trait. The [`GeneralField`] struct implements the [`Field`] trait
108//! over all [`IrreducablePolynomial`]s, even non-primitive ones. The
109//! [`PrimitivePolynomialField`] struct and implementation are specialized for
110//! primitive polynomials.
111//!
112//! Future releases of this crate will support optimized linear algebra
113//! primitives implemented across potentially heterogeneous compute
114//! environments.
115//!
116//! [`IrreducablePolynomial`]: field/enum.IrreducablePolynomial.html
117//! [`Field`]: field/trait.Field.html
118//! [`GeneralField`]: field/struct.GeneralField.html
119//! [`PrimitivePolynomialField`]: field/struct.PrimitivePolynomialField.html
120
121// "The general internet" says that this _has_ to happen before
122// more module definitions. It'd be real nice if the spec warned us. :/
123#[cfg(test)]
124#[macro_use]
125extern crate proptest;
126#[cfg(test)]
127#[macro_use]
128extern crate lazy_static;
129
130pub use field::{
131    IrreducablePolynomial,
132    Field,
133    GeneralField,
134    PrimitivePolynomialField
135};
136
137pub mod field;
138
139#[cfg(test)]
140#[macro_use]
141mod field_tests;
142#[cfg(test)]
143mod field_multiword_tests;