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 ¶
- type Ideal
- type Polynomial
- func (f *Polynomial) Add(g *Polynomial) *Polynomial
- func (f *Polynomial) BaseField() ff.Field
- func (f *Polynomial) Coef(deg int) ff.Element
- func (f *Polynomial) Coefs() []ff.Element
- func (f *Polynomial) Copy() *Polynomial
- func (f *Polynomial) DecrementCoef(deg int, val ff.Element)
- func (f *Polynomial) Degrees() []int
- func (f *Polynomial) EmbedIn(r *QuotientRing, reduce bool) error
- func (f *Polynomial) Equal(g *Polynomial) bool
- func (f *Polynomial) Err() error
- func (f *Polynomial) Eval(point ff.Element) ff.Element
- func (f *Polynomial) IncrementCoef(deg int, val ff.Element)
- func (f *Polynomial) IsMonomial() bool
- func (f *Polynomial) IsNonzero() bool
- func (f *Polynomial) IsOne() bool
- func (f *Polynomial) IsZero() bool
- func (f *Polynomial) Lc() ff.Element
- func (f *Polynomial) Ld() int
- func (f *Polynomial) Lt() *Polynomial
- func (f *Polynomial) Minus(g *Polynomial) *Polynomial
- func (f *Polynomial) Mult(g *Polynomial) *Polynomial
- func (f *Polynomial) NTerms() (c uint)
- func (f *Polynomial) Neg() *Polynomial
- func (f *Polynomial) Normalize() *Polynomial
- func (f *Polynomial) Plus(g *Polynomial) *Polynomial
- func (f *Polynomial) Pow(n uint) *Polynomial
- func (f *Polynomial) QuoRem(list ...*Polynomial) (q []*Polynomial, r *Polynomial, err error)
- func (f *Polynomial) Scale(c ff.Element) *Polynomial
- func (f *Polynomial) SetCoef(deg int, val ff.Element) *Polynomial
- func (f *Polynomial) SetCoefPtr(deg int, val ff.Element) *Polynomial
- func (f *Polynomial) SetNeg() *Polynomial
- func (f *Polynomial) SetScale(c ff.Element) *Polynomial
- func (f *Polynomial) SetZero()
- func (f *Polynomial) String() string
- func (f *Polynomial) Sub(g *Polynomial) *Polynomial
- func (f *Polynomial) Times(g *Polynomial) *Polynomial
- type QuotientRing
- func (r *QuotientRing) Interpolate(points []ff.Element, values []ff.Element) (*Polynomial, error)
- func (r *QuotientRing) NewIdeal(generators ...*Polynomial) (*Ideal, error)
- func (r *QuotientRing) One() *Polynomial
- func (r *QuotientRing) Polynomial(coefs []ff.Element) *Polynomial
- func (r *QuotientRing) PolynomialFromSigned(coefs []int) *Polynomial
- func (r *QuotientRing) PolynomialFromString(s string) (*Polynomial, error)
- func (r *QuotientRing) PolynomialFromUnsigned(coefs []uint) *Polynomial
- func (r *QuotientRing) Quotient(id *Ideal) (*QuotientRing, error)
- func (r *QuotientRing) SetVarName(varName string) error
- func (r *QuotientRing) String() string
- func (r *QuotientRing) VarName() string
- func (r *QuotientRing) Zero() *Polynomial
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) Generator ¶
func (id *Ideal) Generator() *Polynomial
Generator returns a copy of the generator of id.
func (*Ideal) ShortString ¶
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>
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) 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) 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.