package kzg
|
|
|
|
import (
|
|
"bytes"
|
|
"crypto/rand"
|
|
"math/big"
|
|
"testing"
|
|
|
|
"github.com/stretchr/testify/assert"
|
|
)
|
|
|
|
func randBI() *big.Int {
|
|
maxbits := 256
|
|
b := make([]byte, (maxbits/8)-1)
|
|
_, err := rand.Read(b)
|
|
if err != nil {
|
|
panic(err)
|
|
}
|
|
r := new(big.Int).SetBytes(b)
|
|
return new(big.Int).Mod(r, Q)
|
|
}
|
|
|
|
func neg(a *big.Int) *big.Int {
|
|
return new(big.Int).Neg(a)
|
|
}
|
|
|
|
func TestPolynomial(t *testing.T) {
|
|
b0 := big.NewInt(int64(0))
|
|
b1 := big.NewInt(int64(1))
|
|
b2 := big.NewInt(int64(2))
|
|
b3 := big.NewInt(int64(3))
|
|
b4 := big.NewInt(int64(4))
|
|
b5 := big.NewInt(int64(5))
|
|
b6 := big.NewInt(int64(6))
|
|
b16 := big.NewInt(int64(16))
|
|
|
|
a := []*big.Int{b1, b0, b5}
|
|
b := []*big.Int{b3, b0, b1}
|
|
|
|
// new Finite Field
|
|
r, ok := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10) //nolint:lll
|
|
assert.True(nil, ok)
|
|
|
|
// polynomial multiplication
|
|
o := polynomialMul(a, b)
|
|
assert.Equal(t, o, []*big.Int{b3, b0, b16, b0, b5})
|
|
|
|
// polynomial division
|
|
quo, rem := polynomialDiv(a, b)
|
|
assert.Equal(t, quo[0].Int64(), int64(5))
|
|
// check the rem result without modulo
|
|
assert.Equal(t, new(big.Int).Sub(rem[0], r).Int64(), int64(-14))
|
|
|
|
c := []*big.Int{neg(b4), b0, neg(b2), b1}
|
|
d := []*big.Int{neg(b3), b1}
|
|
quo2, rem2 := polynomialDiv(c, d)
|
|
assert.Equal(t, quo2, []*big.Int{b3, b1, b1})
|
|
assert.Equal(t, rem2[0].Int64(), int64(5))
|
|
|
|
// polynomial addition
|
|
o = polynomialAdd(a, b)
|
|
assert.Equal(t, o, []*big.Int{b4, b0, b6})
|
|
|
|
// polynomial subtraction
|
|
o1 := polynomialSub(a, b)
|
|
o2 := polynomialSub(b, a)
|
|
o = polynomialAdd(o1, o2)
|
|
assert.True(t, bytes.Equal(b0.Bytes(), o[0].Bytes()))
|
|
assert.True(t, bytes.Equal(b0.Bytes(), o[1].Bytes()))
|
|
assert.True(t, bytes.Equal(b0.Bytes(), o[2].Bytes()))
|
|
|
|
c = []*big.Int{b5, b6, b1}
|
|
d = []*big.Int{b1, b3}
|
|
o = polynomialSub(c, d)
|
|
assert.Equal(t, o, []*big.Int{b4, b3, b1})
|
|
|
|
// NewPolZeroAt
|
|
o = newPolZeroAt(3, 4, b4)
|
|
assert.Equal(t, polynomialEval(o, big.NewInt(3)), b4)
|
|
o = newPolZeroAt(2, 4, b3)
|
|
assert.Equal(t, polynomialEval(o, big.NewInt(2)), b3)
|
|
|
|
// polynomialEval
|
|
// p(x) = x^3 + x + 5
|
|
p := []*big.Int{
|
|
big.NewInt(5),
|
|
big.NewInt(1), // x^1
|
|
big.NewInt(0), // x^2
|
|
big.NewInt(1), // x^3
|
|
}
|
|
assert.Equal(t, "x³ + x¹ + 5", PolynomialToString(p))
|
|
assert.Equal(t, "35", polynomialEval(p, big.NewInt(3)).String())
|
|
assert.Equal(t, "1015", polynomialEval(p, big.NewInt(10)).String())
|
|
assert.Equal(t, "16777477", polynomialEval(p, big.NewInt(256)).String())
|
|
assert.Equal(t, "125055", polynomialEval(p, big.NewInt(50)).String())
|
|
assert.Equal(t, "7", polynomialEval(p, big.NewInt(1)).String())
|
|
}
|
|
|
|
func BenchmarkArithmetic(b *testing.B) {
|
|
// generate arrays with bigint
|
|
var p, q []*big.Int
|
|
for i := 0; i < 1000; i++ {
|
|
pi := randBI()
|
|
p = append(p, pi)
|
|
}
|
|
for i := 1000 - 1; i >= 0; i-- {
|
|
q = append(q, p[i])
|
|
}
|
|
|
|
b.Run("polynomialSub", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
polynomialSub(p, q)
|
|
}
|
|
})
|
|
b.Run("polynomialMul", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
polynomialMul(p, q)
|
|
}
|
|
})
|
|
b.Run("polynomialDiv", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
polynomialDiv(p, q)
|
|
}
|
|
})
|
|
}
|
|
|
|
func TestLagrangeInterpolation(t *testing.T) {
|
|
x0 := big.NewInt(3)
|
|
y0 := big.NewInt(35)
|
|
x1 := big.NewInt(10)
|
|
y1 := big.NewInt(1015)
|
|
x2 := big.NewInt(256)
|
|
y2 := big.NewInt(16777477)
|
|
x3 := big.NewInt(50)
|
|
y3 := big.NewInt(125055)
|
|
|
|
xs := []*big.Int{x0, x1, x2, x3}
|
|
ys := []*big.Int{y0, y1, y2, y3}
|
|
|
|
p, err := LagrangeInterpolation(xs, ys)
|
|
assert.Nil(t, err)
|
|
assert.Equal(t, "x³ + x¹ + 5", PolynomialToString(p))
|
|
|
|
assert.Equal(t, y0, polynomialEval(p, x0))
|
|
assert.Equal(t, y1, polynomialEval(p, x1))
|
|
assert.Equal(t, y2, polynomialEval(p, x2))
|
|
}
|
|
|
|
func TestZeroPolynomial(t *testing.T) {
|
|
x0 := big.NewInt(1)
|
|
x1 := big.NewInt(40)
|
|
x2 := big.NewInt(512)
|
|
xs := []*big.Int{x0, x1, x2}
|
|
|
|
z := zeroPolynomial(xs)
|
|
assert.Equal(t, "x³ "+
|
|
"+ 21888242871839275222246405745257275088548364400416034343698204186575808495064x² "+
|
|
"+ 21032x¹ + 21888242871839275222246405745257275088548364400416034343698204186575808475137",
|
|
PolynomialToString(z))
|
|
|
|
assert.Equal(t, "0", polynomialEval(z, x0).String())
|
|
assert.Equal(t, "0", polynomialEval(z, x1).String())
|
|
assert.Equal(t, "0", polynomialEval(z, x2).String())
|
|
}
|