polynomial_test.go

Documentation: github.com/cloudflare/circl/math/polynomial

     1  package polynomial_test
     2  
     3  import (
     4  	"testing"
     5  
     6  	"github.com/cloudflare/circl/group"
     7  	"github.com/cloudflare/circl/internal/test"
     8  	"github.com/cloudflare/circl/math/polynomial"
     9  )
    10  
    11  func TestPolyDegree(t *testing.T) {
    12  	g := group.P256
    13  
    14  	t.Run("zeroPoly", func(t *testing.T) {
    15  		p := polynomial.New(nil)
    16  		test.CheckOk(p.Degree() == -1, "it should be -1", t)
    17  		p = polynomial.New([]group.Scalar{})
    18  		test.CheckOk(p.Degree() == -1, "it should be -1", t)
    19  	})
    20  
    21  	t.Run("constantPoly", func(t *testing.T) {
    22  		c := []group.Scalar{
    23  			g.NewScalar().SetUint64(0),
    24  			g.NewScalar().SetUint64(0),
    25  		}
    26  		p := polynomial.New(c)
    27  		test.CheckOk(p.Degree() == 0, "it should be 0", t)
    28  	})
    29  
    30  	t.Run("linearPoly", func(t *testing.T) {
    31  		c := []group.Scalar{
    32  			g.NewScalar().SetUint64(0),
    33  			g.NewScalar().SetUint64(1),
    34  			g.NewScalar().SetUint64(0),
    35  		}
    36  		p := polynomial.New(c)
    37  		test.CheckOk(p.Degree() == 1, "it should be 1", t)
    38  	})
    39  }
    40  
    41  func TestPolyEval(t *testing.T) {
    42  	g := group.P256
    43  	c := []group.Scalar{
    44  		g.NewScalar(),
    45  		g.NewScalar(),
    46  		g.NewScalar(),
    47  	}
    48  	c[0].SetUint64(5)
    49  	c[1].SetUint64(5)
    50  	c[2].SetUint64(2)
    51  	p := polynomial.New(c)
    52  
    53  	x := g.NewScalar()
    54  	x.SetUint64(10)
    55  
    56  	got := p.Evaluate(x)
    57  	want := g.NewScalar()
    58  	want.SetUint64(255)
    59  	if !got.IsEqual(want) {
    60  		test.ReportError(t, got, want)
    61  	}
    62  }
    63  
    64  func TestLagrange(t *testing.T) {
    65  	g := group.P256
    66  	c := []group.Scalar{
    67  		g.NewScalar(),
    68  		g.NewScalar(),
    69  		g.NewScalar(),
    70  	}
    71  	c[0].SetUint64(1234)
    72  	c[1].SetUint64(166)
    73  	c[2].SetUint64(94)
    74  	p := polynomial.New(c)
    75  
    76  	x := []group.Scalar{g.NewScalar(), g.NewScalar(), g.NewScalar()}
    77  	x[0].SetUint64(2)
    78  	x[1].SetUint64(4)
    79  	x[2].SetUint64(5)
    80  
    81  	y := []group.Scalar{}
    82  	for i := range x {
    83  		y = append(y, p.Evaluate(x[i]))
    84  	}
    85  
    86  	zero := g.NewScalar()
    87  	l := polynomial.NewLagrangePolynomial(x, y)
    88  	test.CheckOk(l.Degree() == p.Degree(), "bad degree", t)
    89  
    90  	got := l.Evaluate(zero)
    91  	want := p.Evaluate(zero)
    92  
    93  	if !got.IsEqual(want) {
    94  		test.ReportError(t, got, want)
    95  	}
    96  
    97  	// Test Kronecker's delta of LagrangeBase.
    98  	// Thus:
    99  	//    L_j(x[i]) = { 1, if i == j;
   100  	//                { 0, otherwise.
   101  	one := g.NewScalar()
   102  	one.SetUint64(1)
   103  	for j := range x {
   104  		for i := range x {
   105  			got := polynomial.LagrangeBase(uint(j), x, x[i])
   106  
   107  			if i == j {
   108  				want = one
   109  			} else {
   110  				want = zero
   111  			}
   112  
   113  			if !got.IsEqual(want) {
   114  				test.ReportError(t, got, want)
   115  			}
   116  		}
   117  	}
   118  
   119  	// Test that inputs are different length
   120  	err := test.CheckPanic(func() { polynomial.NewLagrangePolynomial(x, y[:1]) })
   121  	test.CheckNoErr(t, err, "should panic")
   122  
   123  	// Test that nodes must be different.
   124  	x[0].Set(x[1])
   125  	err = test.CheckPanic(func() { polynomial.NewLagrangePolynomial(x, y) })
   126  	test.CheckNoErr(t, err, "should panic")
   127  
   128  	// Test LagrangeBase wrong index
   129  	err = test.CheckPanic(func() { polynomial.LagrangeBase(10, x, zero) })
   130  	test.CheckNoErr(t, err, "should panic")
   131  }
   132
View as plain text