Debian Codegraph @

vdaf/prio3/arith/templates/poly.go.tmpl

raw
1 // +build ignore
2 // The previous line (and this one up to the warning below) is removed by the
3 // template generator.
4
5 // Code generated from ./templates/poly.go.tmpl. DO NOT EDIT.
6
7 package {{.Name | ToLower}}
8
9 import "github.com/cloudflare/circl/math"
10
11 type Poly []Fp
12
13 func (p Poly) AddAssign(x Poly) { Vec(p).AddAssign(Vec(x)) }
14 func (p Poly) SubAssign(x Poly) { Vec(p).SubAssign(Vec(x)) }
15 func (p Poly) Mul(x, y Poly) {
16 const thresholdPolyMul = 128
17 if len(x) + len(y) - 1 < thresholdPolyMul {
18 p.MulNSquare(x, y)
19 } else{
20 p.MulNlogN(x, y)
21 }
22 }
23
24 func (p Poly) MulNSquare(x, y Poly) {
25 mustSumLen(p, x, y)
26 clear(p)
27 var xiyj Fp
28 for i := range x {
29 for j := range y {
30 xiyj.Mul(&x[i], &y[j])
31 p[i+j].AddAssign(&xiyj)
32 }
33 }
34 }
35
36 func (p Poly) MulNlogN(x, y Poly) {
37 mustSumLen(p, x, y)
38 N, logN := math.NextPow2(uint(len(x) + len(y) - 1))
39 buf := make(Vec, 2*N)
40 lx, ly := buf[:N], buf[N:]
41 lx.NTT(Vec(x), N)
42 ly.NTT(Vec(y), N)
43 for i := range lx {
44 lx[i].MulAssign(&ly[i])
45 }
46
47 ly.InvNTT(lx, N)
48 var invN Fp
49 invN.InvTwoN(logN)
50 copy(p, ly)
51 Vec(p).ScalarMul(&invN)
52 }
53
54 func (p Poly) Sqr(x Poly) {
55 mustSumLen(p, x, x)
56 clear(p)
57 for i := range x {
58 p[2*i].Sqr(&x[i])
59 }
60
61 var xixj Fp
62 for i := 0; i < len(x); i++ {
63 for j := i + 1; j < len(x); j++ {
64 xixj.Mul(&x[i], &x[j])
65 xixj.AddAssign(&xixj)
66 p[i+j].AddAssign(&xixj)
67 }
68 }
69 }
70
71 func (p Poly) Evaluate(x *Fp) (px Fp) {
72 if l := len(p); l != 0 {
73 px = p[l-1]
74 for i := l - 2; i >= 0; i-- {
75 px.MulAssign(x)
76 px.AddAssign(&p[i])
77 }
78 }
79
80 return
81 }
82
83 func (p Poly) Strip() Poly {
84 for i := len(p) - 1; i >= 0; i-- {
85 if !p[i].IsZero() {
86 return p[:i+1]
87 }
88 }
89
90 return p[:0]
91 }
92