1package prover
  2
  3import (
  4	"bytes"
  5	"math/big"
  6
  7	"github.com/iden3/go-circom-prover-verifier/types"
  8	"github.com/iden3/go-iden3-crypto/ff"
  9)
 10
 11func arrayOfZeroes(n int) []*big.Int {
 12	var r []*big.Int
 13	for i := 0; i < n; i++ {
 14		r = append(r, new(big.Int).SetInt64(0))
 15	}
 16	return r
 17}
 18func arrayOfZeroesE(n int) []*ff.Element {
 19	var r []*ff.Element
 20	for i := 0; i < n; i++ {
 21		r = append(r, ff.NewElement())
 22	}
 23	return r
 24}
 25
 26func fAdd(a, b *big.Int) *big.Int {
 27	ab := new(big.Int).Add(a, b)
 28	return new(big.Int).Mod(ab, types.R)
 29}
 30
 31func fSub(a, b *big.Int) *big.Int {
 32	ab := new(big.Int).Sub(a, b)
 33	return new(big.Int).Mod(ab, types.R)
 34}
 35
 36func fMul(a, b *big.Int) *big.Int {
 37	ab := new(big.Int).Mul(a, b)
 38	return new(big.Int).Mod(ab, types.R)
 39}
 40
 41func fDiv(a, b *big.Int) *big.Int {
 42	ab := new(big.Int).Mul(a, new(big.Int).ModInverse(b, types.R))
 43	return new(big.Int).Mod(ab, types.R)
 44}
 45
 46func fNeg(a *big.Int) *big.Int {
 47	return new(big.Int).Mod(new(big.Int).Neg(a), types.R)
 48}
 49
 50func fInv(a *big.Int) *big.Int {
 51	return new(big.Int).ModInverse(a, types.R)
 52}
 53
 54func fExp(base *big.Int, e *big.Int) *big.Int {
 55	res := big.NewInt(1)
 56	rem := new(big.Int).Set(e)
 57	exp := base
 58
 59	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
 60		// if BigIsOdd(rem) {
 61		if rem.Bit(0) == 1 { // .Bit(0) returns 1 when is odd
 62			res = fMul(res, exp)
 63		}
 64		exp = fMul(exp, exp)
 65		rem = new(big.Int).Rsh(rem, 1)
 66	}
 67	return res
 68}
 69
 70func max(a, b int) int {
 71	if a > b {
 72		return a
 73	}
 74	return b
 75}
 76
 77func polynomialSub(a, b []*big.Int) []*big.Int {
 78	r := arrayOfZeroes(max(len(a), len(b)))
 79	for i := 0; i < len(a); i++ {
 80		r[i] = fAdd(r[i], a[i])
 81	}
 82	for i := 0; i < len(b); i++ {
 83		r[i] = fSub(r[i], b[i])
 84	}
 85	return r
 86}
 87
 88func polynomialSubE(a, b []*ff.Element) []*ff.Element {
 89	r := arrayOfZeroesE(max(len(a), len(b)))
 90	for i := 0; i < len(a); i++ {
 91		r[i].Add(r[i], a[i])
 92	}
 93	for i := 0; i < len(b); i++ {
 94		r[i].Sub(r[i], b[i])
 95	}
 96	return r
 97}
 98
 99func polynomialMul(a, b []*big.Int) []*big.Int {
100	r := arrayOfZeroes(len(a) + len(b) - 1)
101	for i := 0; i < len(a); i++ {
102		for j := 0; j < len(b); j++ {
103			r[i+j] = fAdd(r[i+j], fMul(a[i], b[j]))
104		}
105	}
106	return r
107}
108
109func polynomialMulE(a, b []*ff.Element) []*ff.Element {
110	r := arrayOfZeroesE(len(a) + len(b) - 1)
111	for i := 0; i < len(a); i++ {
112		for j := 0; j < len(b); j++ {
113			r[i+j].Add(r[i+j], ff.NewElement().Mul(a[i], b[j]))
114		}
115	}
116	return r
117}
118
119func polynomialDiv(a, b []*big.Int) ([]*big.Int, []*big.Int) {
120	// https://en.wikipedia.org/wiki/Division_algorithm
121	r := arrayOfZeroes(len(a) - len(b) + 1)
122	rem := a
123	for len(rem) >= len(b) {
124		l := fDiv(rem[len(rem)-1], b[len(b)-1])
125		pos := len(rem) - len(b)
126		r[pos] = l
127		aux := arrayOfZeroes(pos)
128		aux1 := append(aux, l)
129		aux2 := polynomialSub(rem, polynomialMul(b, aux1))
130		rem = aux2[:len(aux2)-1]
131	}
132	return r, rem
133}
134
135func polynomialDivE(a, b []*ff.Element) ([]*ff.Element, []*ff.Element) {
136	// https://en.wikipedia.org/wiki/Division_algorithm
137	r := arrayOfZeroesE(len(a) - len(b) + 1)
138	rem := a
139	for len(rem) >= len(b) {
140		l := ff.NewElement().Div(rem[len(rem)-1], b[len(b)-1])
141		pos := len(rem) - len(b)
142		r[pos] = l
143		aux := arrayOfZeroesE(pos)
144		aux1 := append(aux, l)
145		aux2 := polynomialSubE(rem, polynomialMulE(b, aux1))
146		rem = aux2[:len(aux2)-1]
147	}
148	return r, rem
149}