utils

package
v0.0.0-...-031a8c5 Latest Latest
Warning

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

 Go to latest Published: Jul 19, 2021 License: GPL-3.0 Imports: 11 Imported by: 2

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var Field = PrepareFields(bn256.Order)

Todo I dont like this pubic accessible thing here

Functions

func Abs 

func Abs(n int) (val int, positive bool)

returns the absolute value of a signed int and a flag telling if the input was positive or not this implementation is awesome and fast (see Henry S Warren, Hackers's Delight)

func AbsInt 

func AbsInt(i int) int

func Addicity 

func Addicity(n int) int

func AdicityBig 

func AdicityBig(input *big.Int) (twoadicity int)

AdicityBig returns the biggest power of 2, that divides the input i.e. 2^n | in

func BigArraysEqual 

func BigArraysEqual(a, b []*big.Int) bool

func BigIsOdd 

func BigIsOdd(n *big.Int) bool

func Equal 

func Equal(a, b int) int

func ExtendArrayWithZeros 

func ExtendArrayWithZeros(in []*big.Int, desiredLength int) []*big.Int

func IsPowerTwo 

func IsPowerTwo(in uint64) bool

checks if a integer is a power of 2 From Henry Warrens Hackers Delight

func IsZeroArray 

func IsZeroArray(a []*big.Int) bool

func MaxInt 

func MaxInt(a, b int) int

func Mod 

func Mod(a, b int) int

the go a%b return negative representants too.. that sucks so much

func NextPowerOfTwo 

func NextPowerOfTwo(n int) int

func Parallelize 

func Parallelize(nbIterations int, work func(int, int), maxCpus ...int)

Parallelize process in parallel the work function

func PrintWithLineNumbering 

func PrintWithLineNumbering(s string)

Types

type AvlNode 

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

func (*AvlNode) AllNodes 

func (root *AvlNode) AllNodes(t *[]Entry)

Each recursively traverses tree `tree` and collects all nodes

func (*AvlNode) Get 

func (self *AvlNode) Get(key uint) (value *big.Int, err error)

func (*AvlNode) Has 

func (self *AvlNode) Has(key uint) (has bool)

func (*AvlNode) Height 

func (self *AvlNode) Height() int

func (*AvlNode) Key 

func (self *AvlNode) Key() uint

func (*AvlNode) Left 

func (self *AvlNode) Left() *AvlNode

func (*AvlNode) Put 

func (self *AvlNode) Put(key uint, value *big.Int, insert func(old, new *big.Int) *big.Int) (_ *AvlNode, updated bool)

func (*AvlNode) Remove 

func (self *AvlNode) Remove(key uint) (_ *AvlNode, value *big.Int, err error)

func (*AvlNode) Right 

func (self *AvlNode) Right() *AvlNode

func (*AvlNode) Size 

func (self *AvlNode) Size() int

func (AvlNode) String 

func (s AvlNode) String() string

func (*AvlNode) Value 

func (self *AvlNode) Value() *big.Int

type AvlTree 

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

func NewAvlTree 

func NewAvlTree() *AvlTree

func NewSparseArrayFromArray 

func NewSparseArrayFromArray(in []*big.Int) *AvlTree

func NewSparseArrayWith 

func NewSparseArrayWith(key uint, value *big.Int) (sp *AvlTree)

func TransposeSparse 

func TransposeSparse(matrix []*AvlTree, witness int) (tra []*AvlTree)

func (*AvlTree) ChannelNodes 

func (t *AvlTree) ChannelNodes(ascendingOrder bool) (collectedNodes chan Entry)

Each recursively traverses tree `tree` and collects all nodes array is filled up from highest to lowest degree

func (*AvlTree) Clone 

func (a *AvlTree) Clone() *AvlTree

Add adds two polinomials over the Finite Field

func (*AvlTree) DecendingNodes 

func (t *AvlTree) DecendingNodes() (collectedNodes []Entry)

Each recursively traverses tree `tree` and collects all nodes array is filled up from highest to lowest degree

func (*AvlTree) Get 

func (self *AvlTree) Get(key uint) (value *big.Int, err error)

func (*AvlTree) Has 

func (self *AvlTree) Has(key uint) bool

func (*AvlTree) Insert 

func (t *AvlTree) Insert(key uint, value *big.Int) (err error)

Add inserts an element to tree with root `t`

func (*AvlTree) InsertNoOverwriteAllowed 

func (t *AvlTree) InsertNoOverwriteAllowed(key uint, value *big.Int) (err error)

Add inserts an element to tree with root `t`

func (*AvlTree) MaxNode 

func (t *AvlTree) MaxNode() *AvlNode

MaxNode returns the node with the maximal Key in the tree

func (*AvlTree) MaxPower 

func (t *AvlTree) MaxPower() uint

MaxNode returns the node with the maximal Key in the tree

func (*AvlTree) MinNode 

func (t *AvlTree) MinNode() *AvlNode

MinNode returns the node with the minimal Key in the tree

func (*AvlTree) Put 

func (self *AvlTree) Put(key uint, value *big.Int, insert func(old, new *big.Int) *big.Int) (err error)

func (*AvlTree) Remove 

func (self *AvlTree) Remove(key uint) (value *big.Int, err error)

func (*AvlTree) Root 

func (self *AvlTree) Root() *AvlNode

func (*AvlTree) Size 

func (self *AvlTree) Size() int

func (*AvlTree) String 

func (t *AvlTree) String() string

func (*AvlTree) ToArray 

func (t *AvlTree) ToArray(length int) (collectedNodes []*big.Int)

type Entry 

type Entry struct {
	Key   uint
	Value *big.Int
}

type FFT_PrecomputedParas 

type FFT_PrecomputedParas struct {
	RootOfUnity                  *big.Int
	RootOfUnitys_SquareSteps     []*big.Int // w,w^2,w^4,w^8..
	RootOfUnity_inv              *big.Int
	RootOfUnity_invs_SquareSteps []*big.Int // w^-1,w^-2,w^-4,w^-8..
	RootOfUnitys                 []*big.Int // 1,w,w^2,w^3,w^4..,
	RootOfUnity_invs             []*big.Int // 1,w^-1,w^-2,w^-3,w^-4..
	Size                         int        //number of points we want to consider, rounded to the next power of two

	Domain Poly //p(x) = x^size - 1
	// contains filtered or unexported fields
}

type FastBool 

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

func NewFastBool 

func NewFastBool() FastBool

func (FastBool) IsSet 

func (fb FastBool) IsSet(pos int) bool

func (FastBool) Set 

func (fb FastBool) Set(pos int)

type Fields 

type Fields struct {
	ArithmeticField Fq
	PolynomialField PolynomialField
}

func PrepareFields 

func PrepareFields(r *big.Int) Fields

PrepareFields For prime r, in order to prove statements about F_r-arithmetic circuit satisfiability, one instantiates (G, P, V ) using an elliptic curve E defined over some finite field F_q , where the group E(F_q) of F_q-rational points has order r = #E(F q ) (or, more generally, r divides #E(F q )).

type Fq 

type Fq struct {
	Q *big.Int // Q

}

Fq is the Z field over modulus Q

func NewFiniteField 

func NewFiniteField(order *big.Int) Fq

NewFiniteField generates a new Fq

func (Fq) Add 

func (fq Fq) Add(a, b *big.Int) *big.Int

Add performs an addition on the Fq

func (Fq) AddPolynomials 

func (f Fq) AddPolynomials(polynomials []*AvlTree) (sumPoly *AvlTree)

func (Fq) AddToSparse 

func (fq Fq) AddToSparse(a, b *AvlTree) *AvlTree

func (Fq) Affine 

func (fq Fq) Affine(a *big.Int) *big.Int

func (Fq) Combine 

func (f Fq) Combine(a *AvlTree, w []*big.Int) (scaledPolynomial *AvlTree)

func (Fq) Copy 

func (fq Fq) Copy(a *big.Int) *big.Int

func (Fq) Div 

func (fq Fq) Div(a, b *big.Int) *big.Int

Div performs the division over the finite field

func (Fq) DivideSparse 

func (fq Fq) DivideSparse(a, b *AvlTree) (result, rem *AvlTree)

Div divides two polinomials over the Finite Field, returning the result and the remainder

func (Fq) Double 

func (fq Fq) Double(a *big.Int) *big.Int

Double performs a doubling on the Fq

func (Fq) Equal 

func (fq Fq) Equal(a, b *big.Int) bool

func (Fq) EvalPoly 

func (fq Fq) EvalPoly(v Poly, x *big.Int) *big.Int

EvalPoly Evaluates a polynomial v at position x, using the Horners Rule

func (Fq) EvalSparsePoly 

func (fq Fq) EvalSparsePoly(poly *AvlTree, at *big.Int) (result *big.Int)

EvalPoly Evaluates a sparse polynomial

func (Fq) Exp 

func (fq Fq) Exp(base *big.Int, e *big.Int) *big.Int

Exp performs the exponential over Fq unsafe when e is negative

func (Fq) ExpInt 

func (fq Fq) ExpInt(base *big.Int, e int64) *big.Int

Exp performs the exponential over Fq

func (Fq) Inverse 

func (fq Fq) Inverse(a *big.Int) *big.Int

Inverse returns the inverse on the Fq

func (Fq) IsZero 

func (fq Fq) IsZero(a *big.Int) bool

func (Fq) LinearCombine 

func (f Fq) LinearCombine(polynomials []*AvlTree, w []*big.Int) (scaledPolynomials []*AvlTree)

func (Fq) Mul 

func (fq Fq) Mul(a, b *big.Int) *big.Int

Mul performs a multiplication on the Fq

func (Fq) MulSparse 

func (fq Fq) MulSparse(a, b *AvlTree) *AvlTree

Mul multiplies two polinomials over the Finite Field

func (Fq) MulSparseScalar 

func (fq Fq) MulSparseScalar(a *AvlTree, scalar *big.Int) *AvlTree

Mul multiplies a sparse polynomail with a scalar over the Finite Field

func (Fq) Neg 

func (fq Fq) Neg(a *big.Int) *big.Int

Neg returns the additive inverse -a over Fq

func (Fq) One 

func (fq Fq) One() *big.Int

One returns a One value on the Fq

func (Fq) Rand 

func (fq Fq) Rand() (*big.Int, error)

func (Fq) ScalarProduct 

func (fq Fq) ScalarProduct(l, r []*big.Int) (sum *big.Int)

func (Fq) SparseScalarProduct 

func (f Fq) SparseScalarProduct(a *AvlTree, b []*big.Int) (res *big.Int)

func (Fq) Square 

func (fq Fq) Square(a *big.Int) *big.Int

Square performs a square operation on the Fq

func (Fq) StringToFieldElement 

func (fq Fq) StringToFieldElement(a string) (v *big.Int, s bool)

func (Fq) Sub 

func (fq Fq) Sub(a, b *big.Int) *big.Int

Sub performs a subtraction on the Fq

func (Fq) SubToSparse 

func (fq Fq) SubToSparse(a, b *AvlTree) *AvlTree

Sub subtracts two polinomials over the Finite Field

func (Fq) Zero 

func (fq Fq) Zero() *big.Int

Zero returns a Zero value on the Fq

type Poly 

type Poly []*big.Int

func ArrayOfBigZeros 

func ArrayOfBigZeros(num int) Poly

ArrayOfBigZeros creates a *big.Int array with n elements to zero

func Transpose 

func Transpose(matrix []Poly) []Poly

Transpose transposes the *big.Int matrix

func (Poly) Degree 

func (p Poly) Degree() int

func (Poly) IsSparse 

func (p Poly) IsSparse() bool

if less then 20% of the entries are unequal to 0, we consider the polynomial to be sparse

type PolynomialField 

type PolynomialField struct {
	F Fq
	// contains filtered or unexported fields
}

PolynomialField is the Polynomial over a Finite Field where the polynomial operations are performed

func NewPolynomialField 

func NewPolynomialField(f Fq) (pf *PolynomialField)

func (PolynomialField) Add 

func (pf PolynomialField) Add(a, b Poly) Poly

Add adds two polinomials over the Finite Field

func (PolynomialField) AddPolynomials 

func (pf PolynomialField) AddPolynomials(polynomials []Poly) (sumPoly Poly)

func (*PolynomialField) DFFT 

func (pf *PolynomialField) DFFT(polynomial Poly, shift *big.Int) (evaluatedAtRoots []*big.Int)

func (PolynomialField) Div 

func (pf PolynomialField) Div(a, b Poly) (Poly, Poly)

Div divides two polinomials over the Finite Field, returning the result and the remainder

func (PolynomialField) DivFFT 

func (pf PolynomialField) DivFFT(a, b Poly) (Poly, Poly)

TODO

func (PolynomialField) DomainPolynomial 

func (pf PolynomialField) DomainPolynomial(len int) Poly

returns (x)(x-1)..(x-(len-1))

func (PolynomialField) EvalPoly 

func (pf PolynomialField) EvalPoly(v Poly, x *big.Int) *big.Int

EvalPoly Evaluates a polynomial v at position x, using the Horners Rule

func (PolynomialField) InterpolateSparseArray 

func (pf PolynomialField) InterpolateSparseArray(dataArray *AvlTree, degree int) (polynom *AvlTree)

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (*PolynomialField) InvDFFT 

func (pf *PolynomialField) InvDFFT(ValuesAtRoots []*big.Int, shift *big.Int) (coefficients Poly)

input an array of datapoints, returns the coefficients of a polynomial that interpolates the data at the roots of unity

func (PolynomialField) LagrangeInterpolation 

func (pf PolynomialField) LagrangeInterpolation(datapoints Poly) (polynom Poly)

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (*PolynomialField) LagrangeInterpolation_RootOfUnity 

func (pf *PolynomialField) LagrangeInterpolation_RootOfUnity(datapoints Poly) (polynom Poly)

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (PolynomialField) LinearCombine 

func (pf PolynomialField) LinearCombine(polynomials []Poly, w Poly) (scaledPolynomials []Poly)

func (*PolynomialField) MulFFT 

func (pf *PolynomialField) MulFFT(a, b Poly) Poly

MulFFT multiplies two polynomials over the Finite Field

func (*PolynomialField) MulNaive 

func (pf *PolynomialField) MulNaive(a, b Poly) Poly

MulNaive multiplies two polinomials over the Finite Field

func (PolynomialField) MulScalar 

func (pf PolynomialField) MulScalar(polynomial Poly, w *big.Int) (scaledPolynomial Poly)

func (PolynomialField) NewPolZeroAt 

func (pf PolynomialField) NewPolZeroAt(pointPos, totalPoints int, height *big.Int) Poly

NewPolZeroAt generates a new polynomial that has value zero at the given value

func (PolynomialField) PointwiseAdd 

func (pf PolynomialField) PointwiseAdd(a Poly, b Poly) (ab Poly)

func (PolynomialField) PointwiseMultiplication 

func (pf PolynomialField) PointwiseMultiplication(a Poly, b Poly) (ab Poly)

func (PolynomialField) PointwiseSub 

func (pf PolynomialField) PointwiseSub(a Poly, b Poly) (ab Poly)

func (*PolynomialField) PrecomputeLagrange 

func (pf *PolynomialField) PrecomputeLagrange(totalPoints int)

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (*PolynomialField) PrecomputeLagrangeFFT 

func (pf *PolynomialField) PrecomputeLagrangeFFT(points int)

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (*PolynomialField) PrecomputeLagrangeFFT_2 

func (pf *PolynomialField) PrecomputeLagrangeFFT_2(points int)

func (*PolynomialField) PrecomputeLagrangeFFT_3 

func (pf *PolynomialField) PrecomputeLagrangeFFT_3(points int)

Author Mathias Wolf 2020

func (*PolynomialField) PrepareFFT 

func (pf *PolynomialField) PrepareFFT(length int) *FFT_PrecomputedParas

func (PolynomialField) Sub 

func (pf PolynomialField) Sub(a, b Poly) Poly

Sub subtracts two polinomials over the Finite Field

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.