univariate

package
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 18, 2022 License: BSD-3-Clause Imports: 7 Imported by: 0

README

Go Report Card coverage-badge GoDoc

Algobra: Univariate Polynomials

This package implements univariate polynomials over prime fields.

Basic usage

To perform computations on univariate polynomials, first define the finite field and the polynomial ring. Polynomials can then be constructed in several different ways.

field, _ := finitefield.Define(7)	// Ignoring errors in example
ring := bivariate.DefRing(field)

// Define f = 3X^5+2X^2+6
f := ring.PolynomialFromUnsigned([]uint{6,0,2,0,0,3})

// The same polynomial can be defined from 
g := ring.PolynomialFromSigned([]int{-1,0,2,0,0,-4})

fmt.Println(f.Equal(g))	// Prints 'true'

In addition to the polynomial definition from maps as above, it is also possible to define polynomials from strings in a natural way by using PolynomialFromString. When doing so, each monomial can contain at most one of each variable. The order of the variables does not matter, and capitalization is ignored. Using * to indicate multiplication is optional. In addition, the parser supports Singular-style exponents, meaning that 5X2 is interpreted as 5X^2.

Ideals

The package provides support for computations modulo an ideal.

// Let ring be defined as above
id, _ := ring.NewIdeal(
	ring.PolynomialFromString("X^49-X"),
)
qRing, _ := ring.Quotient(id)

Once the quotient ring has been defined, polynomials are defined as before. For instance, h := qRing.PolynomialFromString("X^50") sets h to X^2 since the polynomial is automatically reduced modulo the ideal.

Internally, this is achieved by finding a single element that generates the ideal. Hence, calling Generators at a later point will not necessarily return the polynomials that were used to define the ideal. Instead, it will return the greatest common divisor of these polynomials.

Error handling

In order to allow method chaining for arithmetic operations – such as f.Plus(g).Mult(h.Inv()) – the methods themselves do not return errors. Instead, potential errors are tied to the resulting polynomial, and the error can be retrieved with the Err-method.

Documentation

Overview

Package univariate implements univariate polynomials over finite fields.

Basic usage

To perform computations on univariate polynomials, first define the finite field and the polynomial ring. Polynomials can then be constructed in several different ways. 

field, _ := finitefield.Define(7)   // Ignoring errors in example
ring := bivariate.DefRing(field)

// Define f = 3X^5+2X^2+6
f := ring.PolynomialFromUnsigned([]uint{6,0,2,0,0,3})

// The same polynomial can be defined from
g := ring.PolynomialFromSigned([]int{-1,0,2,0,0,-4})

fmt.Println(f.Equal(g))	// Prints 'true'

In addition to the polynomial definition from maps as above, it is also possible to define polynomials from strings in a natural way by using PolynomialFromString. When doing so, each monomial can contain at most one of each variable. The order of the variables does not matter, and capitalization is ignored. Using * to indicate multiplication is optional. In addition, the parser supports Singular-style exponents, meaning that 5X2 is interpreted as 5X^2.

Ideals

The package provides support for computations modulo an ideal. 

// Let ring be defined as above
id, _ := ring.NewIdeal(
    ring.PolynomialFromString("X^49-X"),
)
qRing, _ := ring.Quotient(id)

Once the quotient ring has been defined, polynomials are defined as before. For instance, h := qRing.PolynomialFromString("X^50") sets h to X^2 since the polynomial is automatically reduced modulo the ideal.

Internally, this is achieved by finding a single element that generates the ideal. Hence, calling Generator at a later point will not return the polynomials that were used to define the ideal, unless there was only one generator. Instead, it will return the greatest common divisor of these polynomials.

Error handling

In order to allow method chaining for arithmetic operations -- such as f.Plus(g).Mult(h.Inv()) -- the methods themselves do not return errors. Instead, potential errors are tied to the resulting polynomial, and the error can be retrieved with the Err-method.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Ideal 

type Ideal struct {
	// contains filtered or unexported fields
}

Ideal is the implementation of a polynomial ideal.

func (*Ideal) Copy 

func (id *Ideal) Copy() *Ideal

Copy creates a copy of id.

func (*Ideal) Generator 

func (id *Ideal) Generator() *Polynomial

Generator returns a copy of the generator of id.

func (*Ideal) Reduce 

func (id *Ideal) Reduce(f *Polynomial) error

Reduce sets f to f modulo id.

func (*Ideal) ShortString 

func (id *Ideal) ShortString() string

ShortString returns a short string description of id. More precisely, it returns the string representation of the generators.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf7, _ := finitefield.Define(7)
	ring := univariate.DefRing(gf7)

	f, _ := ring.PolynomialFromString("X^7-X")
	id, _ := ring.NewIdeal(f)

	fmt.Println(id.ShortString())
}

Output:

<X^7 + 6X>

func (*Ideal) String 

func (id *Ideal) String() string

String returns the string representation of id. See also ShortString.

type Polynomial 

type Polynomial struct {
	// contains filtered or unexported fields
}

Polynomial denotes a bivariate polynomial.

func Gcd 

func Gcd(f *Polynomial, g ...*Polynomial) (*Polynomial, error)

Gcd returns the greatest common divisor of the given polynomials.

An InputIncompatible-error is returned if the polynomials are not defined over the same ring.

func (*Polynomial) Add 

func (f *Polynomial) Add(g *Polynomial) *Polynomial

Add sets f to the sum of the two polynomials f and g and returns f.

If f and g are defined over different rings, a new polynomial is returned with an ArithmeticIncompat-error as error status.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

func (*Polynomial) BaseField 

func (f *Polynomial) BaseField() ff.Field

BaseField returns the field over which the coefficients of f are defined.

func (*Polynomial) Coef 

func (f *Polynomial) Coef(deg int) ff.Element

Coef returns the coefficient of the monomial with degree specified by the input. The return value is a finite field element.

func (*Polynomial) Coefs 

func (f *Polynomial) Coefs() []ff.Element

Coefs returns a slice containing the coefficients of f.

The i'th element of the resulting slice is the coefficient of degree i.

func (*Polynomial) Copy 

func (f *Polynomial) Copy() *Polynomial

Copy returns a new polynomial object over the same ring and with the same coefficients as f.

func (*Polynomial) DecrementCoef 

func (f *Polynomial) DecrementCoef(deg int, val ff.Element)

DecrementCoef decrements the coefficient of the monomial with degree deg in f by val.

func (*Polynomial) Degrees 

func (f *Polynomial) Degrees() []int

Degrees returns a slice containing the degrees in the support of f.

The list is sorted with higher degrees preceding lower ones in the list.

func (*Polynomial) EmbedIn 

func (f *Polynomial) EmbedIn(r *QuotientRing, reduce bool) error

EmbedIn embeds f in the ring r if possible. The input reduce determines if f is reduced in the new ring.

An InputIncompatible-error is returned if r and the polynomial ring of f are not compatible.

func (*Polynomial) Equal 

func (f *Polynomial) Equal(g *Polynomial) bool

Equal determines whether two polynomials are equal. That is, whether they are defined over the same ring, and have the same coefficients.

func (*Polynomial) Err 

func (f *Polynomial) Err() error

Err returns the error status of f.

func (*Polynomial) Eval 

func (f *Polynomial) Eval(point ff.Element) ff.Element

Eval evaluates f at the given point.

func (*Polynomial) IncrementCoef 

func (f *Polynomial) IncrementCoef(deg int, val ff.Element)

IncrementCoef increments the coefficient of the monomial with degree deg in f by val.

func (*Polynomial) IsMonomial 

func (f *Polynomial) IsMonomial() bool

IsMonomial returns a bool describing whether f consists of a single monomial.

func (*Polynomial) IsNonzero 

func (f *Polynomial) IsNonzero() bool

IsNonzero determines whether f contains some monomial with nonzero coefficient.

func (*Polynomial) IsOne 

func (f *Polynomial) IsOne() bool

IsOne determines whether f is the constant 1.

func (*Polynomial) IsZero 

func (f *Polynomial) IsZero() bool

IsZero determines whether f is the zero polynomial.

func (*Polynomial) Lc 

func (f *Polynomial) Lc() ff.Element

Lc returns the leading coefficient of f.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf9, _ := finitefield.Define(9)
	ring := univariate.DefRing(gf9)
	f, _ := ring.PolynomialFromString("(a+2)X^4 + aX^2 + (2a+2)X - 1")

	fmt.Println(f.Lc())
}

Output:

a + 2

func (*Polynomial) Ld 

func (f *Polynomial) Ld() int

Ld returns the leading degree of f.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf9, _ := finitefield.Define(9)
	ring := univariate.DefRing(gf9)
	f, _ := ring.PolynomialFromString("(a+2)X^4 + aX^2 + (2a+2)X - 1")

	fmt.Println(f.Ld())
}

Output:

4

func (*Polynomial) Lt 

func (f *Polynomial) Lt() *Polynomial

Lt returns the leading term of f.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf9, _ := finitefield.Define(9)
	ring := univariate.DefRing(gf9)
	f, _ := ring.PolynomialFromString("(a+2)X^4 + aX^2 + (2a+2)X - 1")

	fmt.Println(f.Lt())
}

Output:

(a + 2)X^4

func (*Polynomial) Minus 

func (f *Polynomial) Minus(g *Polynomial) *Polynomial

Minus returns polynomial difference f-g.

If f and g are defined over different rings, a new polynomial is returned with an ArithmeticIncompat-error as error status.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

func (*Polynomial) Mult 

func (f *Polynomial) Mult(g *Polynomial) *Polynomial

Mult sets f to the product of the polynomials f and g and returns f.

If f and g are defined over different rings, a new polynomial is returned with an ArithmeticIncompat-error as error status.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

func (*Polynomial) NTerms 

func (f *Polynomial) NTerms() (c uint)

NTerms returns the number of terms in f.

func (*Polynomial) Neg 

func (f *Polynomial) Neg() *Polynomial

Neg returns the polynomial obtained by scaling f by -1 (modulo the characteristic).

func (*Polynomial) Normalize 

func (f *Polynomial) Normalize() *Polynomial

Normalize creates a new polynomial obtained by normalizing f. That is, f.Normalize() multiplied by f.Lc() is f.

If f is the zero polynomial, a copy of f is returned.

func (*Polynomial) Plus 

func (f *Polynomial) Plus(g *Polynomial) *Polynomial

Plus returns the sum of the two polynomials f and g.

If f and g are defined over different rings, a new polynomial is returned with an ArithmeticIncompat-error as error status.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

func (*Polynomial) Pow 

func (f *Polynomial) Pow(n uint) *Polynomial

Pow raises f to the power of n.

If the computation causes the degree of f to overflow, the returned polynomial has an Overflow-error as error status.

func (*Polynomial) QuoRem 

func (f *Polynomial) QuoRem(list ...*Polynomial) (q []*Polynomial, r *Polynomial, err error)

QuoRem returns the polynomial quotient and remainder under division by the given list of polynomials.

func (*Polynomial) Scale 

func (f *Polynomial) Scale(c ff.Element) *Polynomial

Scale scales all coefficients of f by the field element c and returns the result as a new polynomial.

func (*Polynomial) SetCoef 

func (f *Polynomial) SetCoef(deg int, val ff.Element) *Polynomial

SetCoef sets the coefficient of the monomial with degree deg in f to val. It returns f itself.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf4, _ := finitefield.Define(4)
	ring := univariate.DefRing(gf4)

	f := ring.One().SetCoef(25, gf4.One())
	fmt.Println(f)
}

Output:

X^25 + 1

func (*Polynomial) SetCoefPtr 

func (f *Polynomial) SetCoefPtr(deg int, val ff.Element) *Polynomial

SetCoefPtr sets the coefficient of the monomial with degree deg in f to val as a pointer. It returns f itself.

func (*Polynomial) SetNeg 

func (f *Polynomial) SetNeg() *Polynomial

SetNeg returns the polynomial obtained by scaling f by -1 (modulo the characteristic).

func (*Polynomial) SetScale 

func (f *Polynomial) SetScale(c ff.Element) *Polynomial

SetScale scales all coefficients of f by the field element c. It then returns f.

func (*Polynomial) SetZero 

func (f *Polynomial) SetZero()

SetZero sets f to the zero polynomial.

func (*Polynomial) String 

func (f *Polynomial) String() string

String returns the string representation of f. The variable is named according to the ring used.

func (*Polynomial) Sub 

func (f *Polynomial) Sub(g *Polynomial) *Polynomial

Sub sets f to the polynomial difference f-g and returns f.

If f and g are defined over different rings, the error status of f is set to ArithmeticIncompat.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

func (*Polynomial) Times 

func (f *Polynomial) Times(g *Polynomial) *Polynomial

Times returns the product of the polynomials f and g

If f and g are defined over different rings, a new polynomial is returned with an ArithmeticIncompat-error as error status.

When f or g has a non-nil error status, its error is wrapped and the same polynomial is returned.

type QuotientRing 

type QuotientRing struct {
	// contains filtered or unexported fields
}

QuotientRing denotes a polynomial quotient ring. The quotient may be trivial, in which case, the object acts as a ring.

func DefRing 

func DefRing(field ff.Field) *QuotientRing

DefRing defines a new polynomial ring over the given field. It returns a new ring-object

func (*QuotientRing) Interpolate 

func (r *QuotientRing) Interpolate(
	points []ff.Element,
	values []ff.Element,
) (*Polynomial, error)

Interpolate computes the Lagrange interpolation polynomial evaluating to values in the specified points. The resulting polynomial has degree at most len(points).

It returns an InputValue-error if the number of points and values differ, or if points are not distinct.

func (*QuotientRing) NewIdeal 

func (r *QuotientRing) NewIdeal(generators ...*Polynomial) (*Ideal, error)

NewIdeal returns a new polynomial ideal over the given ring. If the generators are not defined over the given ring, the function returns an InputIncompatible-error.

Internally, this computes the greatest common divisor of the generators to find a single generator.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf7, _ := finitefield.Define(7)
	ring := univariate.DefRing(gf7)

	f, _ := ring.PolynomialFromString("X^7-X")
	id, _ := ring.NewIdeal(f)

	fmt.Println(id)
}

Output:

Ideal <X^7 + 6X> of Univariate polynomial ring in X over Finite field of 7 elements

func (*QuotientRing) One 

func (r *QuotientRing) One() *Polynomial

One returns the degree zero polynomial over the specified ring with coefficient 1.

func (*QuotientRing) Polynomial 

func (r *QuotientRing) Polynomial(coefs []ff.Element) *Polynomial

Polynomial defines a new polynomial with the given coefficients. The coefficient of X^i is set to coefs[i].

func (*QuotientRing) PolynomialFromSigned 

func (r *QuotientRing) PolynomialFromSigned(coefs []int) *Polynomial

PolynomialFromSigned defines a new polynomial with the given coefficients. The coefficient of X^i is set to coefs[i].

func (*QuotientRing) PolynomialFromString 

func (r *QuotientRing) PolynomialFromString(s string) (*Polynomial, error)

PolynomialFromString defines a polynomial by parsing s.

The string s must use 'X' of 'x' as variable names. Multiplication symbol '*' is allowed, but not necessary. Additionally, Singular-style exponents are allowed, meaning that "X2" is interpreted as "X^2".

If the string cannot be parsed, the function returns the zero polynomial and a Parsing-error.

Example 
package main

import (
	"fmt"
	"log"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf9, _ := finitefield.Define(9)
	ring := univariate.DefRing(gf9)

	f, err := ring.PolynomialFromString("(a+2)X^4 + aX^2 + 2a+2")
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("f(X) = %v", f)
}

Output:

f(X) = (a + 2)X^4 + aX^2 + (2a + 2)

func (*QuotientRing) PolynomialFromUnsigned 

func (r *QuotientRing) PolynomialFromUnsigned(coefs []uint) *Polynomial

PolynomialFromUnsigned defines a new polynomial with the given coefficients. The coefficient of X^i is set to coefs[i].

func (*QuotientRing) Quotient 

func (r *QuotientRing) Quotient(id *Ideal) (*QuotientRing, error)

Quotient defines the quotient of the given ring modulo the input ideal.

The return type is a new ring-object

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf7, _ := finitefield.Define(7)
	ring := univariate.DefRing(gf7)

	f, _ := ring.PolynomialFromString("X^7-X")
	id, _ := ring.NewIdeal(f)

	ring, _ = ring.Quotient(id)
	fmt.Println(ring)
}

Output:

Quotient ring of univariate polynomials in X over Finite field of 7 elements modulo <X^7 + 6X>

func (*QuotientRing) SetVarName 

func (r *QuotientRing) SetVarName(varName string) error

SetVarName sets the variable name to be used in the given quotient ring.

Leading and trailing whitespace characters are removed before setting the variable name. If the string consists solely of whitespace characters, an InputValue-error is returned.

Example 
package main

import (
	"fmt"

	"github.com/ReneBoedker/algobra/finitefield"
	"github.com/ReneBoedker/algobra/univariate"
)

func main() {
	gf4, _ := finitefield.Define(4)
	ring := univariate.DefRing(gf4)

	f, _ := ring.PolynomialFromString("X^4 + (a+1)X^3 + a")

	// Change the variable names
	err := ring.SetVarName("Y")
	if err != nil {
		fmt.Printf("Could not set variable names: %q", err)
	}

	g, _ := ring.PolynomialFromString("aY^3 + (a+1)Y^2 + Y")

	// Both f and g are affected by the change
	fmt.Printf("f(Y) = %v\ng(Y) = %v", f, g)
}

Output:

f(Y) = Y^4 + (a + 1)Y^3 + a
g(Y) = aY^3 + (a + 1)Y^2 + Y

func (*QuotientRing) String 

func (r *QuotientRing) String() string

String returns the string representation of r.

func (*QuotientRing) VarName 

func (r *QuotientRing) VarName() string

VarName returns the string used to represent the variable of r.

func (*QuotientRing) Zero 

func (r *QuotientRing) Zero() *Polynomial

Zero returns a zero polynomial over the specified ring.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.