Documentation ¶
Overview ¶
Package algobra is a collection of packages for finite field arithmetic.
This package does not provide any functionality itself. Instead, this is found in each of the subpackages.
Example (HermitianPlaces) ¶
The so-called places of the Hermitian function field over the finite field of q^2 elements can be represented by pairs (α, β) satisfying α^(q+1)=β^q+β. It is well-known that there are q^3 such pairs, see for instance [Stichtenoth, 2009].
This example computes the pairs (α, β) for q=3.
package main import ( "fmt" "github.com/ReneBoedker/algobra/finitefield" "github.com/ReneBoedker/algobra/finitefield/ff" ) func main() { // Define the norm map given by N(a)=a^(q+1) in the Hermitian case norm := func(field ff.Field, a ff.Element) ff.Element { return a.Pow(field.Char() + 1) } // trInv computes the preimage of a with respect to the trace map. In the // Hermitian case, the trace is given by Tr(a)=a^q+a. trInv := func(field ff.Field, a ff.Element) ([]ff.Element, error) { if !a.Equal(a.Pow(field.Char())) { // The input must be in the image of the trace. // That is, it must be in F_q return nil, fmt.Errorf("%v is not in the image of the trace", a) } out := make([]ff.Element, 0, field.Char()) for _, b := range field.Elements() { // Search for those elements that map to a under the trace map if b.Trace().Equal(a) { out = append(out, b) } // Stop searching once all q solutions have been found if uint(len(out)) == field.Char() { break } } return out, nil } // Define the field and the list of places. field, _ := finitefield.Define(9) places := make([][2]ff.Element, 0, 27) for _, a := range field.Elements() { // Find the preimage of a tmp, err := trInv(field, norm(field, a)) if err != nil { fmt.Println(err) return } // Append the found pairs for _, b := range tmp { places = append(places, [2]ff.Element{a, b}) } } for _, p := range places { fmt.Printf("α = %v, β = %v\n", p[0], p[1]) } }
Output: α = 0, β = 0 α = 0, β = a + 1 α = 0, β = 2a + 2 α = 1, β = a α = 1, β = 2a + 1 α = 1, β = 2 α = a, β = 1 α = a, β = 2a α = a, β = a + 2 α = a + 1, β = a α = a + 1, β = 2a + 1 α = a + 1, β = 2 α = 2a + 1, β = 1 α = 2a + 1, β = 2a α = 2a + 1, β = a + 2 α = 2, β = a α = 2, β = 2a + 1 α = 2, β = 2 α = 2a, β = 1 α = 2a, β = 2a α = 2a, β = a + 2 α = 2a + 2, β = a α = 2a + 2, β = 2a + 1 α = 2a + 2, β = 2 α = a + 2, β = 1 α = a + 2, β = 2a α = a + 2, β = a + 2
Example (SecretSharing) ¶
This example contains a simple illustration of Shamir's secret sharing scheme.
package main import ( "fmt" "github.com/ReneBoedker/algobra/finitefield" "github.com/ReneBoedker/algobra/finitefield/ff" "github.com/ReneBoedker/algobra/univariate" "math/rand" ) func main() { rand.Seed(314159265) // Use a fixed seed for the example // We want 5 participants and any 3 should be able to reconstruct n := 5 recon := 3 // Define the finite field of 9 elements (a smaller field could have been used) gf9, err := finitefield.Define(9) if err != nil { fmt.Println(err) return } r := univariate.DefRing(gf9) // Let the secret be 2a+1 s, err := gf9.ElementFromString("2a+1") if err != nil { fmt.Println(err) return } // Define random polynomial f of degree less than recon conditioned on f(0)=s f := r.Polynomial([]ff.Element{s}) for i := 1; i < recon; i++ { f.SetCoef(i, gf9.RandElement()) } fmt.Printf("The sharing polynomal is f(X) = %v\n\n", f) // Evaluate f in n distinct points, giving the shares points := make([]ff.Element, 0, n) shares := make([]ff.Element, 0, n) for _, p := range gf9.Elements() { if p.IsZero() { // Avoid zero since this evaluates to the secret continue } points = append(points, p) shares = append(shares, f.Eval(p)) if len(shares) == n { break } } fmt.Printf("Points: %v\nShares: %v\n\n", points, shares) // Assume that the first three shares are known knownPoints := points[:3] knownShares := shares[:3] // Use interpolation to find the secret g, err := r.Interpolate(knownPoints, knownShares) if err != nil { fmt.Println(err) return } fmt.Printf("The reconstructed polynomial is g(X) = %v\n", g) fmt.Printf("g(0) = %v\n", g.Eval(gf9.Zero())) }
Output: The sharing polynomal is f(X) = (a + 2)X^2 + 2aX + (2a + 1) Points: [1 a a + 1 2a + 1 2] Shares: [2a 2a 2a + 1 a + 2 a] The reconstructed polynomial is g(X) = (a + 2)X^2 + 2aX + (2a + 1) g(0) = 2a + 1
Directories ¶
Path | Synopsis |
---|---|
Package auxmath contains a number of auxiliary mathematical functions.
|
Package auxmath contains a number of auxiliary mathematical functions. |
Package bivariate implements bivariate polynomials over finite fields.
|
Package bivariate implements bivariate polynomials over finite fields. |
Package errors implements error handling in algobra.
|
Package errors implements error handling in algobra. |
Package finitefield implements finite fields of arbitrary cardinality.
|
Package finitefield implements finite fields of arbitrary cardinality. |
binfield
Package binfield implements finite fields characteristic two.
|
Package binfield implements finite fields characteristic two. |
conway
Package conway contains a database of Conway polynomials.
|
Package conway contains a database of Conway polynomials. |
extfield
Package extfield implements finite fields as extensions of prime fields.
|
Package extfield implements finite fields as extensions of prime fields. |
ff
Package ff contains the interfaces describing finite fields and their elements.
|
Package ff contains the interfaces describing finite fields and their elements. |
primefield
Package primefield implements finite fields with prime cardinality.
|
Package primefield implements finite fields with prime cardinality. |
Package univariate implements univariate polynomials over finite fields.
|
Package univariate implements univariate polynomials over finite fields. |
Click to show internal directories.
Click to hide internal directories.