tableGF

package
v0.0.0-...-70c1fab Latest Latest
Warning

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

Go to latest
Published: Nov 12, 2023 License: MIT Imports: 2 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
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")
)
View Source
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.

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

func New(n, p uint, g byte) *GF

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) Add

func (_ *GF) Add(x, y byte) byte

Add returns x+y == x-y == x^y in GF(2**k).

func (*GF) Compare

func (a *GF) Compare(b *GF) int

Compare defines a total order for finite fields: -1 if a < b, 0 if a == b, or +1 if a > b.

func (*GF) Div

func (gf *GF) Div(x, y byte) byte

Div returns x/y in GF(2**k).

func (*GF) Equal

func (a *GF) Equal(b *GF) bool

Equal returns true iff a == b.

func (*GF) Exp

func (gf *GF) Exp(x byte) byte

Exp returns g**x in GF(2**k).

func (*GF) Generator

func (gf *GF) Generator() uint

Generator returns the exponent base used to generate the Galois field.

func (*GF) Inv

func (gf *GF) Inv(x byte) byte

Inv returns 1/x in GF(2**k).

func (*GF) Less

func (a *GF) Less(b *GF) bool

Less returns true iff a < b.

func (*GF) Log

func (gf *GF) Log(x byte) byte

Log returns log_g(x) in GF(2**k).

func (*GF) Mul

func (gf *GF) Mul(x, y byte) byte

Mul returns x*y in GF(2**k).

func (*GF) Polynomial

func (gf *GF) Polynomial() uint

Polynomial returns the polynomial used to generate the Galois field.

func (*GF) Size

func (gf *GF) Size() uint

Size returns the order of the Galois field, i.e. the number of elements.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL