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