1package field
  2
  3import (
  4	"fmt"
  5	"math/bits"
  6
  7	"github.com/consensys/gnark/frontend"
  8)
  9
 10type QuadraticExtensionAPI struct {
 11	fieldAPI frontend.API
 12
 13	W        F
 14	DTH_ROOT F
 15
 16	ONE_QE  QuadraticExtension
 17	ZERO_QE QuadraticExtension
 18}
 19
 20func NewQuadraticExtensionAPI(fieldAPI frontend.API, degreeBits uint64) *QuadraticExtensionAPI {
 21	// TODO:  Should degreeBits be verified that it fits within the field and that degree is within uint64?
 22
 23	return &QuadraticExtensionAPI{
 24		fieldAPI: fieldAPI,
 25
 26		W:        NewFieldElement(7),
 27		DTH_ROOT: NewFieldElement(18446744069414584320),
 28
 29		ONE_QE:  QuadraticExtension{ONE_F, ZERO_F},
 30		ZERO_QE: QuadraticExtension{ZERO_F, ZERO_F},
 31	}
 32}
 33
 34func (c *QuadraticExtensionAPI) SquareExtension(a QuadraticExtension) QuadraticExtension {
 35	return c.MulExtension(a, a)
 36}
 37
 38func (c *QuadraticExtensionAPI) MulExtension(a QuadraticExtension, b QuadraticExtension) QuadraticExtension {
 39	c_0 := c.fieldAPI.Add(c.fieldAPI.Mul(a[0], b[0]).(F), c.fieldAPI.Mul(c.W, a[1], b[1])).(F)
 40	c_1 := c.fieldAPI.Add(c.fieldAPI.Mul(a[0], b[1]).(F), c.fieldAPI.Mul(a[1], b[0])).(F)
 41	return QuadraticExtension{c_0, c_1}
 42}
 43
 44func (c *QuadraticExtensionAPI) AddExtension(a QuadraticExtension, b QuadraticExtension) QuadraticExtension {
 45	c_0 := c.fieldAPI.Add(a[0], b[0]).(F)
 46	c_1 := c.fieldAPI.Add(a[1], b[1]).(F)
 47	return QuadraticExtension{c_0, c_1}
 48}
 49
 50func (c *QuadraticExtensionAPI) SubExtension(a QuadraticExtension, b QuadraticExtension) QuadraticExtension {
 51	c_0 := c.fieldAPI.Sub(a[0], b[0]).(F)
 52	c_1 := c.fieldAPI.Sub(a[1], b[1]).(F)
 53	return QuadraticExtension{c_0, c_1}
 54}
 55
 56func (c *QuadraticExtensionAPI) DivExtension(a QuadraticExtension, b QuadraticExtension) QuadraticExtension {
 57	return c.MulExtension(a, c.InverseExtension(b))
 58}
 59
 60func (c *QuadraticExtensionAPI) IsZero(a QuadraticExtension) frontend.Variable {
 61	return c.fieldAPI.Mul(c.fieldAPI.IsZero(a[0]), c.fieldAPI.IsZero(a[1]))
 62}
 63
 64// TODO: Instead of calculating the inverse within the circuit, can witness the
 65// inverse and assert that a_inverse * a = 1.  Should reduce # of constraints.
 66func (c *QuadraticExtensionAPI) InverseExtension(a QuadraticExtension) QuadraticExtension {
 67	// First assert that a doesn't have 0 value coefficients
 68	a0_is_zero := c.fieldAPI.IsZero(a[0])
 69	a1_is_zero := c.fieldAPI.IsZero(a[1])
 70
 71	// assert that a0_is_zero OR a1_is_zero == false
 72	c.fieldAPI.AssertIsEqual(c.fieldAPI.Mul(a0_is_zero, a1_is_zero).(F), ZERO_F)
 73
 74	a_pow_r_minus_1 := QuadraticExtension{a[0], c.fieldAPI.Mul(a[1], c.DTH_ROOT).(F)}
 75	a_pow_r := c.MulExtension(a_pow_r_minus_1, a)
 76	return c.ScalarMulExtension(a_pow_r_minus_1, c.fieldAPI.Inverse(a_pow_r[0]).(F))
 77}
 78
 79func (c *QuadraticExtensionAPI) ScalarMulExtension(a QuadraticExtension, scalar F) QuadraticExtension {
 80	return QuadraticExtension{c.fieldAPI.Mul(a[0], scalar).(F), c.fieldAPI.Mul(a[1], scalar).(F)}
 81}
 82
 83func (c *QuadraticExtensionAPI) FieldToQE(a F) QuadraticExtension {
 84	return QuadraticExtension{a, ZERO_F}
 85}
 86
 87// / Exponentiate `base` to the power of a known `exponent`.
 88func (c *QuadraticExtensionAPI) ExpU64Extension(a QuadraticExtension, exponent uint64) QuadraticExtension {
 89	switch exponent {
 90	case 0:
 91		return c.ONE_QE
 92	case 1:
 93		return a
 94	case 2:
 95		return c.SquareExtension(a)
 96	default:
 97	}
 98
 99	current := a
100	product := c.ONE_QE
101
102	for i := 0; i < bits.Len64(exponent); i++ {
103		if i != 0 {
104			current = c.SquareExtension(current)
105		}
106
107		if (exponent >> i & 1) != 0 {
108			product = c.MulExtension(product, current)
109		}
110	}
111
112	return product
113}
114
115func (c *QuadraticExtensionAPI) ReduceWithPowers(terms []QuadraticExtension, scalar QuadraticExtension) QuadraticExtension {
116	sum := c.ZERO_QE
117
118	for i := len(terms) - 1; i >= 0; i-- {
119		sum = c.AddExtension(
120			c.MulExtension(
121				sum,
122				scalar,
123			),
124			terms[i],
125		)
126	}
127
128	return sum
129}
130
131func (c *QuadraticExtensionAPI) Select(b frontend.Variable, qe0, qe1 QuadraticExtension) QuadraticExtension {
132	var retQE QuadraticExtension
133
134	for i := 0; i < 2; i++ {
135		retQE[i] = c.fieldAPI.Select(b, qe0[i], qe1[i]).(F)
136	}
137
138	return retQE
139}
140
141func (c *QuadraticExtensionAPI) Lookup2(b0 frontend.Variable, b1 frontend.Variable, qe0, qe1, qe2, qe3 QuadraticExtension) QuadraticExtension {
142	var retQE QuadraticExtension
143
144	for i := 0; i < 2; i++ {
145		retQE[i] = c.fieldAPI.Lookup2(b0, b1, qe0[i], qe1[i], qe2[i], qe3[i]).(F)
146	}
147
148	return retQE
149}
150
151func (c *QuadraticExtensionAPI) AssertIsEqual(a, b QuadraticExtension) {
152	for i := 0; i < 2; i++ {
153		c.fieldAPI.AssertIsEqual(a[i], b[i])
154	}
155}
156
157func (c *QuadraticExtensionAPI) Println(a QuadraticExtension) {
158	fmt.Print("Degree 0 coefficient")
159	c.fieldAPI.Println(a[0])
160
161	fmt.Print("Degree 1 coefficient")
162	c.fieldAPI.Println(a[1])
163}