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.