### 3 releases

Uses old Rust 2015

0.1.2 | Feb 13, 2022 |
---|---|

0.1.1 | Nov 28, 2018 |

0.1.0 | Nov 28, 2018 |

#**455** in Algorithms

**69** downloads per month

Used in **2** crates

**MIT**license

81KB

1.5K
SLoC

# galois_2p8

Basic Arithmetic over Galois (finite) fields with

members.`2``^``8` `==` `256`

This library currently implements addition, subtraction, multiplication, and
division over members of a

field. All possible `GF``(``2``^``8``)` `==` `GF``(``256``)`

fields are supported by these implementations.`GF``(``2``^``8``)`

## 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:

and`a``+``(`b`+`c`)``==``(`a`+`b`)``+`c`a``*``(`b`*`c`)``==``(`a`*`b`)``*`c - Commutativity:

and`a``+`b`==`b`+`a`a``*`b`==`b`*`a - Identity:

and`a``+``0``==`a`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

, where `GF``(`characteristic `^` order`)`

may be concretely
written as the result of the exponentiation. This crate implements operations
over `characteristic ^ order`

`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

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.`characteristic ^ order`

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

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
`alpha`

in the Galois field, `n`

is a unique member of the same Galois field.
In the case of `alpha ^ n`

`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

`galois_2p8`

This crate contains implementations of general

field arithmetic across
all irreducable polynomials. The irreducable polynomials have been precomputed
with an auxiliary utility script (see `GF``(``2``^``8``)`

), 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.`utils/polys.py`

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

feature.`"`simd`"`

### SIMD Support

Common operations over vectors of

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 `GF``(``2``^``8``)`

only, and only if compiled with
the `x86_64`

feature. Additionally, AVX 2 is only used if the AVX 2 ABI enabled
with the `"`simd`"`

code generation, e.g. by exporting
`avx2`

.`RUSTFLAGS``=``"`-C target-feature=avx2`"`

### Future Direction

As of the current version of this crate (

), 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.`v0 .1.0`