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