1package goldilocks
  2
  3import "github.com/consensys/gnark-crypto/field/goldilocks"
  4
  5const D = 2
  6
  7type QuadraticExtensionAlgebraVariable = [D]QuadraticExtensionVariable
  8
  9func NewQuadraticExtensionAlgebraVariable(
 10	a QuadraticExtensionVariable,
 11	b QuadraticExtensionVariable,
 12) QuadraticExtensionAlgebraVariable {
 13	return QuadraticExtensionAlgebraVariable{a, b}
 14}
 15
 16func (p QuadraticExtensionVariable) ToQuadraticExtensionAlgebra() QuadraticExtensionAlgebraVariable {
 17	return [D]QuadraticExtensionVariable{p, ZeroExtension()}
 18}
 19
 20func ZeroExtensionAlgebra() QuadraticExtensionAlgebraVariable {
 21	return ZeroExtension().ToQuadraticExtensionAlgebra()
 22}
 23
 24func OneExtensionAlgebra() QuadraticExtensionAlgebraVariable {
 25	return OneExtension().ToQuadraticExtensionAlgebra()
 26}
 27
 28func (p *Chip) AddExtensionAlgebra(
 29	a QuadraticExtensionAlgebraVariable,
 30	b QuadraticExtensionAlgebraVariable,
 31) QuadraticExtensionAlgebraVariable {
 32	var sum QuadraticExtensionAlgebraVariable
 33	for i := 0; i < D; i++ {
 34		sum[i] = p.AddExtension(a[i], b[i])
 35	}
 36	return sum
 37}
 38
 39func (p *Chip) SubExtensionAlgebra(
 40	a QuadraticExtensionAlgebraVariable,
 41	b QuadraticExtensionAlgebraVariable,
 42) QuadraticExtensionAlgebraVariable {
 43	var diff QuadraticExtensionAlgebraVariable
 44	for i := 0; i < D; i++ {
 45		diff[i] = p.SubExtension(a[i], b[i])
 46	}
 47	return diff
 48}
 49
 50func (p Chip) MulExtensionAlgebra(
 51	a QuadraticExtensionAlgebraVariable,
 52	b QuadraticExtensionAlgebraVariable,
 53) QuadraticExtensionAlgebraVariable {
 54	var inner [D][]QuadraticExtensionAlgebraVariable
 55	var innerW [D][]QuadraticExtensionAlgebraVariable
 56
 57	for i := 0; i < D; i++ {
 58		for j := 0; j < D-i; j++ {
 59			idx := (i + j) % D
 60			inner[idx] = append(inner[idx], QuadraticExtensionAlgebraVariable{a[i], b[j]})
 61		}
 62		for j := D - i; j < D; j++ {
 63			idx := (i + j) % D
 64			innerW[idx] = append(innerW[idx], QuadraticExtensionAlgebraVariable{a[i], b[j]})
 65		}
 66	}
 67
 68	var product QuadraticExtensionAlgebraVariable
 69	for i := 0; i < D; i++ {
 70		acc := p.InnerProductExtension(NewVariable(W), ZeroExtension(), innerW[i])
 71		product[i] = p.InnerProductExtension(One(), acc, inner[i])
 72	}
 73
 74	return product
 75}
 76
 77func (p *Chip) ScalarMulExtensionAlgebra(
 78	a QuadraticExtensionVariable,
 79	b QuadraticExtensionAlgebraVariable,
 80) QuadraticExtensionAlgebraVariable {
 81	var product QuadraticExtensionAlgebraVariable
 82	for i := 0; i < D; i++ {
 83		product[i] = p.MulExtension(a, b[i])
 84	}
 85	return product
 86}
 87
 88func (p *Chip) PartialInterpolateExtAlgebra(
 89	domain []goldilocks.Element,
 90	values []QuadraticExtensionAlgebraVariable,
 91	barycentricWeights []goldilocks.Element,
 92	point QuadraticExtensionAlgebraVariable,
 93	initialEval QuadraticExtensionAlgebraVariable,
 94	initialPartialProd QuadraticExtensionAlgebraVariable,
 95) (QuadraticExtensionAlgebraVariable, QuadraticExtensionAlgebraVariable) {
 96	n := len(values)
 97	if n == 0 {
 98		panic("Cannot interpolate with no values")
 99	}
100	if n != len(domain) {
101		panic("Domain and values must have the same length")
102	}
103	if n != len(barycentricWeights) {
104		panic("Domain and barycentric weights must have the same length")
105	}
106
107	newEval := initialEval
108	newPartialProd := initialPartialProd
109	for i := 0; i < n; i++ {
110		val := values[i]
111		x := domain[i]
112		xField := NewVariable(x)
113		xQE := xField.ToQuadraticExtension()
114		xQEAlgebra := xQE.ToQuadraticExtensionAlgebra()
115		weight := NewVariable(barycentricWeights[i].Uint64()).ToQuadraticExtension()
116		term := p.SubExtensionAlgebra(point, xQEAlgebra)
117		weightedVal := p.ScalarMulExtensionAlgebra(weight, val)
118		newEval = p.MulExtensionAlgebra(newEval, term)
119		tmp := p.MulExtensionAlgebra(weightedVal, newPartialProd)
120		newEval = p.AddExtensionAlgebra(newEval, tmp)
121		newPartialProd = p.MulExtensionAlgebra(newPartialProd, term)
122	}
123
124	return newEval, newPartialProd
125}