-
Notifications
You must be signed in to change notification settings - Fork 136
/
poly.go
73 lines (59 loc) · 1.4 KB
/
poly.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package secretsharing
import (
"errors"
"io"
"github.com/cloudflare/circl/group"
)
type polynomial struct {
deg uint64
coeff []group.Scalar
}
func randomPolynomial(rnd io.Reader, g group.Group, deg uint64) (p polynomial) {
p = polynomial{deg, make([]group.Scalar, deg+1)}
for i := 0; i <= int(deg); i++ {
p.coeff[i] = g.RandomScalar(rnd)
}
return
}
func (p polynomial) evaluate(x group.Scalar) group.Scalar {
px := p.coeff[p.deg].Copy()
for i := int(p.deg) - 1; i >= 0; i-- {
px.Mul(px, x)
px.Add(px, p.coeff[i])
}
return px
}
func LagrangeCoefficient(g group.Group, x []group.Scalar, index uint64) group.Scalar {
if index > uint64(len(x)) {
panic("invalid parameter")
}
num := g.NewScalar()
num.SetUint64(1)
den := g.NewScalar()
den.SetUint64(1)
tmp := g.NewScalar()
for j := range x {
if j != int(index) {
num.Mul(num, x[j])
den.Mul(den, tmp.Sub(x[j], x[index]))
}
}
return num.Mul(num, tmp.Inv(den))
}
func LagrangeInterpolate(g group.Group, x, px []group.Scalar) (group.Scalar, error) {
if len(x) != len(px) {
return nil, errors.New("lagrange: bad input length")
}
zero := g.NewScalar()
for i := range x {
if x[i].IsEqual(zero) {
return nil, errors.New("lagrange: tried to evaluate on zero")
}
}
pol0 := g.NewScalar()
delta := g.NewScalar()
for i := range x {
pol0.Add(pol0, delta.Mul(px[i], LagrangeCoefficient(g, x, uint64(i))))
}
return pol0, nil
}