1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

// lib.rs: part of the galois_2p8 Crate.
// Copyright 2018 Daniel Sweet. See the COPYRIGHT file at the top-level
// directory of this distribution.

//! Provides operations over all `GF(2^8)` extensions.
//!
//! # Fields
//!
//! Fields are sets of values over which addition, subtraction, multiplication
//! and division are defined, such that the results of these operations are
//! still members of the defined set and the following properties hold:
//!
//! 1. Associativity: `a + (b + c) == (a + b) + c`.
//! 2. Commutativity: `a + b` == `b + a` and `a * b == b * a`.
//! 3. Identity: There exists a `0` and `1` element such that
//!    `a + 0 == a` and `a * 1 == a`.
//! 4. Additive inverse: For every `a` there is some `-a` such that
//!    `a + -a == 0`.
//! 5. Multiplicative inverse: For every `a` there is some `a^-1` such that
//!    `a * a^-1 == 1`.
//! 6. Distributivity: `a * (b + c) == a * b + b * c`.
//!
//! The set of real numbers constitutes a field, but said set is not the only
//! possible field.
//!
//! # Galois Fields
//!
//! Galois fields are finite fields: a limited number of possible members are
//! defined. The number of unique members of a Galois field is called the order
//! of the field. Galois fields only exist for integers that are also powers
//! of prime numbers. The prime base of an order is called the characteristic
//! of the field. For any Galois field with a characteristic of `c`, for all
//! members of the field `m`, `let sum = 0; for i in 0..c { sum += m };
//! sum == 0`.
//!
//! Galois fields with non-prime orders are defined in terms of polynomials with
//! the coefficients being members of the field defined by the characteristic as
//! the order. This maps directly to the representation of numbers in terms of
//! their base. The resulting field is considered an _extension_ of the field
//! generated by the characteristic.
//!
//! For example, a Galois field with an order of 256 necessarily has a
//! characteristic of 2, because 2 is the least prime base of 256. As a result,
//! `GF(256) == GF(2^8)` is defined in terms of an order 8 polynomial, taking
//! the form
//!
//! `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`
//!
//! where `k_n in [0, 1] for n in [0..8]`.
//!
//! Similar to non-extension fields being defined over prime numbers, extensions
//! are defined over prime polynomials, that is, multiplication and division are
//! performed modulo some polynomial that cannot be represented as the result
//! of the multiplication of two polynomial factors. These prime polynomials are
//! known as _irreducable polynomials_, because they cannot be reduced to
//! factors.
//!
//! # Primitive Polynomials
//!
//! Consider the exponential operation `a ^ b`. In Galois fields, this is still
//! defined in terms of repeated multiplication of `a` times itself over `b`
//! iterations. Consider also a Galois field defined over an irreducable
//! polynomial `p`. If `a` is prime, but also the member of a given field, and
//! for every member `b` in the field, `a ^ b` corresponds to exactly one other
//! member of the field, then we say that `p` is a _primitive polynomial_,
//! because the entirety of the field members can be represented in terms of
//! exponents and logarithms about the base `a`.
//!
//! # `GF(2^x)` on Hardware
//!
//! The definition of finite fields with a characteristic of 2 results in addition
//! and subtraction mapping directly to bitwise XOR. Consider that:
//!
//! - `0 +/- 0 == 0; 0 XOR 0 == 0`
//! - `1 +/- 0 == 1; 1 XOR 0 == 1`
//! - `0 +/- 1 == 1; 0 XOR 1 == 1`
//! - `1 +/- 1 == 0; 1 XOR 1 == 0`
//!
//! Multiplication and division are slightly more difficult. Multiplication is
//! still defined as repeated addition of coefficients within the field, but
//! is performed modulo the primitive polynomial, which requires taking the
//! remainder of divison. Division within the field is purely defined as the
//! inverse of multiplication, with no canonical polynomial-time algorithm.
//! (This ostensible incongruity of computational complexity between
//! multiplication and division forms the basis of several areas of study
//! in cryptography).
//!
//! If the size of the field is small enough, multiplication and division can
//! be performed by way of table lookups. For non-primitive polynomials, the
//! size of the lookup tables can be reduced by decomposing operations
//! according to the field properties. For example, `a * b == (a_1 + a_2) * b
//! == a_1 * b + a_2 * b`, where a_1 represents the upper bits of `a` and `a_2`
//! represents the lower bits of `a`. As a result, the required storage space
//! is reduced by a factor of `2 ^ (x - 5)`. For primitive polynomials,
//! the operations can be performed in terms of exponentials and logarithms,
//! which only requires two to five times as many entries as members of the
//! field, depending on the implementation. `galois_2p8` currently uses
//! tables requiring three times the size of the field for multiplication
//! and division for primitive polynomials.
//!
//! # The `galois_2p8` Crate
//!
//! This crate implements `GF(2^8)` arithmetic for all possible irreducable
//! polynomials. The possible irreducable polynomials are represented as members
//! of the [`IrreducablePolynomial`] enumeration. Each [`IrreducablePolynomial`]
//! is passed as an argument to the constructor of a struct implementing the
//! [`Field`] trait. The [`GeneralField`] struct implements the [`Field`] trait
//! over all [`IrreducablePolynomial`]s, even non-primitive ones. The
//! [`PrimitivePolynomialField`] struct and implementation are specialized for
//! primitive polynomials.
//!
//! Future releases of this crate will support optimized linear algebra
//! primitives implemented across potentially heterogeneous compute
//! environments.
//!
//! [`IrreducablePolynomial`]: field/enum.IrreducablePolynomial.html
//! [`Field`]: field/trait.Field.html
//! [`GeneralField`]: field/struct.GeneralField.html
//! [`PrimitivePolynomialField`]: field/struct.PrimitivePolynomialField.html

// "The general internet" says that this _has_ to happen before
// more module definitions. It'd be real nice if the spec warned us. :/
#[cfg(test)]
#[macro_use]
extern crate proptest;
#[cfg(test)]
#[macro_use]
extern crate lazy_static;

pub use field::{
    IrreducablePolynomial,
    Field,
    GeneralField,
    PrimitivePolynomialField
};

pub mod field;

#[cfg(test)]
#[macro_use]
mod field_tests;
#[cfg(test)]
mod field_multiword_tests;