Documentation
¶
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) 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
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.
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.