gf

Documentation

Overview

Package gf implements operations over finite fields *of prime order*. As such only a subset of fields is supported, each corresponding to the ring of integers modulo p.

Index

• func BasePolynomial(j int, xs []*big.Int, field GF) *big.Int
• type GF
  • func NewGF(order *big.Int) (GF, error)
  • func (gf *GF) Add(a *big.Int, b *big.Int) *big.Int
  • func (gf *GF) Div(a *big.Int, b *big.Int) *big.Int
  • func (gf *GF) Exp(b *big.Int, e *big.Int) *big.Int
  • func (gf *GF) IsGroupElement(x *big.Int) bool
  • func (gf *GF) Mul(a *big.Int, b *big.Int) *big.Int
  • func (gf *GF) MultInverse(a *big.Int) *big.Int
  • func (gf *GF) Rand() (*big.Int, error)
  • func (gf *GF) RandomPolynomial(degree int) (Polynomial, error)
  • func (gf *GF) Sub(a *big.Int, b *big.Int) *big.Int
• type Polynomial
  • func NewPolynomial(degree int, field GF) (Polynomial, error)
  • func (pol *Polynomial) Degree() int
  • func (pol *Polynomial) Evaluate(x *big.Int) (*big.Int, error)
  • func (pol *Polynomial) String() string

Functions

func BasePolynomial

func BasePolynomial(j int, xs []*big.Int, field GF) *big.Int

BasePolynomial calculates the Lagrange base polynomial `l_j` *at position 0*, ie `l_j(0)`.

Recall the general Lagrange base polynomial: `l_j(x) = Product for m = 0 to k, where m != k [ (x - x_m) / (x_j - x_m) ] For x = 0 this simplifies to: `l_j(0) = Product for m = 0 to k, where m != k [ x_m / (x_m - x_j) ]

This simplification is sufficient to calculate the value of the polynomial at x = 0, which is all we need for retrieving the secret. It has the benefit that each evaluate of a base polynomial is a scalar rather than a polynomial.

Types

type GF

type GF struct {
	P *big.Int
}

GF implements a finite field of prime order

func NewGF

func NewGF(order *big.Int) (GF, error)

NewGF creates a new finite field.

Returns an error if the order is not prime.

func (*GF) Add

func (gf *GF) Add(a *big.Int, b *big.Int) *big.Int

Add performs addition in the finite field `gf`.

func (*GF) Div

func (gf *GF) Div(a *big.Int, b *big.Int) *big.Int

Div performs division in the finite field `gf`.

func (*GF) Exp

func (gf *GF) Exp(b *big.Int, e *big.Int) *big.Int

Exp performs modular exponentiation in the finite field `gf`.

func (*GF) IsGroupElement

func (gf *GF) IsGroupElement(x *big.Int) bool

IsGroupElement checks if a value is an element of group `gf`.

func (*GF) Mul

func (gf *GF) Mul(a *big.Int, b *big.Int) *big.Int

Mul performs multiplication in the finite field `gf`.

func (*GF) MultInverse

func (gf *GF) MultInverse(a *big.Int) *big.Int

MultInverse calculates the modular multiplicative inverse in the finite field `gf`.

func (*GF) Rand

func (gf *GF) Rand() (*big.Int, error)

Rand returns a random rember of the finite field `gf`.

func (*GF) RandomPolynomial

func (gf *GF) RandomPolynomial(degree int) (Polynomial, error)

RandomPolynomial returns a random polynomial over the finite field `gf`.

func (*GF) Sub

func (gf *GF) Sub(a *big.Int, b *big.Int) *big.Int

Sub performs subtraction in the finite field `gf`.

type Polynomial

type Polynomial struct {
	// Field the polynomial is in
	Field GF
	// Coefficients of the polynomial, ordered from the lowest degree to
	// the highest
	Coefficients []*big.Int
}

Polynomial over a finite field

func NewPolynomial

func NewPolynomial(degree int, field GF) (Polynomial, error)

NewPolynomial initializes a new polynomial of given degree in the given field.

func (*Polynomial) Degree

func (pol *Polynomial) Degree() int

Degree returns the degree of the polynomial

func (*Polynomial) Evaluate

func (pol *Polynomial) Evaluate(x *big.Int) (*big.Int, error)

Evaluate evaluates the polynomial at a given point

Returns an error if the provided value is not a valid group element.

func (*Polynomial) String

func (pol *Polynomial) String() string

Return a string representation of this polynomial for printing purposes.