galois_2p8

Basic Arithmetic over Galois (finite) fields with 2^8 == 256 members.

This library currently implements addition, subtraction, multiplication, and division over members of a GF(2^8) == GF(256) field. All possible GF(2^8) fields are supported by these implementations.

Galois Fields: A Primer

Fields

Fields are mathematical objects over which the following operations are defined:

Addition: a + b
Subtraction a - b
Multiplication a * b
Division a / b

Where Subtraction is the inverse of Addition:

a + b - b == a
a + b - a == b

And Division is the inverse of Multiplication:

a * b / b == a
a * b / a == b

With a few more properties as well:

Associativity: a + (b + c) == (a + b) + c and a * (b * c) == (a * b) * c
Commutativity: a + b == b + a and a * b == b * a
Identity: a + 0 == a and a * 1 == a
Distributivity: a * (b + c) == a * b + a * c

Real numbers constitute a field, but there are many others. In particular, finite fields exist.

Finite Fields

Finite fields only contain a certain number of distinct members: operations within these finite fields become cyclical. Finite fields are also known as Galois fields, hence the crate name galois_2p8.

The canonical definition of a Galois field requires that the cardinality of the membership set be a prime number. That is, one cannot have a finite field containing a composite count of distinct members under the canonical definition.

Galois fields with a membership set of a composite cardinality are possible under arithmetic extension. That is, if the cardinality of the membership set may be composite if said cardinality is a power of a prime number. The prime number basis is known as the characteristic of the resulting field, and the exponent is known as the order. In the case of this crate, the fields implemented have a characteristic of two and an order of 8. The shorthand notation for Galois fields of a given characteristic and order is GF(characteristic ^ order), where characteristic ^ order may be concretely written as the result of the exponentiation. This crate implements operations over GF(2^8) == GF(256).

Arithmetic extensions of Galois fields treat all members as a polynomial of a degree equal to the extension's order minus one, ensuring that there may be exactly characteristic ^ order members of the field when accounting for 0. Within this crate, field members are treated as a degree 8 polynomial, where the coefficients of said polynomial are members of the Galois field with two possible members: 0 and 1. The coefficients naturally map into bits, and the polynomial as a whole maps into unsigned 8-bit integers.

Arithmetic within these algebraic extensions follows the general definition of arithmetic over polynomials. Addition and subtraction of two polynomials results in a polynomial whose coefficients are the addition or subtraction of the corresponding coefficients in the source polynomial. Division is defined purely in terms of the multiplicative inverse, and multiplication is performed using the distributive property of fields, with one important caveat: in order to maintain the field properties, multiplications are performed modulo an irreducable polynomial.

Irreducable Polynomials and Multiplication

A given polynomial is said to be irreducable in general if it cannot be represented as the result of the multiplication of two other polynomials. This is analogous to prime numbers in terms of integers. The irreducable polynomials used in algebraic extensions have a degree equal to the order of the extension.

Multiplication within algebraic extensions of Galois fields requires that the usual distributive multiplication of polynomials be performed modulo an irreducable polynomial. That is to say, the result of the overall operation must be equal to the remainder of the non-modulo operation divided by the target irreducable polynomial.

In general, algebraic extensions allow for the existence of multiple valid irreducable polynomials, modulo which multiplication can be performed. Each distinct irreducable polynomial defines its own distinct Galois field.

This crate implements all degree 8 irreducable polynomials with a characteristic of 2 in general, with special support for primitive polynomials.

Primitive Polynomials

An irreducable polynomial is said to be primitive if the resulting field it generates is structured such that there exists some basis alpha for which the set of all powers, exponentiated up to the cardinality of the membership set, is equal to the set of all members of the finite field. That is, for any arbitrary n in the Galois field, alpha ^ n is a unique member of the same Galois field. In the case of GF(2 ^ n) for arbitrary n, alpha is 2.

Multiplication and division may be represented in terms of logarithms and exponentiation if the irreducable polynomial is a primitive polynomial. Implementing multiplication and division in terms of logarithms and exponentiation requires either less storage or fewer operations than using rendered multiplication and division tables. In this crate, the multiplication and division tables are designed to minimize storage requirements, so the implementation of multiplication and division for single elements is faster for fields over primitive polynomials.

Note that only a subset of the irreducable polynomials are primitive.

The `galois_2p8` Crate

This crate contains implementations of general GF(2^8) field arithmetic across all irreducable polynomials. The irreducable polynomials have been precomputed with an auxiliary utility script (see utils/polys.py), and the primitive polynomials have been identified by this precomputation as well. Special implementations of field arithmetic are also available for these primitive polynomials, taking advantage of the ability to accurately represent multiplication and division in terms of exponentiation and logarithms.

Vector Operations

The following vector operation kernels are provided in addition to single-element arithmetic:

Adding and subtracting vectors
Multiplying and dividing vectors by one scalar
Adding to or subtracting from vectors, where the non-destination vector is scaled by a provided scalar.

The vector kernels concerning addition and subtraction are expected to result in optimized code if compiled with the right optimization level, but other vector kernels default to simply being loops over scalar operations unless SIMD support is enabled with the "simd" feature.

SIMD Support

Common operations over vectors of GF(2^8) members lend themselves to acceleration with SIMD intrinsics, as per James Plank's [Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions] (http://web.eecs.utk.edu/~plank/plank/papers/FAST-2013-GF.html). This crate currently utilizes SSE 3 and AVX 2 on x86_64 only, and only if compiled with the "simd" feature. Additionally, AVX 2 is only used if the AVX 2 ABI enabled with the avx2 code generation, e.g. by exporting RUSTFLAGS="-C target-feature=avx2".

Future Direction

As of the current version of this crate (v0.1.0), only arithmetic and vector kernels are provided. The long-term goal of this crate is to provide optimized matrix storage and basic matrix operations, optimized matrix inversion, and possibly GPGPU implementations of matrix operations.

galois_2p8 0.1.2