# [−][src]Crate galois_2p8

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:

- Associativity:
`a + (b + c) == (a + b) + c`

. - Commutativity:
`a + b`

==`b + a`

and`a * b == b * a`

. - Identity: There exists a
`0`

and`1`

element such that`a + 0 == a`

and`a * 1 == a`

. - Additive inverse: For every
`a`

there is some`-a`

such that`a + -a == 0`

. - Multiplicative inverse: For every
`a`

there is some`a^-1`

such that`a * a^-1 == 1`

. - 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.

## Re-exports

`pub use field::IrreducablePolynomial;` |

`pub use field::Field;` |

`pub use field::GeneralField;` |

`pub use field::PrimitivePolynomialField;` |

## Modules

field | Implements arithmetic operations over all |