galois

package module
v0.0.0-...-aa1bbcd Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 5, 2022 License: MIT Imports: 6 Imported by: 0

README

galois

Implements finite fields of order $2^m$ up to $2^{32}$ using polynomials.

Finite Fields

Finite fields are mathematical objects used to construct finite, cyclical number systems which mirror the behaviors of normal infinite number systems in many common ways. They create domains where numbers can be added, subtracted, multiplied, divided, and exponentiated while still behaving according to the common rules of algebra, such as commutativity, associativity, distributivity, identity elements, and inverses.

The most common way to construct a finite field is by performing operations on integers, and taking the result modulo some prime integer $p$. For example, the integers modulo 5 form a finite field. Integers already follow most of the simpler common rules for fields, and taking them modulo 5 allows you to find multiplicative inverses: For every value from 1 to 4, there is another number which multiplies mod 5 to produce the multiplicative identity element 1.

Multiplication mod 5 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

You can now define division among the integers mod 5. For example, $4 \div 3 \equiv 3 \mod{5}$ because $3 \cdot 3 \equiv 4 \mod{5}$

Non-Prime Order Finite Fields

The 'order' of a finite field is the number of elements in the field. For the integers mod 5, it is easy to see that it has five elements: the integers 1 through 4, and zero. This generalizes for integer finite fields generated by any prime number $p$: That field will always have order $p$.

But what if you want a finite field with a non-prime order?

It is common to use finite fields with orders that are powers of two. This helps us maximize the use of storage and communication bandwidth. After all, the fundamental unit of information is the binary bit. Frequently in computer systems, information is stored and transmitted in symbols which are some fixed number of bits.

If we have need of a finite number system to keep numbers bounded to within the space of such a symbol (for example, a byte), it would be best if that number system makes full use of the symbol space (thus it would work with all possible byte values from 0 to 255). Since 256 is not a prime number, we can't use simple integers and modular arithmetic to construct a finite field of that order.

Polynomials

This library uses polynomials modulo prime polynomials (instead of integers modulo prime integers) to construct finite fields which have non-prime order. This allows you to define cyclic multiplication and division within fixed-bit-size symbols, ensuring the outputs of the operation do not overflow the maximum symbol size.

For example, this library can be used to perform byte-wise multiplication and division, where the output of every operation is also a byte, while the normal laws of algebra still apply. See example_test.go to see an example.

Usage

First, decide how many elements you need in your finite field. This library allows callers to create finite fields of size $2^m$, where $2 <= m <= 32$.

Based on this, pick an irreducible prime polynomial whose degree is $m$. For example, if you need to do finite field arithmetic on 16-bit symbols, use a polynomial of degree 16. For convenience, this library comes pre-packaged with a set of prime polynomials, which were sourced from https://www.partow.net/programming/polynomials/index.html. A prime polynomial of degree 16 is exported as galois.PrimePolynomialDegree16.

Next, instantiate a galois.Field[T]:

field := galois.NewField[uint16](galois.PrimePolynomialDegree16)

The type parameter T on galois.Field[T] selects the type of integer which will represent the elements of the field in the interface of galois.Field[T]. Note that this doesn't affect the speed of internal operations, only the API of galois.Field[T]. Internally, galois.Field[T] always uses uint64 to represent polynomials when performing mathematical operations.

This field can then be used to perform operations on uint16 symbols:

field.Mul(0x1234, 0x4567) // 0x6324
field.Div(0x6324, 0x1234) // 0x4567

Note that the choice of prime polynomial matters very much for compatibility between implementations. Even if two different prime polynomials share the same degree, and thus generate finite fields of the same order, the results of arithmetic operations within their respective fields will be different.

Documentation

Overview

Package galois implements finite fields with non-prime order 2^m, up to a maximum of 2^32.

To achieve this, we create fields whose elements are polynomials with binary coefficients (one and zero) with operations between coefficients taken modulo two. All operations between polynomials are taken modulo an irreducible prime. Operations within this domain form a finite field (Galois Field) with an order that is a power of two.

We use prime polynomials sourced from https://www.partow.net/programming/polynomials/index.html

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Field 

type Field[T IntLike] struct {
	// Prime should be an irreducible polynomial. All operations within the Field
	// are taken modulo this polynomial - That is to say, polynomials are divided
	// by this polynomial and the remainder is used as the final output.
	Prime Polynomial
}

Field is a finite field of polynomials over an irreducible prime polynomial.

Example

This example demonstrates the construction and use of a Finite Field of order 256, AKA GF(256).

This is a very commonly used finite field, as the elements of GF(256) have a bijective correspondence (one-to-one mapping) to all possible values of a byte: 0 to 255.

GF(256) is useful because it allows you to define byte-wise division and multiplication with unique outputs which stay within the size of a byte. 

package main

import (
	"fmt"

	"github.com/kklash/galois"
)

func main() {
	field := galois.NewField[uint8](galois.PrimePolynomialDegree8)

	x := uint8(0xBC)
	y := uint8(0xDE)
	z := uint8(0xFF)

	xMulY := field.Mul(x, y)

	fmt.Printf(
		"0x%X * 0x%X = 0x%X\n",
		x, y, xMulY,
	)
	fmt.Printf(
		"0x%X / 0x%X = 0x%X\n",
		xMulY, x, field.Div(xMulY, x),
	)

	zMulY := field.Mul(z, y)

	fmt.Printf(
		"0x%X * 0x%X = 0x%X\n",
		z, y, zMulY,
	)
	fmt.Printf(
		"0x%X / 0x%X = 0x%X\n",
		zMulY, y, field.Div(zMulY, y),
	)

}

Output:

0xBC * 0xDE = 0x6D
0x6D / 0xBC = 0xDE
0xFF * 0xDE = 0x8B
0x8B / 0xDE = 0xFF

func NewField 

func NewField[T IntLike](prime Polynomial) *Field[T]

NewField creates a Field generated by the given prime polynomial.

The generic type parameter T selects which type of integer will be used to represent elements of the Field. This parameter only affects the API of Field; Internally Field uses uint64 to represent polynomials during mathematical operations.

If a signed integer type is used for T, Field operations on negative values will return undefined results.

Panics if the type parameter T is not of sufficient size to represent every element in the field.

func (*Field[T]) Add 

func (field *Field[T]) Add(values ...T) (sum T)

Add computes the sum of the given elements within the finite field.

Note that addition and subtraction within a Field is the same, because addition consists of adding polynomials with coefficients modulo two.

func (*Field[T]) Div 

func (field *Field[T]) Div(numerator, denominator T) T

Div returns the division of the numerator field element by the denominator element. As long as the field is using a real prime polynomial as its modulus, every field element will always be able to divide evenly into any other element, and still produce a defined quotient which is also a member of the field.

The exception is dividing by zero. If denominator is the additive identity element zero, Div will panic when trying to calculate the multiplicative inverse of denominator.

func (*Field[T]) Exp 

func (field *Field[T]) Exp(base T, exponent uint64) T

Exp multiplies the base element by itself the given number of times.

If exponent is zero, returns the multiplicative identity 1.

func (*Field[T]) Generate 

func (field *Field[T]) Generate(exponent uint64) T

Generate constructs a polynomial element in a finite field for the given prime Polynomial by exponentiating the base Generator element.

If the exponent is larger than the field order, the exponent is reduced modulo that order.

func (*Field[T]) Mul 

func (field *Field[T]) Mul(values ...T) (product T)

Mul multiplies a set of field field elements and returns the product. If called with no parameters, Mul returns zero.

If any element is the additive identity element 0, Mul always returns zero.

Example

This example demonstrates basic multiplication of two elements using a Field.

Note how the choice of prime polynomial matters very much. Even if two prime polynomials have the same degree, and thus generate a field of the same order, the results of arithmetic operations within those fields will be different. 

package main

import (
	"fmt"

	"github.com/kklash/galois"
)

func main() {
	field1 := galois.NewField[uint16](galois.PrimePolynomialDegree16)
	a := uint16(0x1234)
	b := uint16(0x5678)
	fmt.Printf("field1: 0x%X * 0x%X = 0x%X\n", a, b, field1.Mul(a, b))

	// x^16 + x^13 + x^12 + x^10 + x^9 + x^7 + x^6 + x^1 + 1
	field2 := galois.NewField[uint16](0b10011011011000011)
	fmt.Printf("field2: 0x%X * 0x%X = 0x%X\n", a, b, field2.Mul(a, b))

}

Output:

field1: 0x1234 * 0x5678 = 0x6324
field2: 0x1234 * 0x5678 = 0xA051

func (*Field[T]) MultInverse 

func (field *Field[T]) MultInverse(y T) T

MultInverse computes the multiplicative inverse of y within the finite field, using the extended euclidean algorithm: 

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Simple_algebraic_field_extensions

Multiplying an element with its multiplicative inverse always returns the multiplicative identity element 1. Every element in the field has an inverse element, including the multiplicative identity element whose inverse is itself, with the notable exception of the additive identity element zero. Zero has no inverse because multiplying it by anything always results in zero.

Panics if y is the additive identity element zero.

func (*Field[T]) Order 

func (field *Field[T]) Order() uint64

Order returns the order of the field (i.e. the number of elements, including zero).

func (*Field[T]) Sub 

func (field *Field[T]) Sub(a, b T) T

Sub computes the difference of the given elements (a - b) within the finite field.

Note that addition and subtraction within a Field is the same, because addition consists of adding polynomials with coefficients modulo two.

type IntLike 

type IntLike interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64
}

IntLike is a type constraint supporting any type that reduces to an integer-like type.

type Polynomial 

type Polynomial uint64

Polynomial is a polynomial whose coefficients are either one or zero.

The bits of this unsigned integer are used to represent the coefficients of a polynomial: least-significant bits are the lowest-degree coefficients, most-significant bits are the highest-degree coefficients.

For example, the integer 361 (101101001 in base-2), would represent the polynomial: 

x^8 + x^6 + x^5 + x^3 + 1

const (
	PrimePolynomialDegree2  Polynomial = 0b000000000000000000000000000000111 // x^2 + x + 1
	PrimePolynomialDegree3  Polynomial = 0b000000000000000000000000000001011 // x^3 + x + 1
	PrimePolynomialDegree4  Polynomial = 0b000000000000000000000000000010011 // x^4 + x + 1
	PrimePolynomialDegree5  Polynomial = 0b000000000000000000000000000100101 // x^5 + x^2 + 1
	PrimePolynomialDegree6  Polynomial = 0b000000000000000000000000001000011 // x^6 + x + 1
	PrimePolynomialDegree7  Polynomial = 0b000000000000000000000000010000011 // x^7 + x + 1
	PrimePolynomialDegree8  Polynomial = 0b000000000000000000000000100011101 // x^8 + x^4 + x^3 + x^2 + 1
	PrimePolynomialDegree9  Polynomial = 0b000000000000000000000001000010001 // x^9 + x^4 + 1
	PrimePolynomialDegree10 Polynomial = 0b000000000000000000000010000001001 // x^10 + x^3 + 1
	PrimePolynomialDegree11 Polynomial = 0b000000000000000000000100000000101 // x^11 + x^2 + 1
	PrimePolynomialDegree12 Polynomial = 0b000000000000000000001000001010011 // x^12 + x^6 + x^4 + x + 1
	PrimePolynomialDegree13 Polynomial = 0b000000000000000000010000000011011 // x^13 + x^4 + x^3 + x + 1
	PrimePolynomialDegree14 Polynomial = 0b000000000000000000100000101000011 // x^14 + x^8 + x^6 + x + 1
	PrimePolynomialDegree15 Polynomial = 0b000000000000000001000000000000011 // x^15 + x + 1
	PrimePolynomialDegree16 Polynomial = 0b000000000000000010001000000001011 // x^16 + x^12 + x^3 + x + 1
	PrimePolynomialDegree17 Polynomial = 0b000000000000000100000000000001001 // x^17 + x^3 + 1
	PrimePolynomialDegree18 Polynomial = 0b000000000000001000000000010000001 // x^18 + x^7 + 1
	PrimePolynomialDegree19 Polynomial = 0b000000000000010000000000000100111 // x^19 + x^5 + x^2 + x + 1
	PrimePolynomialDegree20 Polynomial = 0b000000000000100000000000000001001 // x^20 + x^3 + 1
	PrimePolynomialDegree21 Polynomial = 0b000000000001000000000000000000101 // x^21 + x^2 + 1
	PrimePolynomialDegree22 Polynomial = 0b000000000010000000000000000000011 // x^22 + x + 1
	PrimePolynomialDegree23 Polynomial = 0b000000000100000000000000000100001 // x^23 + x^5 + 1
	PrimePolynomialDegree24 Polynomial = 0b000000001000000000000000010000111 // x^24 + x^7 + x^2 + x + 1
	PrimePolynomialDegree25 Polynomial = 0b000000010000000000000000000001001 // x^25 + x^3 + 1
	PrimePolynomialDegree26 Polynomial = 0b000000100000000000000000001000111 // x^26 + x^6 + x^2 + x + 1
	PrimePolynomialDegree27 Polynomial = 0b000001000000000000000000000100111 // x^27 + x^5 + x^2 + x + 1
	PrimePolynomialDegree28 Polynomial = 0b000010000000000000000000000001001 // x^28 + x^3 + 1
	PrimePolynomialDegree29 Polynomial = 0b000100000000000000000000000000101 // x^29 + x^2 + 1
	PrimePolynomialDegree30 Polynomial = 0b001000000100000000000000000000111 // x^30 + x^23 + x^2 + x + 1
	PrimePolynomialDegree31 Polynomial = 0b010000000000000000000000000001001 // x^31 + x^3 + 1
	PrimePolynomialDegree32 Polynomial = 0b100000000010000000000000000000111 // x^32 + x^22 + x^2 + x + 1
)
const Generator Polynomial = 2

Generator is the primitive generator polynomial element used to generate all other elements in a finite field, by modular exponentiation of itself.

func (Polynomial) Add 

func (a Polynomial) Add(b Polynomial) (sum Polynomial)

Add returns the sum of the polynomials a and b, with coefficients taken modulo two.

func (Polynomial) Degree 

func (p Polynomial) Degree() uint64

Degree returns the degree of the highest non-zero term of the Polynomial.

func (Polynomial) Div 

func (numerator Polynomial) Div(denominator Polynomial) (quotient, remainder Polynomial)

Div divides the numerator polynomial by the given denominator polynomial and returns the quotient and remainder.

Panics if denominator is zero.

func (Polynomial) Exp 

func (base Polynomial) Exp(exponent uint64, modulus Polynomial) Polynomial

Exp exponentiates the base Polynomial to the power of the given exponent, modulo the given modulus Polynomial, using the square & multiply algorithm.

If modulus is the empty Polynomial (zero), no modular arithmetic is performed.

func (Polynomial) Mod 

func (numerator Polynomial) Mod(denominator Polynomial) Polynomial

Mod divides the numerator polynomial by the given denominator polynomial and returns only the remainder.

Panics if denominator is zero.

func (Polynomial) Mul 

func (a Polynomial) Mul(b Polynomial) (product Polynomial)

Mul returns the product of the polynomials a and b, with coefficients taken modulo two.

func (Polynomial) String 

func (p Polynomial) String() string

String returns the string representation of the Polynomial in standard form.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.