README
¶
go-galoisfield
An implementation of the GF(2**m) Galois finite fields for Go.
What is a Galois field?
- http://mathworld.wolfram.com/FiniteField.html
- http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-451-principles-of-digital-communication-ii-spring-2005/lecture-notes/chap7.pdf
- http://www.cs.utsa.edu/~wagner/laws/FFM.html
- http://research.swtch.com/field
A Galois field, also known as a finite field, is a mathematical field with a
number of elements equal to a prime number to a positive integer power. While
finite fields with a prime number of elements are familiar to most programmers
-- boolean arithmetic, a.k.a. arithmetic mod 2 is a well-known example --
fields that take that prime to powers higher than 1 are less well-known.
Basically, an element of GF(2**m) can be seen as a list of m bits, where
addition and multiplication are elementwise mod 2 (a XOR b for addition,
a AND b for multiplication) and the remaining rules of field arithmetic
follow from linear algebra (vectors, or alternatively, polynomial coefficients).
Short version: an element of GF(2**8) element may be represented as a byte
(0 ≤ n ≤ 255), but it's really a vector of 8 bits -- like a very primitive
MMX/SSE. We then treat said vector as the coefficients of a polynomial, and
that allows us to define multiplication, giving us a full mathematical field.
Finite fields -- and GF(2**8) in particular -- get a ton of use in codes,
in both the "error-correcting code" and "cryptographic code" senses.
However, this implementation has NOT been hardened against timing attacks,
so it MUST NOT be used in cryptography.
Documentation
¶
Overview ¶
Package galoisfield implements the `GF(2**m)` Galois finite fields.
What is a Galois field?
http://mathworld.wolfram.com/FiniteField.html http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-451-principles-of-digital-communication-ii-spring-2005/lecture-notes/chap7.pdf http://www.cs.utsa.edu/~wagner/laws/FFM.html http://research.swtch.com/field
A Galois field, also known as a finite field, is a mathematical field with a number of elements equal to a prime number to a positive integer power. While finite fields with a prime number of elements are familiar to most programmers -- boolean arithmetic, a.k.a. arithmetic `mod 2` is a well-known example -- fields that take that prime to powers higher than 1 is less well-known. Basically, an element of `GF(2**m)` can be seen as a list of `m` bits, where addition and multiplication are elementwise `mod 2` (`a XOR b` for addition, `a AND b` for multiplication) and the remaining rules of field arithmetic follow from linear algebra (vectors, or alternatively, polynomial coefficients).
Short version: an element of `GF(2**8)` element may be represented as a byte (0 ≤ n ≤ 255), but it's really a vector of 8 bits -- like a very primitive MMX/SSE. We then treat said vector as the coefficients of a polynomial, and that allows us to define multiplication, giving us a full mathematical field.
Finite fields -- and `GF(2**8)` in particular -- get a tons of use in codes, in both the "error-correcting code" and "cryptographic code" senses. However, this implementation has NOT been hardened against timing attacks, so it MUST NOT be used in cryptography.
Index ¶
- Variables
- type GF
- func (_ *GF) Add(x, y byte) byte
- func (a *GF) Compare(b *GF) int
- func (gf *GF) Div(x, y byte) byte
- func (a *GF) Equal(b *GF) bool
- func (gf *GF) Exp(x byte) byte
- func (gf *GF) Generator() uint
- func (gf *GF) GoString() string
- func (gf *GF) Inv(x byte) byte
- func (a *GF) Less(b *GF) bool
- func (gf *GF) Log(x byte) byte
- func (gf *GF) Mul(x, y byte) byte
- func (gf *GF) Polynomial() uint
- func (gf *GF) Size() uint
- func (gf *GF) String() string
- type Polynomial
- func (first Polynomial) Add(rest ...Polynomial) Polynomial
- func (a Polynomial) Coefficient(i uint) byte
- func (a Polynomial) Coefficients() []byte
- func (a Polynomial) Compare(b Polynomial) int
- func (a Polynomial) Degree() uint
- func (a Polynomial) Equal(b Polynomial) bool
- func (a Polynomial) Evaluate(x byte) byte
- func (a Polynomial) Field() *GF
- func (a Polynomial) GoString() string
- func (a Polynomial) IsZero() bool
- func (a Polynomial) Less(b Polynomial) bool
- func (first Polynomial) Mul(rest ...Polynomial) Polynomial
- func (a Polynomial) Scale(s byte) Polynomial
- func (a Polynomial) String() string
Constants ¶
This section is empty.
Variables ¶
var ( ErrFieldSize = errors.New("only field sizes 4, 8, 16, 32, 64, 128, and 256 are permitted") ErrPolyOutOfRange = errors.New("polynomial is out of range") ErrReduciblePoly = errors.New("polynomial is reducible") ErrNotGenerator = errors.New("value is not a generator") ErrDivByZero = errors.New("division by zero") ErrLogZero = errors.New("logarithm of zero") )
var ( // GF(4) p=(x^2 + x + 1) g=2 Poly210_g2 = New(4, 0x7, 2) // GF(8) p=(x^3 + x + 1) g=2 Poly310_g2 = New(8, 0xb, 2) // GF(16) p=(x^4 + x + 1) g=2 Poly410_g2 = New(16, 0x13, 2) // GF(32) p=(x^5 + x^2 + 1) g=2 Poly520_g2 = New(32, 0x25, 2) // GF(64) p=(x^6 + x + 1) g=2 Poly610_g2 = New(64, 0x43, 2) // GF(64) p=(x^6 + x + 1) g=7 Poly610_g7 = New(64, 0x43, 7) // GF(128) p=(x^7 + x + 1) g=2 Poly710_g2 = New(128, 0x83, 2) // GF(256), p (x^8 + x^4 + x^3 + x + 1), g 3 Poly84310_g3 = New(256, 0x11b, 0x03) // GF(256), p (x^8 + x^4 + x^3 + x^2 + 1), g 2 Poly84320_g2 = New(256, 0x11d, 0x02) // Some arbitrarily-chosen permutations of GF(n). DefaultGF4 = Poly210_g2 DefaultGF8 = Poly310_g2 DefaultGF16 = Poly410_g2 DefaultGF32 = Poly520_g2 DefaultGF64 = Poly610_g2 DefaultGF128 = Poly710_g2 DefaultGF256 = Poly84320_g2 // Some arbitrarily-chosen permutation of GF(256). Default = DefaultGF256 )
Some handy pre-chosen polynomial/generator combinations.
var (
ErrIncompatibleFields = errors.New("cannot combine polynomials from different finite fields")
)
Functions ¶
This section is empty.
Types ¶
type GF ¶
type GF struct {
// contains filtered or unexported fields
}
GF represents a particular permutation of GF(2**k) for some fixed k.
func New ¶
New takes n (a power of 2), p (a polynomial), and g (a generator), then uses them to construct an instance of GF(n). This comes complete with precomputed g**x and log_g(x) tables, so that all operations take O(1) time.
If n isn't a supported power of 2, if p is reducible or of the wrong degree, or if g isn't actually a generator for the field, this function will panic.
In the following, let k := log_2(n).
The "p" argument describes a polynomial of the form
x**k + ∑_i: p_i*x**i; i ∈ [0..(k-1)]
where the coefficient p_i is ((p>>i)&1), i.e. the i-th bit counting from the LSB. The k-th bit MUST be 1, and all higher bits MUST be 0. Thus, n ≤ p < 2n.
The "g" argument determines the permutation of field elements. The value g chosen must be a generator for the field, i.e. the sequence
g**0, g**1, g**2, ... g**(n-1)
must be a complete list of all elements in the field. The field is small enough that the easiest way to discover generators is trial-and-error.
The "p" and "g" arguments both have no effect on Add. The "g" argument additionally has no effect on (the output of) Mul/Div/Inv. Both arguments affect Exp/Log.
func (*GF) Compare ¶
Compare defines a total order for finite fields: -1 if a < b, 0 if a == b, or +1 if a > b.
func (*GF) Polynomial ¶
Polynomial returns the polynomial used to generate the Galois field.
type Polynomial ¶
type Polynomial struct {
// contains filtered or unexported fields
}
Polynomial implements polynomials with coefficients drawn from a Galois field.
func NewPolynomial ¶
func NewPolynomial(field *GF, coefficients ...byte) Polynomial
NewPolynomial returns a new polynomial with the given coefficients. Coefficients are in little-endian order; that is, the first coefficient is the constant term, the second coefficient is the linear term, etc.
func (Polynomial) Add ¶
func (first Polynomial) Add(rest ...Polynomial) Polynomial
Add returns the sum of one or more polynomials.
func (Polynomial) Coefficient ¶
func (a Polynomial) Coefficient(i uint) byte
Coefficient returns the coefficient of the i'th term.
func (Polynomial) Coefficients ¶
func (a Polynomial) Coefficients() []byte
Coefficients returns the coefficients of the terms of this polynomial. The result is in little-endian order; see NewPolynomial for details.
func (Polynomial) Compare ¶
func (a Polynomial) Compare(b Polynomial) int
Compare defines a partial order for polynomials: -1 if a < b, 0 if a == b, +1 if a > b, or panic if a and b are drawn from different Galois fields.
func (Polynomial) Degree ¶
func (a Polynomial) Degree() uint
Degree returns the degree of this polynomial, with the convention that the polynomial of zero terms has degree 0.
func (Polynomial) Equal ¶
func (a Polynomial) Equal(b Polynomial) bool
Equal returns true iff a == b.
func (Polynomial) Evaluate ¶
func (a Polynomial) Evaluate(x byte) byte
Evaluate substitutes for x and returns the resulting value.
func (Polynomial) Field ¶
func (a Polynomial) Field() *GF
Field returns the Galois field from which this polynomial's coefficients are drawn.
func (Polynomial) GoString ¶
func (a Polynomial) GoString() string
GoString returns a Go-syntax representation of this polynomial.
func (Polynomial) IsZero ¶
func (a Polynomial) IsZero() bool
IsZero returns true iff this polynomial has no terms.
func (Polynomial) Mul ¶
func (first Polynomial) Mul(rest ...Polynomial) Polynomial
Mul returns the product of one or more polynomials.
func (Polynomial) Scale ¶
func (a Polynomial) Scale(s byte) Polynomial
Scale multiplies this polynomial by a scalar.
func (Polynomial) String ¶
func (a Polynomial) String() string
String returns a human-readable algebraic representation of this polynomial.
Source Files