polynomial.go

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

     1  // Package polynomial provides representations of polynomials over the scalars
     2  // of a group.
     3  package polynomial
     4  
     5  import "github.com/cloudflare/circl/group"
     6  
     7  // Polynomial stores a polynomial over the set of scalars of a group.
     8  type Polynomial struct {
     9  	// Internal representation is in polynomial basis:
    10  	// Thus,
    11  	//     p(x) = \sum_i^k c[i] x^i,
    12  	// where k = len(c)-1 is the degree of the polynomial.
    13  	c []group.Scalar
    14  }
    15  
    16  // New creates a new polynomial given its coefficients in ascending order.
    17  // Thus,
    18  //
    19  //	p(x) = \sum_i^k c[i] x^i,
    20  //
    21  // where k = len(c)-1 is the degree of the polynomial.
    22  //
    23  // The zero polynomial has degree equal to -1 and can be instantiated passing
    24  // nil to New.
    25  func New(coeffs []group.Scalar) (p Polynomial) {
    26  	if l := len(coeffs); l != 0 {
    27  		p.c = make([]group.Scalar, l)
    28  		for i := range coeffs {
    29  			p.c[i] = coeffs[i].Copy()
    30  		}
    31  	}
    32  
    33  	return
    34  }
    35  
    36  func (p Polynomial) Degree() int {
    37  	i := len(p.c) - 1
    38  	for i > 0 && p.c[i].IsZero() {
    39  		i--
    40  	}
    41  	return i
    42  }
    43  
    44  func (p Polynomial) Evaluate(x group.Scalar) group.Scalar {
    45  	px := x.Group().NewScalar()
    46  	if l := len(p.c); l != 0 {
    47  		px.Set(p.c[l-1])
    48  		for i := l - 2; i >= 0; i-- {
    49  			px.Mul(px, x)
    50  			px.Add(px, p.c[i])
    51  		}
    52  	}
    53  	return px
    54  }
    55  
    56  // LagrangePolynomial stores a Lagrange polynomial over the set of scalars of a group.
    57  type LagrangePolynomial struct {
    58  	// Internal representation is in Lagrange basis:
    59  	// Thus,
    60  	//     p(x) = \sum_i^k y[i] L_j(x), where k is the degree of the polynomial,
    61  	//     L_j(x) = \prod_i^k (x-x[i])/(x[j]-x[i]),
    62  	//     y[i] = p(x[i]), and
    63  	//     all x[i] are different.
    64  	x, y []group.Scalar
    65  }
    66  
    67  // NewLagrangePolynomial creates a polynomial in Lagrange basis given a list
    68  // of nodes (x) and values (y), such that:
    69  //
    70  //	p(x) = \sum_i^k y[i] L_j(x), where k is the degree of the polynomial,
    71  //	L_j(x) = \prod_i^k (x-x[i])/(x[j]-x[i]),
    72  //	y[i] = p(x[i]), and
    73  //	all x[i] are different.
    74  //
    75  // It panics if one of these conditions does not hold.
    76  //
    77  // The zero polynomial has degree equal to -1 and can be instantiated passing
    78  // (nil,nil) to NewLagrangePolynomial.
    79  func NewLagrangePolynomial(x, y []group.Scalar) (l LagrangePolynomial) {
    80  	if len(x) != len(y) {
    81  		panic("lagrange: invalid length")
    82  	}
    83  
    84  	if !areAllDifferent(x) {
    85  		panic("lagrange: x[i] must be different")
    86  	}
    87  
    88  	if n := len(x); n != 0 {
    89  		l.x, l.y = make([]group.Scalar, n), make([]group.Scalar, n)
    90  		for i := range x {
    91  			l.x[i], l.y[i] = x[i].Copy(), y[i].Copy()
    92  		}
    93  	}
    94  
    95  	return
    96  }
    97  
    98  func (l LagrangePolynomial) Degree() int { return len(l.x) - 1 }
    99  
   100  func (l LagrangePolynomial) Evaluate(x group.Scalar) group.Scalar {
   101  	px := x.Group().NewScalar()
   102  	tmp := x.Group().NewScalar()
   103  	for i := range l.x {
   104  		LjX := baseRatio(uint(i), l.x, x)
   105  		tmp.Mul(l.y[i], LjX)
   106  		px.Add(px, tmp)
   107  	}
   108  
   109  	return px
   110  }
   111  
   112  // LagrangeBase returns the j-th Lagrange polynomial base evaluated at x.
   113  // Thus, L_j(x) = \prod (x - x[i]) / (x[j] - x[i]) for 0 <= i < k, and i != j.
   114  func LagrangeBase(jth uint, xi []group.Scalar, x group.Scalar) group.Scalar {
   115  	if jth >= uint(len(xi)) {
   116  		panic("lagrange: invalid index")
   117  	}
   118  	return baseRatio(jth, xi, x)
   119  }
   120  
   121  func baseRatio(jth uint, xi []group.Scalar, x group.Scalar) group.Scalar {
   122  	num := x.Copy()
   123  	num.SetUint64(1)
   124  	den := x.Copy()
   125  	den.SetUint64(1)
   126  
   127  	tmp := x.Copy()
   128  	for i := range xi {
   129  		if uint(i) != jth {
   130  			num.Mul(num, tmp.Sub(x, xi[i]))
   131  			den.Mul(den, tmp.Sub(xi[jth], xi[i]))
   132  		}
   133  	}
   134  
   135  	return num.Mul(num, den.Inv(den))
   136  }
   137  
   138  func areAllDifferent(x []group.Scalar) bool {
   139  	m := make(map[string]struct{})
   140  	for i := range x {
   141  		k, err := x[i].MarshalBinary()
   142  		if err != nil {
   143  			panic(err)
   144  		}
   145  		if _, exists := m[string(k)]; exists {
   146  			return false
   147  		}
   148  		m[string(k)] = struct{}{}
   149  	}
   150  	return true
   151  }
   152
View as plain text