| 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 |
|