README
¶
Algobra: Extension Fields
This package implements arithmetic in finite fields of any prime power cardinality.
If you need finite fields of extension degree one – that is, prime fields – algobra/primefield provides a more efficient implementation. If both prime fields and extension fields are needed, consider using algobra/finitefields instead.
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
- Frank Lübeck: Conway polynomials for finite fields
Documentation
¶
Overview ¶
Package extfield implements finite fields as extensions of prime fields.
If you need finite fields of extension degree one -- that is, prime fields -- algobra/primefield provides a more efficient implementation. If both prime fields and extension fields are needed, consider using algobra/finitefields instead.
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 ¶
- 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
- type Field
- func (f *Field) Card() uint
- func (f *Field) Char() uint
- func (f *Field) ComputeMultTable(maxMem ...uint) (err error)
- func (f *Field) Element(val interface{}) (ff.Element, error)
- func (f *Field) ElementFromSigned(val int) ff.Element
- func (f *Field) ElementFromSignedSlice(val []int) ff.Element
- func (f *Field) ElementFromString(val string) (ff.Element, error)
- func (f *Field) ElementFromUnsigned(val uint) ff.Element
- func (f *Field) ElementFromUnsignedSlice(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 a table of discrete logs. 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 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) Err ¶
Err returns the error status of a.
Example ¶
package main
import (
"fmt"
"github.com/ReneBoedker/algobra/finitefield/extfield"
)
// Set up the finitefield of 4 elements for examples where the cardinality does
// not matter
func getGf4() *extfield.Field {
out, _ := extfield.Define(4)
return out
}
var gf4 *extfield.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/extfield"
)
// Set up the finitefield of 4 elements for examples where the cardinality does
// not matter
func getGf4() *extfield.Field {
out, _ := extfield.Define(4)
return out
}
var gf4 *extfield.Field = getGf4()
func main() {
a := gf4.ElementFromUnsignedSlice([]uint{1, 1}) // a + 1
b := gf4.One()
fmt.Printf("%d, %d", a.NTerms(), b.NTerms())
}
Output: 2, 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 given cardinality.
If card is not a prime power, the package returns an InputValue-error.
Example ¶
package main
import (
"fmt"
"github.com/ReneBoedker/algobra/finitefield/extfield"
)
func main() {
field, _ := extfield.Define(9)
fmt.Println(field)
_, err := extfield.Define(10)
fmt.Printf("Error: %v", err)
}
Output: Finite field of 9 elements Error: Defining prime field: Factorizing prime power: 10 does not seem to be a prime power.
func (*Field) ComputeMultTable ¶
ComputeMultTable will precompute the table of discrete logarithms for the field f.
The optional argument maxMem specifies the maximal table size in KiB. If no value is given, a default value 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, []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/extfield"
)
func main() {
field, _ := extfield.Define(25)
a, _ := field.Element(6)
b, _ := field.Element([]int{3, -1})
c, _ := field.Element("2a+4")
fmt.Printf("%v, %v, %v", a, b, c)
}
Output: 1, 4a + 3, 2a + 4
func (*Field) ElementFromSigned ¶
ElementFromSigned defines a new element over f with values specified by 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) ElementFromSignedSlice ¶
ElementFromSignedSlice defines a new element over f with values specified by 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 specified by val.
The returned element will automatically be reduced modulo the characteristic.
func (*Field) ElementFromUnsignedSlice ¶
ElementFromUnsignedSlice defines a new element over f with value specified by 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/extfield"
)
func main() {
field, _ := extfield.Define(9)
for _, v := range field.Elements() {
fmt.Println(v)
}
}
Output: 0 1 2 a a + 1 a + 2 2a 2a + 1 2a + 2
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 should be required around elements containing several terms.
Source Files