binfield

package
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Feb 18, 2022 License: BSD-3-Clause Imports: 11 Imported by: 0

README

Go Report Card coverage-badge GoDoc

Algobra: Binary Fields

This package implements arithmetic in finite fields of characteristic two. These can also be obtained from the general implementation in algobra/extfield, but the implementation in the binfield-package is more efficient.

Basic usage

Arithmetic operations

The Element objects have methods Add, Sub, Mult, and Inv for the basic field operations. Of these four, only Inv allocates a new object. The other methods store the result in the receiving element object. For instance, a.Add(b) would evaluate the sum a+b, and then set a to this value. If the result is to be stored in a new object, the package provides the methods Plus, Minus, and Times, which evaluate the arithmetic operation and returns the result in a new object.

Additional functions such as Neg and Pow are also defined. For details, please refer to the documentation.

Equality testing

To test if two elements a and b are equal, a == b will not work since this compares pointers rather than the underlying data. Instead, use a.Equal(b). In addition, the expressions a.IsZero(), a.IsNonzero(), and a.IsOne() provide shorthands for common comparisons.

Error handling

In order to allow method chaining for arithmetic operations – such as a.Add(b).Mult(c.Inv()) – the methods themselves do not return errors. Instead, potential errors are tied to the resulting field element, and the error can be retrieved with the Err-method. For instance, you might do something like this:

a:=field.Element(0).Inv()
if a.Err()!=nil {
    // Handle error
}

References

Documentation

Overview

Package binfield implements finite fields characteristic two.

These can also be obtained from the general implementation in extfield, but the implementation in the binfield-package is more efficient.

Arithmetic operations

The Element objects have methods Add, Sub, Mult, and Inv for the basic field operations. Of these four, only Inv allocates a new object. The other methods store the result in the receiving element object. For instance, a.Add(b) would evaluate the sum a+b, and then set a to this value. If the result is to be stored in a new object, the package provides the methods Plus, Minus, and Times, which evaluate the arithmetic operation and returns the result in a new object.

Additional functions such as Neg and Pow are also defined.

Equality testing

To test if two elements a and b are equal, a == b will not work since this compares pointers rather than the underlying data. Instead, use a.Equal(b). In addition, the expressions a.IsZero(), a.IsNonzero(), and a.IsOne() provide shorthands for common comparisons.

Error handling

In order to allow method chaining for arithmetic operations -- such as a.Add(b).Mult(c.Inv()) -- the methods themselves do not return errors. Instead, potential errors are tied to the resulting field element, and the error can be retrieved with the Err-method. For instance, you might do something like this: 

a:=field.Element(0).Inv()
if a.Err()!=nil {
	// Handle error
}

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Element 

type Element struct {
	// contains filtered or unexported fields
}

Element is the implementation of an element in a finite field.

func (*Element) Add 

func (a *Element) Add(b ff.Element) ff.Element

Add sets a to the sum of a and b. It then returns a.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) AsBits added in v0.1.1 

func (a *Element) AsBits() uint

AsBits returns the bitstring representation of a. That is, the i'th bit in the output gives the coefficient of the i'th term in the representation of the element.

See also ElementFromBits.

func (*Element) Copy 

func (a *Element) Copy() ff.Element

Copy returns a copy of a.

func (*Element) Equal 

func (a *Element) Equal(b ff.Element) bool

Equal tests equality of elements a and b.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	gf64, _ := binfield.Define(64)
	gf256, _ := binfield.Define(256)

	a := gf64.One()
	b := gf64.ElementFromSigned(1)
	c := gf64.ElementFromBits(0b10)
	d := gf256.One()

	fmt.Printf(
		"a == b: %t\na == c: %t\na == d: %t",
		a.Equal(b), a.Equal(c), a.Equal(d))
}

Output:

a == b: true
a == c: false
a == d: false

func (*Element) Err 

func (a *Element) Err() error

Err returns the error status of a.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

// Set up the finitefield of 4 elements for examples where the cardinality does
// not matter
func getGf4() *binfield.Field {
	out, _ := binfield.Define(4)
	return out
}

var gf4 *binfield.Field = getGf4()

func main() {
	a := gf4.Zero().Inv()
	if a.Err() != nil {
		fmt.Println(a.Err())
	}
}

Output:

Inverting element: Cannot invert zero element

func (*Element) Inv 

func (a *Element) Inv() ff.Element

Inv returns the inverse of a.

If a is the zero element, the return value is an element with InputValue-error as error status.

func (*Element) IsNonzero 

func (a *Element) IsNonzero() bool

IsNonzero returns a boolean describing whether a is a non-zero element.

func (*Element) IsOne 

func (a *Element) IsOne() bool

IsOne returns a boolean describing whether a is the multiplicative identity.

func (*Element) IsZero 

func (a *Element) IsZero() bool

IsZero returns a boolean describing whether a is the additive identity.

func (*Element) Minus 

func (a *Element) Minus(b ff.Element) ff.Element

Minus returns the difference of elements a and b.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) Mult 

func (a *Element) Mult(b ff.Element) ff.Element

Mult sets a to the product of elements a and b. It then returns a.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) NTerms 

func (a *Element) NTerms() uint

NTerms returns the number of terms in the representation of a.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

// Set up the finitefield of 4 elements for examples where the cardinality does
// not matter
func getGf4() *binfield.Field {
	out, _ := binfield.Define(4)
	return out
}

var gf4 *binfield.Field = getGf4()

func main() {
	a := gf4.ElementFromBits(0b11) // a + 1
	b := gf4.One()

	fmt.Printf("%d, %d", a.NTerms(), b.NTerms())
}

Output:

2, 1

func (*Element) Neg 

func (a *Element) Neg() ff.Element

Neg returns a scaled by negative one (modulo the characteristic). Since the field has characteristic two, this function simply returns a copy of a.

func (*Element) Plus 

func (a *Element) Plus(b ff.Element) ff.Element

Plus returns the sum of elements a and b.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) Pow 

func (a *Element) Pow(n uint) ff.Element

Pow returns a raised to the power of n.

func (*Element) Prod 

func (a *Element) Prod(b, c ff.Element) ff.Element

Prod sets a to the product of b and c. It then returns a.

The function returns an ArithmeticIncompat-error if b, and c are not defined over the same field.

When b or c has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) SetNeg 

func (a *Element) SetNeg() ff.Element

SetNeg sets a to a scaled by negative one (modulo the characteristic). It then returns a. Since the field has characteristic two, this function simply returns a.

func (*Element) SetUnsigned 

func (a *Element) SetUnsigned(val uint) ff.Element

SetUnsigned sets the value of a to the element corresponding to val. It then returns a.

The value is automatically reduced modulo the characteristic.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

// Set up the finitefield of 4 elements for examples where the cardinality does
// not matter
func getGf4() *binfield.Field {
	out, _ := binfield.Define(4)
	return out
}

var gf4 *binfield.Field = getGf4()

func main() {
	a := gf4.ElementFromBits(0b11) // a+1
	a.SetUnsigned(0)
	fmt.Println(a)
}

Output:

0

func (*Element) String 

func (a *Element) String() string

String returns the string representation of a.

func (*Element) Sub 

func (a *Element) Sub(b ff.Element) ff.Element

Sub sets a to the difference of elements a and b. It then returns a.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

func (*Element) Times 

func (a *Element) Times(b ff.Element) ff.Element

Times returns the product of elements a and b.

If a and b are defined over different fields, a new element is returned with an ArithmeticIncompat-error as error status.

When a or b has a non-nil error status, its error is wrapped and the same element is returned.

type Field 

type Field struct {
	// contains filtered or unexported fields
}

Field is the implementation of a finite field.

func Define 

func Define(card uint) (*Field, error)

Define creates a new finite field with given cardinality.

If card is not a power of two, the package returns an InputValue-error. If card implies that multiplication will overflow uint, the function returns an InputTooLarge-error.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(256)
	fmt.Println(field)

	_, err := binfield.Define(49)
	fmt.Printf("Error: %v", err)
}

Output:

Finite field of 256 elements
Error: Defining binary field: The cardinality of a binary field must be a power of 2

func (*Field) Card 

func (f *Field) Card() uint

Card returns the cardinality of f.

func (*Field) Char 

func (f *Field) Char() uint

Char returns the characteristic of f.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(1024)
	fmt.Println(field.Char())
}

Output:

2

func (*Field) Element 

func (f *Field) Element(val interface{}) (ff.Element, error)

Element defines a new element over f with value val, which must be either uint, int, or string.

If type of val is unsupported, the function returns an Input-error.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(16)

	a, _ := field.Element(uint(7))
	b, _ := field.Element(-2)
	c, _ := field.Element("a + a^2 + 1")

	fmt.Printf("%v, %v, %v", a, b, c)
}

Output:

1, 0, a^2 + a + 1

func (*Field) ElementFromBits 

func (f *Field) ElementFromBits(val uint) ff.Element

ElementFromBits defines a new element over f with value specified by the bitstring val. That is, the i'th bit in val determines the coefficient of the i'th term in the representation of the element.

The returned element will automatically be reduced modulo the characteristic.

See also AsBits.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(16)

	a := field.ElementFromBits(0b1101)
	b := field.ElementFromBits(0b11)

	fmt.Printf("%v, %v", a, b)
}

Output:

a^3 + a^2 + 1, a + 1

func (*Field) ElementFromSigned 

func (f *Field) ElementFromSigned(val int) ff.Element

ElementFromSigned defines a new element over f with value val.

The returned element will be reduced modulo the characteristic automatically. That is, the additive identity is returned if val is even, and the multiplicative identity is returned if val is odd.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(8)

	a := field.ElementFromSigned(-3)
	b := field.ElementFromSigned(4)

	fmt.Printf("%v, %v", a, b)
}

Output:

1, 0

func (*Field) ElementFromString 

func (f *Field) ElementFromString(s string) (ff.Element, error)

ElementFromString defines a new element over f from the given string.

A Parsing-error is returned if the string cannot be parsed.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(8)

	for _, s := range [...]string{"a+1", "a + a^2 -1", "a+b"} {
		a, err := field.ElementFromString(s)
		if err != nil {
			fmt.Println(err)
		} else {
			fmt.Println(a)
		}
	}
}

Output:

a + 1
a^2 + a + 1
Defining element from string: Cannot parse a+b; lengths do not match (1 ≠ 3).

func (*Field) ElementFromUnsigned 

func (f *Field) ElementFromUnsigned(val uint) ff.Element

ElementFromUnsigned defines a new element over f with value specified by val.

The returned element will automatically be reduced modulo the characteristic. That is, the additive identity is returned if val is even, and the multiplicative identity is returned if val is odd.

func (*Field) Elements 

func (f *Field) Elements() []ff.Element

Elements returns a slice containing all elements of f.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(8)
	for _, v := range field.Elements() {
		fmt.Println(v)
	}
}

Output:

0
1
a
a + 1
a^2
a^2 + 1
a^2 + a
a^2 + a + 1

func (*Field) MultGenerator 

func (f *Field) MultGenerator() ff.Element

MultGenerator returns an element that generates the units of f.

func (*Field) One 

func (f *Field) One() ff.Element

One returns the multiplicative identity in f.

func (*Field) RandElement 

func (f *Field) RandElement() ff.Element

RandElement returns a pseudo-random element in f.

This function uses the default source from the math/rand package. The seed is set automatically when loading the primefield package, but a new seed can be set by calling rand.Seed().

The pseudo-random generator used is not cryptographically safe.

func (*Field) RegexElement 

func (f *Field) RegexElement(requireParens bool) string

RegexElement returns a string containing a regular expression describing an element of f.

The input argument requireParens indicates whether parentheses are required around elements containing several terms. This has no effect for prime fields.

func (*Field) SetVarName 

func (f *Field) SetVarName(varName string) error

SetVarName sets the variable name to be used in the given quotient ring.

Leading and trailing whitespace characters are removed before setting the variable name. If the string consists solely of whitespace characters, an InputValue-error is returned.

Additionally, the variable name is not allowed to be "0" or "1". If this is the case, an InputValue-error is returned.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield/binfield"
)

func main() {
	field, _ := binfield.Define(8)

	a := field.ElementFromBits(0b101)
	fmt.Println(a)

	field.SetVarName("y")
	fmt.Println(a)
}

Output:

a^2 + 1
y^2 + 1

func (*Field) String 

func (f *Field) String() string

String returns the string representation of f.

func (*Field) VarName 

func (f *Field) VarName() string

VarName returns the string used to represent the variable of r.

func (*Field) Zero 

func (f *Field) Zero() ff.Element

Zero returns the additive identity in f.

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.