Documentation
¶
Overview ¶
Package polynomial provides polynomial methods and commitment schemes.
Index ¶
- func EvalEq(q, h []small_rational.SmallRational) small_rational.SmallRational
- type MultiLin
- func (m *MultiLin) Add(left, right MultiLin)
- func (m MultiLin) Clone() MultiLin
- func (m *MultiLin) Eq(q []small_rational.SmallRational)
- func (m MultiLin) Evaluate(coordinates []small_rational.SmallRational, p *Pool) small_rational.SmallRational
- func (m *MultiLin) Fold(r small_rational.SmallRational)
- func (m *MultiLin) FoldParallel(r small_rational.SmallRational) utils.Task
- func (m MultiLin) NumVars() int
- func (m MultiLin) Sum() small_rational.SmallRational
- type Polynomial
- func (p *Polynomial) Add(p1, p2 Polynomial) *Polynomial
- func (p *Polynomial) AddConstantInPlace(c *small_rational.SmallRational)
- func (p *Polynomial) Clone() Polynomial
- func (p *Polynomial) Degree() uint64
- func (p *Polynomial) Equal(p1 Polynomial) bool
- func (p *Polynomial) Eval(v *small_rational.SmallRational) small_rational.SmallRational
- func (p *Polynomial) Scale(c *small_rational.SmallRational, p0 Polynomial)
- func (p *Polynomial) ScaleInPlace(c *small_rational.SmallRational)
- func (p *Polynomial) Set(p1 Polynomial)
- func (p Polynomial) SetZero()
- func (p *Polynomial) Sub(p1, p2 Polynomial) *Polynomial
- func (p *Polynomial) SubConstantInPlace(c *small_rational.SmallRational)
- func (p Polynomial) Text(base int) string
- type Pool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func EvalEq ¶
func EvalEq(q, h []small_rational.SmallRational) small_rational.SmallRational
EvalEq computes Eq(q₁, ... , qₙ, h₁, ... , hₙ) = Π₁ⁿ Eq(qᵢ, hᵢ) where Eq(x,y) = xy + (1-x)(1-y) = 1 - x - y + xy + xy interpolates
_________________
| | |
| 0 | 1 |
|_______|_______|
y | | |
| 1 | 0 |
|_______|_______|
x
In other words the polynomial evaluated here is the multilinear extrapolation of one that evaluates to q' == h' for vectors q', h' of binary values
Types ¶
type MultiLin ¶
type MultiLin []small_rational.SmallRational
MultiLin tracks the values of a (dense i.e. not sparse) multilinear polynomial The variables are X₁ through Xₙ where n = log(len(.)) .[∑ᵢ 2ⁱ⁻¹ bₙ₋ᵢ] = the polynomial evaluated at (b₁, b₂, ..., bₙ) It is understood that any hypercube evaluation can be extrapolated to a multilinear polynomial
func (MultiLin) Clone ¶
Clone creates a deep copy of a bookkeeping table. Both multilinear interpolation and sumcheck require folding an underlying array, but folding changes the array. To do both one requires a deep copy of the bookkeeping table.
func (*MultiLin) Eq ¶
func (m *MultiLin) Eq(q []small_rational.SmallRational)
Eq sets m to the representation of the polynomial Eq(q₁, ..., qₙ, *, ..., *) × m[0]
func (MultiLin) Evaluate ¶
func (m MultiLin) Evaluate(coordinates []small_rational.SmallRational, p *Pool) small_rational.SmallRational
Evaluate extrapolate the value of the multilinear polynomial corresponding to m on the given coordinates
func (*MultiLin) Fold ¶
func (m *MultiLin) Fold(r small_rational.SmallRational)
Fold is partial evaluation function k[X₁, X₂, ..., Xₙ] → k[X₂, ..., Xₙ] by setting X₁=r
func (*MultiLin) FoldParallel ¶ added in v0.9.1
func (m *MultiLin) FoldParallel(r small_rational.SmallRational) utils.Task
func (MultiLin) Sum ¶
func (m MultiLin) Sum() small_rational.SmallRational
type Polynomial ¶
type Polynomial []small_rational.SmallRational
Polynomial represented by coefficients in the field.
func InterpolateOnRange ¶
func InterpolateOnRange(values []small_rational.SmallRational) Polynomial
InterpolateOnRange performs the interpolation of the given list of elements On the range [0, 1,..., len(values) - 1]
func (*Polynomial) Add ¶
func (p *Polynomial) Add(p1, p2 Polynomial) *Polynomial
Add adds p1 to p2 This function allocates a new slice unless p == p1 or p == p2
func (*Polynomial) AddConstantInPlace ¶
func (p *Polynomial) AddConstantInPlace(c *small_rational.SmallRational)
AddConstantInPlace adds a constant to the polynomial, modifying p
func (*Polynomial) Clone ¶
func (p *Polynomial) Clone() Polynomial
Clone returns a copy of the polynomial
func (*Polynomial) Degree ¶
func (p *Polynomial) Degree() uint64
Degree returns the degree of the polynomial, which is the length of Data.
func (*Polynomial) Equal ¶
func (p *Polynomial) Equal(p1 Polynomial) bool
Equal checks equality between two polynomials
func (*Polynomial) Eval ¶
func (p *Polynomial) Eval(v *small_rational.SmallRational) small_rational.SmallRational
Eval evaluates p at v returns a small_rational.SmallRational
func (*Polynomial) Scale ¶
func (p *Polynomial) Scale(c *small_rational.SmallRational, p0 Polynomial)
Scale multiplies p0 by v, storing the result in p
func (*Polynomial) ScaleInPlace ¶
func (p *Polynomial) ScaleInPlace(c *small_rational.SmallRational)
ScaleInPlace multiplies p by v, modifying p
func (Polynomial) SetZero ¶
func (p Polynomial) SetZero()
func (*Polynomial) Sub ¶
func (p *Polynomial) Sub(p1, p2 Polynomial) *Polynomial
Sub subtracts p2 from p1 TODO make interface more consistent with Add
func (*Polynomial) SubConstantInPlace ¶
func (p *Polynomial) SubConstantInPlace(c *small_rational.SmallRational)
SubConstantInPlace subs a constant to the polynomial, modifying p
func (Polynomial) Text ¶
func (p Polynomial) Text(base int) string
type Pool ¶
type Pool struct {
}
Do as little as possible to instantiate the interface
func (*Pool) Clone ¶
func (p *Pool) Clone(slice []small_rational.SmallRational) []small_rational.SmallRational
func (*Pool) Dump ¶
func (p *Pool) Dump(...[]small_rational.SmallRational)
func (*Pool) Make ¶
func (p *Pool) Make(n int) []small_rational.SmallRational
Source Files