algobra

README

Algobra

Algobra is a collection of packages that implement finite field arithmetic as well as univariate and bivariate polynomials over finite fields.

Installation

Algobra is a package for the Go programming language. Therefore, the following assumes that you have already installed Go on your machine. Otherwise, please refer to the official instructions.

To install the full set of Algobra-packages, you can run

go get github.com/ReneBoedker/algobra/...

Note that this top-level package does not provide any functionality in itself. It simply contains documentation for the package as a whole.

Example usage

For examples on how to use the package, please refer to the documentation.

References

• Gathen, Joachim von zur & Gerhard, Jürgen: Modern Computer Algebra (2013), 3rd edition. Cambridge University Press. ISBN 978-1-107-03903-2.
• Lauritzen, Niels: Concrete Abstract Algebra (2003). Cambridge University Press. ISBN 978-0-521-53410-9
• Lübeck, Frank: Conway polynomials for finite fields
• Stichtenoth, Henning: Algebraic Function Fields and Codes (2009), 2nd edition. Springer. ISBN 978-3-540-76877-7.

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)
	}

	// Define the trace map given by Tr(a)=a^q+a in the Hermitian case
	trace := func(field ff.Field, a ff.Element) ff.Element {
		return a.Pow(field.Char()).Add(a)
	}

	// trInv computes the preimage of a with respect to the trace map.
	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 trace(field, b).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