1package kzg
  2
  3import (
  4	"bytes"
  5	"crypto/rand"
  6	"math/big"
  7	"testing"
  8
  9	"github.com/stretchr/testify/assert"
 10)
 11
 12func randBI() *big.Int {
 13	maxbits := 256
 14	b := make([]byte, (maxbits/8)-1)
 15	_, err := rand.Read(b)
 16	if err != nil {
 17		panic(err)
 18	}
 19	r := new(big.Int).SetBytes(b)
 20	return new(big.Int).Mod(r, Q)
 21}
 22
 23func neg(a *big.Int) *big.Int {
 24	return new(big.Int).Neg(a)
 25}
 26
 27func TestPolynomial(t *testing.T) {
 28	b0 := big.NewInt(int64(0))
 29	b1 := big.NewInt(int64(1))
 30	b2 := big.NewInt(int64(2))
 31	b3 := big.NewInt(int64(3))
 32	b4 := big.NewInt(int64(4))
 33	b5 := big.NewInt(int64(5))
 34	b6 := big.NewInt(int64(6))
 35	b16 := big.NewInt(int64(16))
 36
 37	a := []*big.Int{b1, b0, b5}
 38	b := []*big.Int{b3, b0, b1}
 39
 40	// new Finite Field
 41	r, ok := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10) //nolint:lll
 42	assert.True(nil, ok)
 43
 44	// polynomial multiplication
 45	o := polynomialMul(a, b)
 46	assert.Equal(t, o, []*big.Int{b3, b0, b16, b0, b5})
 47
 48	// polynomial division
 49	quo, rem := polynomialDiv(a, b)
 50	assert.Equal(t, quo[0].Int64(), int64(5))
 51	// check the rem result without modulo
 52	assert.Equal(t, new(big.Int).Sub(rem[0], r).Int64(), int64(-14))
 53
 54	c := []*big.Int{neg(b4), b0, neg(b2), b1}
 55	d := []*big.Int{neg(b3), b1}
 56	quo2, rem2 := polynomialDiv(c, d)
 57	assert.Equal(t, quo2, []*big.Int{b3, b1, b1})
 58	assert.Equal(t, rem2[0].Int64(), int64(5))
 59
 60	// polynomial addition
 61	o = polynomialAdd(a, b)
 62	assert.Equal(t, o, []*big.Int{b4, b0, b6})
 63
 64	// polynomial subtraction
 65	o1 := polynomialSub(a, b)
 66	o2 := polynomialSub(b, a)
 67	o = polynomialAdd(o1, o2)
 68	assert.True(t, bytes.Equal(b0.Bytes(), o[0].Bytes()))
 69	assert.True(t, bytes.Equal(b0.Bytes(), o[1].Bytes()))
 70	assert.True(t, bytes.Equal(b0.Bytes(), o[2].Bytes()))
 71
 72	c = []*big.Int{b5, b6, b1}
 73	d = []*big.Int{b1, b3}
 74	o = polynomialSub(c, d)
 75	assert.Equal(t, o, []*big.Int{b4, b3, b1})
 76
 77	// NewPolZeroAt
 78	o = newPolZeroAt(3, 4, b4)
 79	assert.Equal(t, polynomialEval(o, big.NewInt(3)), b4)
 80	o = newPolZeroAt(2, 4, b3)
 81	assert.Equal(t, polynomialEval(o, big.NewInt(2)), b3)
 82
 83	// polynomialEval
 84	// p(x) = x^3 + x + 5
 85	p := []*big.Int{
 86		big.NewInt(5),
 87		big.NewInt(1), // x^1
 88		big.NewInt(0), // x^2
 89		big.NewInt(1), // x^3
 90	}
 91	assert.Equal(t, "x³ + x¹ + 5", PolynomialToString(p))
 92	assert.Equal(t, "35", polynomialEval(p, big.NewInt(3)).String())
 93	assert.Equal(t, "1015", polynomialEval(p, big.NewInt(10)).String())
 94	assert.Equal(t, "16777477", polynomialEval(p, big.NewInt(256)).String())
 95	assert.Equal(t, "125055", polynomialEval(p, big.NewInt(50)).String())
 96	assert.Equal(t, "7", polynomialEval(p, big.NewInt(1)).String())
 97}
 98
 99func BenchmarkArithmetic(b *testing.B) {
100	// generate arrays with bigint
101	var p, q []*big.Int
102	for i := 0; i < 1000; i++ {
103		pi := randBI()
104		p = append(p, pi)
105	}
106	for i := 1000 - 1; i >= 0; i-- {
107		q = append(q, p[i])
108	}
109
110	b.Run("polynomialSub", func(b *testing.B) {
111		for i := 0; i < b.N; i++ {
112			polynomialSub(p, q)
113		}
114	})
115	b.Run("polynomialMul", func(b *testing.B) {
116		for i := 0; i < b.N; i++ {
117			polynomialMul(p, q)
118		}
119	})
120	b.Run("polynomialDiv", func(b *testing.B) {
121		for i := 0; i < b.N; i++ {
122			polynomialDiv(p, q)
123		}
124	})
125}
126
127func TestLagrangeInterpolation(t *testing.T) {
128	x0 := big.NewInt(3)
129	y0 := big.NewInt(35)
130	x1 := big.NewInt(10)
131	y1 := big.NewInt(1015)
132	x2 := big.NewInt(256)
133	y2 := big.NewInt(16777477)
134	x3 := big.NewInt(50)
135	y3 := big.NewInt(125055)
136
137	xs := []*big.Int{x0, x1, x2, x3}
138	ys := []*big.Int{y0, y1, y2, y3}
139
140	p, err := LagrangeInterpolation(xs, ys)
141	assert.Nil(t, err)
142	assert.Equal(t, "x³ + x¹ + 5", PolynomialToString(p))
143
144	assert.Equal(t, y0, polynomialEval(p, x0))
145	assert.Equal(t, y1, polynomialEval(p, x1))
146	assert.Equal(t, y2, polynomialEval(p, x2))
147}
148
149func TestZeroPolynomial(t *testing.T) {
150	x0 := big.NewInt(1)
151	x1 := big.NewInt(40)
152	x2 := big.NewInt(512)
153	xs := []*big.Int{x0, x1, x2}
154
155	z := zeroPolynomial(xs)
156	assert.Equal(t, "x³ "+
157		"+ 21888242871839275222246405745257275088548364400416034343698204186575808495064x² "+
158		"+ 21032x¹ + 21888242871839275222246405745257275088548364400416034343698204186575808475137",
159		PolynomialToString(z))
160
161	assert.Equal(t, "0", polynomialEval(z, x0).String())
162	assert.Equal(t, "0", polynomialEval(z, x1).String())
163	assert.Equal(t, "0", polynomialEval(z, x2).String())
164}