1// code originally taken from https://github.com/arnaucube/go-snark (https://github.com/arnaucube/go-snark/blob/master/fields/fq.go), pasted here to ensure compatibility among future changes
  2
  3package field
  4
  5import (
  6	"bytes"
  7	"crypto/rand"
  8	"math/big"
  9)
 10
 11// Fq is the Z field over modulus Q
 12type Fq struct {
 13	Q *big.Int // Q
 14}
 15
 16// NewFq generates a new Fq
 17func NewFq(q *big.Int) Fq {
 18	return Fq{
 19		q,
 20	}
 21}
 22
 23// Zero returns a Zero value on the Fq
 24func (fq Fq) Zero() *big.Int {
 25	return big.NewInt(int64(0))
 26}
 27
 28// One returns a One value on the Fq
 29func (fq Fq) One() *big.Int {
 30	return big.NewInt(int64(1))
 31}
 32
 33// Add performs an addition on the Fq
 34func (fq Fq) Add(a, b *big.Int) *big.Int {
 35	r := new(big.Int).Add(a, b)
 36	return new(big.Int).Mod(r, fq.Q)
 37}
 38
 39// Double performs a doubling on the Fq
 40func (fq Fq) Double(a *big.Int) *big.Int {
 41	r := new(big.Int).Add(a, a)
 42	return new(big.Int).Mod(r, fq.Q)
 43}
 44
 45// Sub performs a subtraction on the Fq
 46func (fq Fq) Sub(a, b *big.Int) *big.Int {
 47	r := new(big.Int).Sub(a, b)
 48	return new(big.Int).Mod(r, fq.Q)
 49}
 50
 51// Neg performs a negation on the Fq
 52func (fq Fq) Neg(a *big.Int) *big.Int {
 53	m := new(big.Int).Neg(a)
 54	return new(big.Int).Mod(m, fq.Q)
 55}
 56
 57// Mul performs a multiplication on the Fq
 58func (fq Fq) Mul(a, b *big.Int) *big.Int {
 59	m := new(big.Int).Mul(a, b)
 60	return new(big.Int).Mod(m, fq.Q)
 61}
 62
 63func (fq Fq) MulScalar(base, e *big.Int) *big.Int {
 64	return fq.Mul(base, e)
 65}
 66
 67// Inverse returns the inverse on the Fq
 68func (fq Fq) Inverse(a *big.Int) *big.Int {
 69	return new(big.Int).ModInverse(a, fq.Q)
 70}
 71
 72// Div performs the division over the finite field
 73func (fq Fq) Div(a, b *big.Int) *big.Int {
 74	d := fq.Mul(a, fq.Inverse(b))
 75	return new(big.Int).Mod(d, fq.Q)
 76}
 77
 78// Square performs a square operation on the Fq
 79func (fq Fq) Square(a *big.Int) *big.Int {
 80	m := new(big.Int).Mul(a, a)
 81	return new(big.Int).Mod(m, fq.Q)
 82}
 83
 84// Exp performs the exponential over Fq
 85func (fq Fq) Exp(base *big.Int, e *big.Int) *big.Int {
 86	res := fq.One()
 87	rem := fq.Copy(e)
 88	exp := base
 89
 90	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
 91		if BigIsOdd(rem) {
 92			res = fq.Mul(res, exp)
 93		}
 94		exp = fq.Square(exp)
 95		rem = new(big.Int).Rsh(rem, 1)
 96	}
 97	return res
 98}
 99
100func (fq Fq) Rand() (*big.Int, error) {
101
102	maxbits := fq.Q.BitLen()
103	b := make([]byte, (maxbits/8)-1)
104	_, err := rand.Read(b)
105	if err != nil {
106		return nil, err
107	}
108	r := new(big.Int).SetBytes(b)
109	rq := new(big.Int).Mod(r, fq.Q)
110
111	// r over q, nil
112	return rq, nil
113}
114
115func (fq Fq) IsZero(a *big.Int) bool {
116	return bytes.Equal(a.Bytes(), fq.Zero().Bytes())
117}
118
119func (fq Fq) Copy(a *big.Int) *big.Int {
120	return new(big.Int).SetBytes(a.Bytes())
121}
122
123func (fq Fq) Affine(a *big.Int) *big.Int {
124	nq := fq.Neg(fq.Q)
125
126	aux := a
127	if aux.Cmp(big.NewInt(int64(0))) == -1 { // negative value
128		if aux.Cmp(nq) != 1 { // aux less or equal nq
129			aux = new(big.Int).Mod(aux, fq.Q)
130		}
131		if aux.Cmp(big.NewInt(int64(0))) == -1 { // negative value
132			aux = new(big.Int).Add(aux, fq.Q)
133		}
134	} else {
135		if aux.Cmp(fq.Q) != -1 { // aux greater or equal nq
136			aux = new(big.Int).Mod(aux, fq.Q)
137		}
138	}
139	return aux
140}
141
142func (fq Fq) Equal(a, b *big.Int) bool {
143	aAff := fq.Affine(a)
144	bAff := fq.Affine(b)
145	return bytes.Equal(aAff.Bytes(), bAff.Bytes())
146}
147
148func BigIsOdd(n *big.Int) bool {
149	one := big.NewInt(int64(1))
150	and := new(big.Int).And(n, one)
151	return bytes.Equal(and.Bytes(), big.NewInt(int64(1)).Bytes())
152}