field_test.go

package eip

import (
	"bytes"
	"crypto/rand"
	"fmt"
	"io"
	"math/big"
	"testing"
)

type fieldElement interface{}

type field interface {
	new() fieldElement
	debugElement(fe fieldElement)
	limbSize() int
	byteSize() int
	fromBytes(in []byte) (fieldElement, error)
	toBytes(a fieldElement) []byte
	isZero(a fieldElement) bool
	isOne(a fieldElement) bool
	zero() fieldElement
	p() *big.Int
	one() fieldElement
	equal(a, b fieldElement) bool
	rand(r io.Reader) fieldElement
	add(c, a, b fieldElement)
	sub(c, a, b fieldElement)
	double(c, a fieldElement)
	neg(c, a fieldElement)
	mul(c, a, b fieldElement)
	square(c, a fieldElement)
	exp(c, a fieldElement, e *big.Int)
	inverse(c, a fieldElement) bool
	sqrt(c, a fieldElement) bool
}

type fqTest struct {
	*fq
}

func (t fqTest) new() fieldElement {
	return t.fq.new()
}

func (t fqTest) debugElement(in fieldElement) {
	t.fq.debugElement(in.(fe))
}

func (f *fq) debugElement(in fe) {
	fmt.Println(f.toString(in))
}

func (t fqTest) byteSize() int {
	return t.fq.byteSize()
}

func (t fqTest) limbSize() int {
	return t.fq.limbSize
}

func (t fqTest) fromBytes(in []byte) (fieldElement, error) {
	return t.fq.fromBytes(in)
}

func (t fqTest) toBytes(in fieldElement) []byte {
	return t.fq.toBytes(in.(fe))
}

func (t fqTest) isZero(in fieldElement) bool {
	return t.fq.isZero(in.(fe))
}

func (t fqTest) isOne(in fieldElement) bool {
	return t.fq.isOne(in.(fe))
}

func (t fqTest) zero() fieldElement {
	return t.fq.zero
}

func (t fqTest) one() fieldElement {
	return t.fq.one
}

func (t fqTest) p() *big.Int {
	return t.fq.modulus()
}

func (t fqTest) equal(a, b fieldElement) bool {
	return t.fq.equal(a.(fe), b.(fe))
}

func (t fqTest) rand(r io.Reader) fieldElement {
	return t.fq.rand(r)
}

func (t fqTest) add(c, a, b fieldElement) {
	t.fq.add(c.(fe), a.(fe), b.(fe))
}

func (t fqTest) sub(c, a, b fieldElement) {
	t.fq.sub(c.(fe), a.(fe), b.(fe))
}

func (t fqTest) mul(c, a, b fieldElement) {
	t.fq.mul(c.(fe), a.(fe), b.(fe))
}

func (t fqTest) double(c, a fieldElement) {
	t.fq.double(c.(fe), a.(fe))
}

func (t fqTest) neg(c, a fieldElement) {
	t.fq.neg(c.(fe), a.(fe))
}

func (t fqTest) square(c, a fieldElement) {
	t.fq.square(c.(fe), a.(fe))
}

func (t fqTest) exp(c, a fieldElement, e *big.Int) {
	t.fq.exp(c.(fe), a.(fe), e)
}

func (t fqTest) inverse(c, a fieldElement) bool {
	return t.fq.inverse(c.(fe), a.(fe))
}

func (t fqTest) sqrt(c, a fieldElement) bool {
	return t.fq.sqrt(c.(fe), a.(fe))
}

type fq2Test struct {
	*fq2
}

func (t fq2Test) new() fieldElement {
	return t.fq2.new()
}

func (t fq2Test) debugElement(in fieldElement) {
	t.fq2.debugElement(in.(*fe2))
}

func (f *fq2) debugElement(in *fe2) {
	fmt.Println(f.toString(in))
}

func (t fq2Test) byteSize() int {
	return t.fq2.byteSize()
}

func (t fq2Test) limbSize() int {
	return t.fq2.f.limbSize
}

func (t fq2Test) fromBytes(in []byte) (fieldElement, error) {
	return t.fq2.fromBytes(in)
}

func (t fq2Test) toBytes(in fieldElement) []byte {
	return t.fq2.toBytes(in.(*fe2))
}

func (t fq2Test) isZero(in fieldElement) bool {
	return t.fq2.isZero(in.(*fe2))
}

func (t fq2Test) isOne(in fieldElement) bool {
	return t.fq2.isOne(in.(*fe2))
}

func (t fq2Test) zero() fieldElement {
	return t.fq2.zero()
}

func (t fq2Test) one() fieldElement {
	return t.fq2.one()
}

func (t fq2Test) p() *big.Int {
	return t.f.modulus()
}

func (t fq2Test) equal(a, b fieldElement) bool {
	return t.fq2.equal(a.(*fe2), b.(*fe2))
}

func (t fq2Test) rand(r io.Reader) fieldElement {
	return t.fq2.rand(r)
}

func (t fq2Test) add(c, a, b fieldElement) {
	t.fq2.add(c.(*fe2), a.(*fe2), b.(*fe2))
}

func (t fq2Test) sub(c, a, b fieldElement) {
	t.fq2.sub(c.(*fe2), a.(*fe2), b.(*fe2))
}

func (t fq2Test) mul(c, a, b fieldElement) {
	t.fq2.mul(c.(*fe2), a.(*fe2), b.(*fe2))
}

func (t fq2Test) double(c, a fieldElement) {
	t.fq2.double(c.(*fe2), a.(*fe2))
}

func (t fq2Test) neg(c, a fieldElement) {
	t.fq2.neg(c.(*fe2), a.(*fe2))
}

func (t fq2Test) square(c, a fieldElement) {
	t.fq2.square(c.(*fe2), a.(*fe2))
}

func (t fq2Test) exp(c, a fieldElement, e *big.Int) {
	t.fq2.exp(c.(*fe2), a.(*fe2), e)
}

func (t fq2Test) inverse(c, a fieldElement) bool {
	return t.fq2.inverse(c.(*fe2), a.(*fe2))
}

func (t fq2Test) mulByFq(c, a fieldElement, b fieldElement) {
	t.fq2.mulByFq(c.(*fe2), a.(*fe2), b.(fe))
}

func (t fq2Test) sqrt(c, a fieldElement) bool {
	return t.fq2.sqrt(c.(*fe2), a.(*fe2))
}

type fq3Test struct {
	*fq3
}

func (t fq3Test) new() fieldElement {
	return t.fq3.new()
}

func (t fq3Test) debugElement(in fieldElement) {
	t.fq3.debugElement(in.(*fe3))
}

func (f *fq3) debugElement(in *fe3) {
	fmt.Println(f.toString(in))
}

func (t fq3Test) byteSize() int {
	return t.fq3.byteSize()
}

func (t fq3Test) limbSize() int {
	return t.fq3.f.limbSize
}

func (t fq3Test) fromBytes(in []byte) (fieldElement, error) {
	return t.fq3.fromBytes(in)
}

func (t fq3Test) toBytes(in fieldElement) []byte {
	return t.fq3.toBytes(in.(*fe3))
}

func (t fq3Test) isZero(in fieldElement) bool {
	return t.fq3.isZero(in.(*fe3))
}

func (t fq3Test) isOne(in fieldElement) bool {
	return t.fq3.isOne(in.(*fe3))
}

func (t fq3Test) zero() fieldElement {
	return t.fq3.zero()
}

func (t fq3Test) one() fieldElement {
	return t.fq3.one()
}

func (t fq3Test) p() *big.Int {
	return t.f.modulus()
}

func (t fq3Test) equal(a, b fieldElement) bool {
	return t.fq3.equal(a.(*fe3), b.(*fe3))
}

func (t fq3Test) rand(r io.Reader) fieldElement {
	return t.fq3.rand(r)
}

func (t fq3Test) add(c, a, b fieldElement) {
	t.fq3.add(c.(*fe3), a.(*fe3), b.(*fe3))
}

func (t fq3Test) sub(c, a, b fieldElement) {
	t.fq3.sub(c.(*fe3), a.(*fe3), b.(*fe3))
}

func (t fq3Test) mul(c, a, b fieldElement) {
	t.fq3.mul(c.(*fe3), a.(*fe3), b.(*fe3))
}

func (t fq3Test) double(c, a fieldElement) {
	t.fq3.double(c.(*fe3), a.(*fe3))
}

func (t fq3Test) neg(c, a fieldElement) {
	t.fq3.neg(c.(*fe3), a.(*fe3))
}

func (t fq3Test) square(c, a fieldElement) {
	t.fq3.square(c.(*fe3), a.(*fe3))
}

func (t fq3Test) exp(c, a fieldElement, e *big.Int) {
	t.fq3.exp(c.(*fe3), a.(*fe3), e)
}

func (t fq3Test) inverse(c, a fieldElement) bool {
	return t.fq3.inverse(c.(*fe3), a.(*fe3))
}

func (t fq3Test) mulByFq(c, a fieldElement, b fieldElement) {
	t.fq3.mulByFq(c.(*fe3), a.(*fe3), b.(fe))
}

func (t fq3Test) sqrt(c, a fieldElement) bool {
	// return t.fq.sqrt(c.(*fe3), a.(*fe3))
	return true
}

type fq4Test struct {
	*fq4
}

func (t fq4Test) new() fieldElement {
	return t.fq4.new()
}

func (t fq4Test) debugElement(in fieldElement) {
	t.fq4.debugElement(in.(*fe4))
}

func (f *fq4) debugElement(in *fe4) {
	fmt.Println(f.toString(in))
}

func (t fq4Test) byteSize() int {
	return t.fq4.byteSize()
}

func (t fq4Test) limbSize() int {
	return t.fq4.f.f.limbSize
}

func (t fq4Test) fromBytes(in []byte) (fieldElement, error) {
	return t.fq4.fromBytes(in)
}

func (t fq4Test) toBytes(in fieldElement) []byte {
	return t.fq4.toBytes(in.(*fe4))
}

func (t fq4Test) isZero(in fieldElement) bool {
	return t.fq4.isZero(in.(*fe4))
}

func (t fq4Test) isOne(in fieldElement) bool {
	return t.fq4.isOne(in.(*fe4))
}

func (t fq4Test) zero() fieldElement {
	return t.fq4.zero()
}

func (t fq4Test) one() fieldElement {
	return t.fq4.one()
}

func (t fq4Test) p() *big.Int {
	return t.f.modulus()
}

func (t fq4Test) equal(a, b fieldElement) bool {
	return t.fq4.equal(a.(*fe4), b.(*fe4))
}

func (t fq4Test) rand(r io.Reader) fieldElement {
	return t.fq4.rand(r)
}

func (t fq4Test) add(c, a, b fieldElement) {
	t.fq4.add(c.(*fe4), a.(*fe4), b.(*fe4))
}

func (t fq4Test) sub(c, a, b fieldElement) {
	t.fq4.sub(c.(*fe4), a.(*fe4), b.(*fe4))
}

func (t fq4Test) mul(c, a, b fieldElement) {
	t.fq4.mul(c.(*fe4), a.(*fe4), b.(*fe4))
}

func (t fq4Test) double(c, a fieldElement) {
	t.fq4.double(c.(*fe4), a.(*fe4))
}

func (t fq4Test) neg(c, a fieldElement) {
	t.fq4.neg(c.(*fe4), a.(*fe4))
}

func (t fq4Test) square(c, a fieldElement) {
	t.fq4.square(c.(*fe4), a.(*fe4))
}

func (t fq4Test) exp(c, a fieldElement, e *big.Int) {
	t.fq4.exp(c.(*fe4), a.(*fe4), e)
}

func (t fq4Test) inverse(c, a fieldElement) bool {
	return t.fq4.inverse(c.(*fe4), a.(*fe4))
}

func (t fq4Test) sqrt(c, a fieldElement) bool {
	// return t.fq.sqrt(c.(*fe4), a.(*fe4))
	return true
}

type fq6CTest struct {
	*fq6C
}

func (t fq6CTest) new() fieldElement {
	return t.fq6C.new()
}

func (t fq6CTest) debugElement(in fieldElement) {
	t.fq6C.debugElement(in.(*fe6C))
}

func (f *fq6C) debugElement(in *fe6C) {
	fmt.Println(f.toString(in))
}

func (t fq6CTest) byteSize() int {
	return t.fq6C.byteSize()
}

func (t fq6CTest) limbSize() int {
	return t.fq6C.f.f.limbSize
}

func (t fq6CTest) fromBytes(in []byte) (fieldElement, error) {
	return t.fq6C.fromBytes(in)
}

func (t fq6CTest) toBytes(in fieldElement) []byte {
	return t.fq6C.toBytes(in.(*fe6C))
}

func (t fq6CTest) isZero(in fieldElement) bool {
	return t.fq6C.isZero(in.(*fe6C))
}

func (t fq6CTest) isOne(in fieldElement) bool {
	return t.fq6C.isOne(in.(*fe6C))
}

func (t fq6CTest) zero() fieldElement {
	return t.fq6C.zero()
}

func (t fq6CTest) one() fieldElement {
	return t.fq6C.one()
}

func (t fq6CTest) p() *big.Int {
	return t.f.modulus()
}

func (t fq6CTest) equal(a, b fieldElement) bool {
	return t.fq6C.equal(a.(*fe6C), b.(*fe6C))
}

func (t fq6CTest) rand(r io.Reader) fieldElement {
	return t.fq6C.rand(r)
}

func (t fq6CTest) add(c, a, b fieldElement) {
	t.fq6C.add(c.(*fe6C), a.(*fe6C), b.(*fe6C))
}

func (t fq6CTest) sub(c, a, b fieldElement) {
	t.fq6C.sub(c.(*fe6C), a.(*fe6C), b.(*fe6C))
}

func (t fq6CTest) mul(c, a, b fieldElement) {
	t.fq6C.mul(c.(*fe6C), a.(*fe6C), b.(*fe6C))
}

func (t fq6CTest) double(c, a fieldElement) {
	t.fq6C.double(c.(*fe6C), a.(*fe6C))
}

func (t fq6CTest) neg(c, a fieldElement) {
	t.fq6C.neg(c.(*fe6C), a.(*fe6C))
}

func (t fq6CTest) square(c, a fieldElement) {
	t.fq6C.square(c.(*fe6C), a.(*fe6C))
}

func (t fq6CTest) exp(c, a fieldElement, e *big.Int) {
	t.fq6C.exp(c.(*fe6C), a.(*fe6C), e)
}

func (t fq6CTest) inverse(c, a fieldElement) bool {
	return t.fq6C.inverse(c.(*fe6C), a.(*fe6C))
}

func (t fq6CTest) sqrt(c, a fieldElement) bool {
	// return t.fq.sqrt(c.(*fe6C), a.(*fe6C))
	return true
}

type fq6QTest struct {
	*fq6Q
}

func (t fq6QTest) new() fieldElement {
	return t.fq6Q.new()
}

func (t fq6QTest) debugElement(in fieldElement) {
	t.fq6Q.debugElement(in.(*fe6Q))
}

func (f *fq6Q) debugElement(in *fe6Q) {
	fmt.Println(f.toString(in))
}

func (t fq6QTest) byteSize() int {
	return t.fq6Q.byteSize()
}

func (t fq6QTest) limbSize() int {
	return t.fq6Q.f.f.limbSize
}

func (t fq6QTest) fromBytes(in []byte) (fieldElement, error) {
	return t.fq6Q.fromBytes(in)
}

func (t fq6QTest) toBytes(in fieldElement) []byte {
	return t.fq6Q.toBytes(in.(*fe6Q))
}

func (t fq6QTest) isZero(in fieldElement) bool {
	return t.fq6Q.isZero(in.(*fe6Q))
}

func (t fq6QTest) isOne(in fieldElement) bool {
	return t.fq6Q.isOne(in.(*fe6Q))
}

func (t fq6QTest) zero() fieldElement {
	return t.fq6Q.zero()
}

func (t fq6QTest) one() fieldElement {
	return t.fq6Q.one()
}

func (t fq6QTest) p() *big.Int {
	return t.f.modulus()
}

func (t fq6QTest) equal(a, b fieldElement) bool {
	return t.fq6Q.equal(a.(*fe6Q), b.(*fe6Q))
}

func (t fq6QTest) rand(r io.Reader) fieldElement {
	return t.fq6Q.rand(r)
}

func (t fq6QTest) add(c, a, b fieldElement) {
	t.fq6Q.add(c.(*fe6Q), a.(*fe6Q), b.(*fe6Q))
}

func (t fq6QTest) sub(c, a, b fieldElement) {
	t.fq6Q.sub(c.(*fe6Q), a.(*fe6Q), b.(*fe6Q))
}

func (t fq6QTest) mul(c, a, b fieldElement) {
	t.fq6Q.mul(c.(*fe6Q), a.(*fe6Q), b.(*fe6Q))
}

func (t fq6QTest) double(c, a fieldElement) {
	t.fq6Q.double(c.(*fe6Q), a.(*fe6Q))
}

func (t fq6QTest) neg(c, a fieldElement) {
	t.fq6Q.neg(c.(*fe6Q), a.(*fe6Q))
}

func (t fq6QTest) square(c, a fieldElement) {
	t.fq6Q.square(c.(*fe6Q), a.(*fe6Q))
}

func (t fq6QTest) exp(c, a fieldElement, e *big.Int) {
	t.fq6Q.exp(c.(*fe6Q), a.(*fe6Q), e)
}

func (t fq6QTest) inverse(c, a fieldElement) bool {
	return t.fq6Q.inverse(c.(*fe6Q), a.(*fe6Q))
}

func (t fq6QTest) sqrt(c, a fieldElement) bool {
	// return t.fq.sqrt(c.(*fe6Q), a.(*fe6Q))
	return true
}

type fq12Test struct {
	*fq12
}

func (t fq12Test) new() fieldElement {
	return t.fq12.new()
}

func (t fq12Test) debugElement(in fieldElement) {
	t.fq12.debugElement(in.(*fe12))
}

func (f *fq12) debugElement(in *fe12) {
	fmt.Println(f.toString(in))
}

func (t fq12Test) byteSize() int {
	return t.fq12.byteSize()
}

func (t fq12Test) limbSize() int {
	return t.fq12.f.f.f.limbSize
}

func (t fq12Test) fromBytes(in []byte) (fieldElement, error) {
	return t.fq12.fromBytes(in)
}

func (t fq12Test) toBytes(in fieldElement) []byte {
	return t.fq12.toBytes(in.(*fe12))
}

func (t fq12Test) isZero(in fieldElement) bool {
	return t.fq12.isZero(in.(*fe12))
}

func (t fq12Test) isOne(in fieldElement) bool {
	return t.fq12.isOne(in.(*fe12))
}

func (t fq12Test) zero() fieldElement {
	return t.fq12.zero()
}

func (t fq12Test) one() fieldElement {
	return t.fq12.one()
}

func (t fq12Test) p() *big.Int {
	return t.f.modulus()
}

func (t fq12Test) equal(a, b fieldElement) bool {
	return t.fq12.equal(a.(*fe12), b.(*fe12))
}

func (t fq12Test) rand(r io.Reader) fieldElement {
	return t.fq12.rand(r)
}

func (t fq12Test) add(c, a, b fieldElement) {
	t.fq12.add(c.(*fe12), a.(*fe12), b.(*fe12))
}

func (t fq12Test) sub(c, a, b fieldElement) {
	t.fq12.sub(c.(*fe12), a.(*fe12), b.(*fe12))
}

func (t fq12Test) mul(c, a, b fieldElement) {
	t.fq12.mul(c.(*fe12), a.(*fe12), b.(*fe12))
}

func (t fq12Test) double(c, a fieldElement) {
	t.fq12.double(c.(*fe12), a.(*fe12))
}

func (t fq12Test) neg(c, a fieldElement) {
	t.fq12.neg(c.(*fe12), a.(*fe12))
}

func (t fq12Test) square(c, a fieldElement) {
	t.fq12.square(c.(*fe12), a.(*fe12))
}

func (t fq12Test) exp(c, a fieldElement, e *big.Int) {
	t.fq12.exp(c.(*fe12), a.(*fe12), e)
}

func (t fq12Test) inverse(c, a fieldElement) bool {
	return t.fq12.inverse(c.(*fe12), a.(*fe12))
}

func (t fq12Test) sqrt(c, a fieldElement) bool {
	// return t.fq.sqrt(c.(*fe12), a.(*fe12))
	return true
}

func randFq(limbSize int) *fq {
	var offset int
	t, err := rand.Int(rand.Reader, new(big.Int).SetUint64(64))
	if err != nil {
		panic(err)
	}
	offset = int(t.Uint64())
	byteLen := limbSize * 8
	bitLen := (limbSize-1)*64 + offset
	if bitLen < 32 {
		bitLen = 32
	}
	pbig, err := rand.Prime(rand.Reader, bitLen)
	if err != nil {
		panic(err)
	}
	rawpbytes := pbig.Bytes()
	pbytes := make([]byte, byteLen)
	copy(pbytes[byteLen-len(rawpbytes):], pbig.Bytes())
	field, err := newField(pbytes)
	if err != nil {
		panic(err)
	}
	if limbSize < 4 {
		if field.limbSize != 4 {
			panic("bad random field construction")
		}
	} else {
		if field.limbSize != limbSize {
			panic("bad random field construction")
		}
	}
	return field
}

func resolveLimbSize(bitSize int) int {
	size := (bitSize / 64)
	if bitSize%64 != 0 {
		size += 1
	}
	return size
}

func BenchmarkField(t *testing.B) {
	var limbSize int
	if targetNumberOfLimb > 0 {
		limbSize = targetNumberOfLimb
	} else {
		return
	}
	field := randFq(limbSize)
	if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize != limbSize {
		t.Fatalf("bad field construction")
	}
	bitSize := limbSize * 64
	a := field.rand(rand.Reader)
	b := field.rand(rand.Reader)
	c := field.new()
	t.Run(fmt.Sprintf("%d_add", bitSize), func(t *testing.B) {
		for i := 0; i < t.N; i++ {
			field.add(c, a, b)
		}
	})
	t.Run(fmt.Sprintf("%d_double", bitSize), func(t *testing.B) {
		for i := 0; i < t.N; i++ {
			field.double(c, a)
		}
	})
	t.Run(fmt.Sprintf("%d_sub", bitSize), func(t *testing.B) {
		for i := 0; i < t.N; i++ {
			field.sub(c, a, b)
		}
	})
	t.Run(fmt.Sprintf("%d_mul", bitSize), func(t *testing.B) {
		for i := 0; i < t.N; i++ {
			field.mul(c, a, b)
		}
	})
	t.Run(fmt.Sprintf("%d_cmp", bitSize), func(t *testing.B) {
		for i := 0; i < t.N; i++ {
			field.cmp(a, b)
		}
	})
}

func TestFqShift(t *testing.T) {
	two := big.NewInt(2)
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_shift", limbSize*64), func(t *testing.T) {
			field := randFq(limbSize)
			a := field.rand(rand.Reader)
			bi := field.toBigNoTransform(a)
			da := field.new()
			field.copy(da, a)
			field.div_two(da)
			dbi := new(big.Int).Div(bi, two)
			dbi_2 := field.toBigNoTransform(da)
			if dbi.Cmp(dbi_2) != 0 {
				t.Fatalf("bad div 2 operation")
			}
			ma := field.new()
			field.copy(ma, a)
			field.mul_two(ma)
			mbi := new(big.Int).Mul(bi, two)
			mbi_2 := field.toBigNoTransform(ma)
			if mbi.Cmp(mbi_2) != 0 {
				t.Fatalf("bad mul 2 operation")
			}
		})
	}
}

func TestFqCompare(t *testing.T) {
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_compare", limbSize*64), func(t *testing.T) {
			field := randFq(limbSize)
			if field.cmp(field.r, field.r) != 0 {
				t.Fatalf("r == r (cmp)")
			}
			if !field.equal(field.r, field.r) {
				t.Fatalf("r == r (equal)")
			}
			if field.equal(field.p, field.r) {
				t.Fatalf("p != r")
			}
			if field.equal(field.r, field.zero) {
				t.Fatalf("r != 0")
			}
			if !field.equal(field.zero, field.zero) {
				t.Fatalf("0 == 0")
			}
			if field.cmp(field.p, field.r) != 1 {
				t.Fatalf("p > r")
			}
			if field.cmp(field.r, field.p) != -1 {
				t.Fatalf("r < p")
			}
			if is_even(field.p) {
				t.Fatalf("p is not even")
			}
		})
	}
}

func TestFqCopy(t *testing.T) {
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_copy", limbSize*64), func(t *testing.T) {
			field := randFq(limbSize)
			a := field.rand(rand.Reader)
			b := field.new()
			field.copy(b, a)
			if !field.equal(a, b) {
				t.Fatalf("copy operation fails")
			}
		})
	}
}

func TestFqSerialization(t *testing.T) {
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_serialization", limbSize*64), func(t *testing.T) {
			field := randFq(limbSize)
			if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize != limbSize {
				t.Fatalf("bad field construction\n")
			}
			// demont(r) == 1
			b0 := make([]byte, field.byteSize())
			b0[len(b0)-1] = byte(1)
			b1 := field.toBytes(field.r)
			if !bytes.Equal(b0, b1) {
				t.Fatalf("demont(r) must be equal to 1\n")
			}
			// is a => modulus should not be valid
			_, err := field.fromBytes(field.pbig.Bytes())
			if err == nil {
				t.Fatalf("a number eq or larger than modulus must not be valid")
			}
			for i := 0; i < fuz; i++ {
				field := randFq(limbSize)
				if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize != limbSize {
					t.Fatalf("bad field construction")
				}
				// bytes
				b0 := randBytes(field.pbig)
				if USE_4LIMBS_FOR_LOWER_LIMBS && len(b0) < 32 {
					b0 = padBytes(b0, 32)
				}
				a0, err := field.fromBytes(b0)
				if err != nil {
					t.Fatal(err)
				}
				if USE_4LIMBS_FOR_LOWER_LIMBS && len(b0) < 32 {
					b0 = padBytes(b0, 32)
				}
				b1 = field.toBytes(a0)
				if !bytes.Equal(b0, b1) {
					t.Fatalf("bad serialization (bytes)")
				}
				// string
				s := field.toString(a0)
				a1, err := field.fromString(s)
				if err != nil {
					t.Fatal(err)
				}
				if !field.equal(a0, a1) {
					t.Fatalf("bad serialization (str)")
				}
				// big int
				a0, err = field.fromBytes(b0)
				if err != nil {
					t.Fatal(err)
				}
				bi := field.toBig(a0)
				a1, err = field.fromBig(bi)
				if err != nil {
					t.Fatal(err)
				}
				if !field.equal(a0, a1) {
					t.Fatalf("bad serialization (big.Int)")
				}
				// bytes dense
				b0 = field.toBytesDense(a0)
				a1, err = field.fromBytes(padBytes(b0, field.byteSize()))
				if err != nil {
					t.Fatal(err)
				}
				if !field.equal(a0, a1) {
					t.Fatalf("bad serialization (dense)")
				}
			}
		})
	}
}

func TestFqAdditionCrossAgainstBigInt(t *testing.T) {
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_addition_cross", limbSize*64), func(t *testing.T) {
			for i := 0; i < fuz; i++ {
				field := randFq(limbSize)
				if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize != limbSize {
					t.Fatalf("Bad field construction")
				}
				a := field.rand(rand.Reader)
				b := field.rand(rand.Reader)
				c := field.new()
				big_a := field.toBig(a)
				big_b := field.toBig(b)
				big_c := new(big.Int)
				field.add(c, a, b)
				out_1 := field.toBytes(c)
				out_2 := padBytes(big_c.Add(big_a, big_b).Mod(big_c, field.pbig).Bytes(), field.byteSize())
				if !bytes.Equal(out_1, out_2) {
					t.Fatalf("cross test against big.Int is not satisfied A")
				}
				field.double(c, a)
				out_1 = field.toBytes(c)
				out_2 = padBytes(big_c.Add(big_a, big_a).Mod(big_c, field.pbig).Bytes(), field.byteSize())
				if !bytes.Equal(out_1, out_2) {
					t.Fatalf("cross test against big.Int is not satisfied B")
				}
				field.sub(c, a, b)
				out_1 = field.toBytes(c)
				out_2 = padBytes(big_c.Sub(big_a, big_b).Mod(big_c, field.pbig).Bytes(), field.byteSize())
				if !bytes.Equal(out_1, out_2) {
					t.Fatalf("cross test against big.Int is not satisfied C")
				}
				field.neg(c, a)
				out_1 = field.toBytes(c)
				out_2 = padBytes(big_c.Neg(big_a).Mod(big_c, field.pbig).Bytes(), field.byteSize())
				if !bytes.Equal(out_1, out_2) {
					t.Fatalf("cross test against big.Int is not satisfied D")
				}
			}
		})
	}
}

func TestFqMultiplicationCrossAgainstBigInt(t *testing.T) {
	for limbSize := from; limbSize < to+1; limbSize++ {
		t.Run(fmt.Sprintf("%d_multiplication_cross", limbSize*64), func(t *testing.T) {
			for i := 0; i < fuz; i++ {
				field := randFq(limbSize)
				if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize != limbSize {
					t.Fatalf("bad field construction")
				}
				a := field.rand(rand.Reader)
				b := field.rand(rand.Reader)
				c := field.new()
				big_a := field.toBig(a)
				big_b := field.toBig(b)
				big_c := new(big.Int)
				field.mul(c, a, b)
				out_1 := field.toBytes(c)
				out_2 := padBytes(big_c.Mul(big_a, big_b).Mod(big_c, field.pbig).Bytes(), field.byteSize())
				if !bytes.Equal(out_1, out_2) {
					t.Fatalf("cross test against big.Int is not satisfied")
				}
			}
		})
	}
}

func randFq2(limbSize int) *fq2 {
	fq := randFq(limbSize)
	fq2, err := newFq2(fq, nil)
	if err != nil {
		panic(err)
	}
	// find a non residue
	for {
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 2) {
			fq.copy(fq2.nonResidue, k)
			break
		}
	}
	fq2.calculateFrobeniusCoeffs()
	return fq2
}

func randFq3(limbSize int) *fq3 {
	var fq3 *fq3
	var err error
	for {
		fq := randFq(limbSize)
		fq3, err = newFq3(fq, nil)
		if err != nil {
			panic(err)
		}
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 3) {
			fq.copy(fq3.nonResidue, k)
			break
		}
	}
	return fq3
}

func randFq4(limbSize int) *fq4 {
	var fq4 *fq4
	var fq2 *fq2
	var err error
	for {
		fq := randFq(limbSize)
		fq2, err = newFq2(fq, nil)
		if err != nil {
			panic(err)
		}
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 4) {
			fq.copy(fq2.nonResidue, k)
			break
		}
	}
	for {
		fq4, err = newFq4(fq2, nil)
		if err != nil {
			panic(err)
		}
		k := fq2.rand(rand.Reader)
		if !fq2.isNonResidue(k, 2) {
			fq2.copy(fq4.nonResidue, k)
			break
		}
	}
	return fq4
}

func randFq6Q(limbSize int) *fq6Q {
	var fq6 *fq6Q
	var fq3 *fq3
	var err error
	for {
		fq := randFq(limbSize)
		fq3, err = newFq3(fq, nil)
		if err != nil {
			panic(err)
		}
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 6) {
			fq.copy(fq3.nonResidue, k)
			break
		}
	}
	for {
		fq6, err = newFq6Quadratic(fq3, nil)
		if err != nil {
			panic(err)
		}
		k := fq3.rand(rand.Reader)
		if !fq3.isNonResidue(k, 2) {
			fq3.copy(fq6.nonResidue, k)
			break
		}
	}
	return fq6
}

func randFq6C(limbSize int) *fq6C {
	var fq6 *fq6C
	var fq2 *fq2
	var err error
	for {
		fq := randFq(limbSize)
		fq2, err = newFq2(fq, nil)
		if err != nil {
			panic(err)
		}
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 6) {
			fq.copy(fq2.nonResidue, k)
			break
		}
	}
	for {
		fq6, err = newFq6Cubic(fq2, nil)
		if err != nil {
			panic(err)
		}
		k := fq2.rand(rand.Reader)
		if !fq2.isNonResidue(k, 3) {
			fq2.copy(fq6.nonResidue, k)
			break
		}
	}
	return fq6
}

func randFq12(limbSize int) *fq12 {
	var fq6 *fq6C
	var fq2 *fq2
	var err error
	for {
		fq := randFq(limbSize)
		fq2, err = newFq2(fq, nil)
		if err != nil {
			panic(err)
		}
		k := fq.rand(rand.Reader)
		if !fq.isNonResidue(k, 12) {
			fq.copy(fq2.nonResidue, k)
			break
		}
	}
	for {
		fq6, err = newFq6Cubic(fq2, nil)
		if err != nil {
			panic(err)
		}
		k := fq2.rand(rand.Reader)
		if !fq2.isNonResidue(k, 6) {
			fq2.copy(fq6.nonResidue, k)
			break
		}
	}
	fq12, err := newFq12(fq6, nil)
	if err != nil {
		panic(err)
	}
	return fq12
}

var fields = []string{"FQ", "FQ2", "FQ3", "FQ4", "FQ6Q", "FQ6C", "FQ12"}

func randField(ext string, limbSize int) field {
	switch ext {
	case "FQ":
		return fqTest{randFq(limbSize)}
	case "FQ2":
		return fq2Test{randFq2(limbSize)}
	case "FQ3":
		return fq3Test{randFq3(limbSize)}
	case "FQ4":
		return fq4Test{randFq4(limbSize)}
	case "FQ6Q":
		return fq6QTest{randFq6Q(limbSize)}
	case "FQ6C":
		return fq6CTest{randFq6C(limbSize)}
	case "FQ12":
		return fq12Test{randFq12(limbSize)}
	default:
		panic("unknown extension")
	}
}

func TestFqSerializationGeneric(t *testing.T) {
	for _, ext := range fields {
		for limbSize := from; limbSize < to+1; limbSize++ {
			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
				field := randField(ext, limbSize)
				for i := 0; i < fuz; i++ {
					a0 := field.rand(rand.Reader)
					buf := field.toBytes(a0)
					a1, err := field.fromBytes(buf)
					if err != nil {
						t.Fatal(err)
					}
					if !field.equal(a0, a1) {
						t.Fatalf("bad serialization (bytes)")
					}
				}
			})
		}
	}
}

func TestFqAdditionProperties(t *testing.T) {
	for _, ext := range fields {
		for limbSize := from; limbSize < to+1; limbSize++ {
			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
				for i := 0; i < fuz; i++ {
					field := randField(ext, limbSize)
					zero := field.zero()
					if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize() != limbSize {
						t.Fatalf("bad field construction")
					}
					a := field.rand(rand.Reader)
					b := field.rand(rand.Reader)
					c_1 := field.new()
					c_2 := field.new()
					field.add(c_1, a, zero)
					if !field.equal(c_1, a) {
						t.Fatalf("a + 0 == a")
					}
					field.sub(c_1, a, zero)
					if !field.equal(c_1, a) {
						t.Fatalf("a - 0 == a")
					}
					field.double(c_1, zero)
					if !field.equal(c_1, zero) {
						t.Fatalf("2 * 0 == 0")
					}
					field.neg(c_1, zero)
					if !field.equal(c_1, zero) {
						t.Fatalf("-0 == 0")
					}
					field.sub(c_1, zero, a)
					field.neg(c_2, a)
					if !field.equal(c_1, c_2) {
						t.Fatalf("0-a == -a")
					}
					field.double(c_1, a)
					field.add(c_2, a, a)
					if !field.equal(c_1, c_2) {
						t.Fatalf("2 * a == a + a")
					}
					field.add(c_1, a, b)
					field.add(c_2, b, a)
					if !field.equal(c_1, c_2) {
						t.Fatalf("a + b = b + a")
					}
					field.sub(c_1, a, b)
					field.sub(c_2, b, a)
					field.neg(c_2, c_2)
					if !field.equal(c_1, c_2) {
						t.Fatalf("a - b = - ( b - a )")
					}
					c_x := field.rand(rand.Reader)
					field.add(c_1, a, b)
					field.add(c_1, c_1, c_x)
					field.add(c_2, a, c_x)
					field.add(c_2, c_2, b)
					if !field.equal(c_1, c_2) {
						t.Fatalf("(a + b) + c == (a + c ) + b")
					}
					field.sub(c_1, a, b)
					field.sub(c_1, c_1, c_x)
					field.sub(c_2, a, c_x)
					field.sub(c_2, c_2, b)
					if !field.equal(c_1, c_2) {
						t.Fatalf("(a - b) - c == (a - c ) -b")
					}
				}
			})
		}
	}
}

func TestFqMultiplicationProperties(t *testing.T) {
	for _, ext := range fields {
		for limbSize := from; limbSize < to+1; limbSize++ {
			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
				for i := 0; i < fuz; i++ {
					field := randField(ext, limbSize)
					if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize() != limbSize {
						t.Fatalf("bad field construction")
					}
					a := field.rand(rand.Reader)
					b := field.rand(rand.Reader)
					zero := field.zero()
					one := field.one()
					c_1 := field.new()
					c_2 := field.new()
					field.mul(c_1, a, zero)
					if !field.equal(c_1, zero) {
						t.Fatalf("a * 0 == 0")
					}
					field.mul(c_1, a, one)
					if !field.equal(c_1, a) {
						t.Fatalf("a * 1 == a")
					}
					field.mul(c_1, a, b)
					field.mul(c_2, b, a)
					if !field.equal(c_1, c_2) {
						t.Fatalf("a * b == b * a")
					}
					c_x := field.rand(rand.Reader)
					field.mul(c_1, a, b)
					field.mul(c_1, c_1, c_x)
					field.mul(c_2, c_x, b)
					field.mul(c_2, c_2, a)
					if !field.equal(c_1, c_2) {
						t.Fatalf("(a * b) * c == (a * c) * b")
					}
				}
			})
		}
	}
}

func TestFqExponentiation(t *testing.T) {
	for _, ext := range fields {
		for limbSize := from; limbSize < to+1; limbSize++ {
			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
				for i := 0; i < fuz; i++ {
					field := randField(ext, limbSize)
					if !USE_4LIMBS_FOR_LOWER_LIMBS && field.limbSize() != limbSize {
						t.Fatalf("bad field construction")
					}
					a := field.rand(rand.Reader)
					u := field.new()
					field.exp(u, a, big.NewInt(0))
					if !field.equal(u, field.one()) {
						t.Fatalf("a^0 == 1")
					}
					field.exp(u, a, big.NewInt(1))
					if !field.equal(u, a) {
						t.Fatalf("a^1 == a")
					}
					v := field.new()
					field.mul(u, a, a)
					field.mul(u, u, u)
					field.mul(u, u, u)
					field.exp(v, a, big.NewInt(8))
					if !field.equal(u, v) {
						t.Fatalf("((a^2)^2)^2 == a^8")
					}
					p := new(big.Int).Set(field.p())
					field.exp(u, a, p)
					if !field.equal(u, a) {
						t.Fatalf("a^p == a")
					}
					field.exp(u, a, p.Sub(p, big.NewInt(1)))
					if !field.equal(u, field.one()) {
						t.Fatalf("a^(p-1) == 1")
					}
				}
			})
		}
	}
}

func TestFqInversion(t *testing.T) {
	for _, ext := range fields {
		for limbSize := from; limbSize < to+1; limbSize++ {
			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
				for i := 0; i < fuz; i++ {
					field := randField(ext, limbSize)
					u := field.new()
					zero := field.zero()
					one := field.one()
					field.inverse(u, zero)
					if !field.equal(u, zero) {
						t.Fatalf("(0^-1) == 0)")
					}
					field.inverse(u, one)
					if !field.equal(u, one) {
						t.Fatalf("(1^-1) == 1)")
					}
					a := field.rand(rand.Reader)
					field.inverse(u, a)
					field.mul(u, u, a)
					if !field.equal(u, one) {
						t.Fatalf("(r*a) * r*(a^-1) == r)")
					}
					v := field.new()
					p := new(big.Int).Set(field.p())
					field.exp(u, a, p.Sub(p, big.NewInt(2)))
					field.inverse(v, a)
					if !field.equal(v, u) {
						t.Fatalf("a^(p-2) == a^-1")
					}
				}
			})
		}
	}
}

// func TestFqSquareRoot(t *testing.T) {
// 	fields = []string{"FQ"}
// 	for _, ext := range fields {
// 		for limbSize := from; limbSize < 4; limbSize++ {
// 			// for limbSize := from; limbSize < to+1; limbSize++ {
// 			t.Run(fmt.Sprintf("%d_%s", limbSize*64, ext), func(t *testing.T) {
// 				for i := 0; i < fuz; i++ {
// 					field := randField(ext, limbSize)
// 					u := field.new()
// 					zero := field.zero()
// 					one := field.one()
// 					field.sqrt(u, zero)
// 					if !field.equal(u, zero) {
// 						t.Errorf("(0^(1/2)) == 0)")
// 					}
// 					field.sqrt(u, one)
// 					if !field.equal(u, one) {
// 						// t.Errorf("(1^(1/2)) == 1)")
// 					}
// 					v, w, negA := field.new(), field.new(), field.new()
// 					a := field.rand(rand.Reader)
// 					field.neg(negA, a)
// 					field.square(u, a)
// 					field.square(w, negA)
// 					if !field.equal(w, u) {
// 						// TODO: why fails?
// 						// t.Errorf("square of r and -r is not same")
// 					}
// 					if hasRoot := field.sqrt(v, u); !hasRoot {
// 						// t.Errorf("elem has no square-root")
// 					}
// 					if !field.equal(a, v) && !field.equal(negA, v) {
// 						field.debugElement(a)
// 						field.debugElement(negA)
// 						field.debugElement(v)
// 						// t.Errorf("((r)^2)^(1/2) == r)")
// 					}
// 				}
// 			})
// 		}
// 	}
// }