README
¶
Algobra: Prime Fields
This package implements arithmetic in finite fields of prime cardinality.
Basic usage
To use the package, simply define the field – or fields – that you want to work over. Then construct the needed elements.
// import "github.com/ReneBoedker/algobra/primefield"
ff,err:=primefield.Define(7)
if err!=nil {
// Define returns an error if the characteristic is not a prime (or too large)
}
a:=ff.Element(3)
b:=ff.Element(6)
c:=a.Plus(b) // c = 2
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
}
Using table lookups
By default, the package will perform the computation each time two elements are added or multiplied. If requested by the user, the package will instead precompute the addition and/or multiplication tables for a field, and use a table lookup for the corresponding field operations.
err:=ff.ComputeTables(true,false) // Precompute the addition table
if err!=nil {
// Table exceeds maximal memory usage
}
Documentation
¶
Overview ¶
Package primefield implements finite fields with prime cardinality.
Basic usage ¶
To use the package, simply define the field -- or fields -- that you want to work over. Then construct the needed elements.
ff,err:=Define(7)
if err!=nil {
// Define returns an error if the characteristic is not a prime (or too large)
}
a:=ff.Element(3)
b:=ff.Element(6)
c:=a.Plus(b) // c = 2
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
}
Using table lookups ¶
By default, the package will perform the computation each time two elements are added or multiplied. If requested by the user, the package will instead precompute the addition and/or multiplication tables for a field, and use a table lookup for the corresponding field operations.
err:=ff.ComputeTables(true,false) // Precompute the addition table
if err!=nil {
// Table exceeds maximal memory usage
}
Index ¶
- Constants
- type Element
- func (a *Element) Add(b ff.Element) ff.Element
- 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
- func (a *Element) Uint() uint
- type Field
- func (f *Field) Card() uint
- func (f *Field) Char() uint
- func (f *Field) ComputeTables(add, mult bool, maxMem ...uint) (err error)
- func (f *Field) Element(val interface{}) (ff.Element, error)
- func (f *Field) ElementFromSigned(val int) ff.Element
- func (f *Field) ElementFromString(val 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) String() string
- func (f *Field) Zero() ff.Element
Examples ¶
Constants ¶
const DefaultMaxMem uint = 1 << 19 // 512 MiB
DefaultMaxMem is the default maximal memory consumption for addition and multiplication tables. The value is in KiB.
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 a finite field element.
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) Err ¶
Err returns the error status of a.
Example ¶
package main
import (
"fmt"
"github.com/ReneBoedker/algobra/finitefield/primefield"
)
// Set up the finitefield of 3 elements for examples where the cardinality does
// not matter
func getGf3() *primefield.Field {
out, _ := primefield.Define(3)
return out
}
var gf3 *primefield.Field = getGf3()
func main() {
a := gf3.Zero().Inv()
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. For prime fields, this is always 1.
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.
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.
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 prime cardinality.
If card is not a prime, 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/primefield"
)
func main() {
field, _ := primefield.Define(7)
fmt.Println(field)
_, err := primefield.Define(4)
fmt.Printf("Error: %v", err)
}
Output: Finite field of 7 elements Error: Defining prime field: 4 is not a prime
func (*Field) ComputeTables ¶
ComputeTables will precompute either the addition or multiplication tables (or both) for the field f.
The optional argument maxMem specifies the maximal table size in KiB. If no value is given, a DefaultMaxMem is used. If more than one value is given, only the first is used.
Returns an InputTooLarge-error if the estimated memory usage exceeds the maximal value specified by maxMem.
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/primefield"
)
func main() {
field, _ := primefield.Define(13)
a, _ := field.Element(14)
b, _ := field.Element(-5)
c, _ := field.Element("6")
fmt.Printf("%v, %v, %v", a, b, c)
}
Output: 1, 8, 6
func (*Field) ElementFromSigned ¶
ElementFromSigned defines a new element over f with value val.
The returned element will be reduced modulo the characteristic automatically. Negative values are reduced to a positive remainder (as opposed to the %-operator in Go).
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.
func (*Field) ElementFromUnsigned ¶
ElementFromUnsigned defines a new element over f with value val.
The returned element will automatically be reduced modulo the characteristic.
func (*Field) Elements ¶
Elements returns a slice containing all elements of f.
Example ¶
package main
import (
"fmt"
"github.com/ReneBoedker/algobra/finitefield/primefield"
)
func main() {
field, _ := primefield.Define(7)
for _, v := range field.Elements() {
fmt.Println(v)
}
}
Output: 0 1 2 3 4 5 6
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.
Source Files