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 ¶
- type Element
- func (a *Element) Add(b ff.Element) ff.Element
- func (a *Element) AsBits() uint
- func (a *Element) Copy() ff.Element
- func (a *Element) Equal(b ff.Element) bool
- func (a *Element) Err() error
- func (a *Element) Inv() ff.Element
- func (a *Element) IsNonzero() bool
- func (a *Element) IsOne() bool
- func (a *Element) IsZero() bool
- func (a *Element) Minus(b ff.Element) ff.Element
- func (a *Element) Mult(b ff.Element) ff.Element
- func (a *Element) NTerms() uint
- func (a *Element) Neg() ff.Element
- func (a *Element) Plus(b ff.Element) ff.Element
- func (a *Element) Pow(n uint) ff.Element
- func (a *Element) Prod(b, c ff.Element) ff.Element
- func (a *Element) SetNeg() ff.Element
- func (a *Element) SetUnsigned(val uint) ff.Element
- func (a *Element) String() string
- func (a *Element) Sub(b ff.Element) ff.Element
- func (a *Element) Times(b ff.Element) ff.Element
- type Field
- func (f *Field) Card() uint
- func (f *Field) Char() uint
- func (f *Field) Element(val interface{}) (ff.Element, error)
- func (f *Field) ElementFromBits(val uint) ff.Element
- func (f *Field) ElementFromSigned(val int) ff.Element
- func (f *Field) ElementFromString(s string) (ff.Element, error)
- func (f *Field) ElementFromUnsigned(val uint) ff.Element
- func (f *Field) Elements() []ff.Element
- func (f *Field) MultGenerator() ff.Element
- func (f *Field) One() ff.Element
- func (f *Field) RandElement() ff.Element
- func (f *Field) RegexElement(requireParens bool) string
- func (f *Field) SetVarName(varName string) error
- func (f *Field) String() string
- func (f *Field) VarName() string
- func (f *Field) Zero() ff.Element
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 ¶
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
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) Equal ¶
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 ¶
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 ¶
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) IsOne ¶
IsOne returns a boolean describing whether a is the multiplicative identity.
func (*Element) Minus ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) Prod ¶
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 ¶
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 ¶
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) Sub ¶
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.
type Field ¶
type Field struct {
// contains filtered or unexported fields
}
Field is the implementation of a finite field.
func Define ¶
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) Char ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
MultGenerator returns an element that generates the units of f.
func (*Field) RandElement ¶
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 ¶
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 ¶
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