-
Notifications
You must be signed in to change notification settings - Fork 135
/
generic.go
77 lines (67 loc) · 2.43 KB
/
generic.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
74
75
76
77
//go:build !amd64 || purego
// +build !amd64 purego
package common
// Sets p to a + b. Does not normalize coefficients.
func (p *Poly) Add(a, b *Poly) {
p.addGeneric(a, b)
}
// Sets p to a - b. Does not normalize coefficients.
func (p *Poly) Sub(a, b *Poly) {
p.subGeneric(a, b)
}
// Executes an in-place forward "NTT" on p.
//
// Assumes the coefficients are in absolute value ≤q. The resulting
// coefficients are in absolute value ≤7q. If the input is in Montgomery
// form, then the result is in Montgomery form and so (by linearity of the NTT)
// if the input is in regular form, then the result is also in regular form.
// The order of coefficients will be "tangled". These can be put back into
// their proper order by calling Detangle().
func (p *Poly) NTT() {
p.nttGeneric()
}
// Executes an in-place inverse "NTT" on p and multiply by the Montgomery
// factor R.
//
// Requires coefficients to be in "tangled" order, see Tangle().
// Assumes the coefficients are in absolute value ≤q. The resulting
// coefficients are in absolute value ≤q. If the input is in Montgomery
// form, then the result is in Montgomery form and so (by linearity)
// if the input is in regular form, then the result is also in regular form.
func (p *Poly) InvNTT() {
p.invNTTGeneric()
}
// Sets p to the "pointwise" multiplication of a and b.
//
// That is: InvNTT(p) = InvNTT(a) * InvNTT(b). Assumes a and b are in
// Montgomery form. Products between coefficients of a and b must be strictly
// bounded in absolute value by 2¹⁵q. p will be in Montgomery form and
// bounded in absolute value by 2q.
//
// Requires a and b to be in "tangled" order, see Tangle(). p will be in
// tangled order as well.
func (p *Poly) MulHat(a, b *Poly) {
p.mulHatGeneric(a, b)
}
// Puts p into the right form to be used with (among others) InvNTT().
func (p *Poly) Tangle() {
// In the generic implementation there is no advantage to using a
// different order, so we use the standard order everywhere.
}
// Puts p back into standard form.
func (p *Poly) Detangle() {
// In the generic implementation there is no advantage to using a
// different order, so we use the standard order everywhere.
}
// Almost normalizes coefficients.
//
// Ensures each coefficient is in {0, …, q}.
func (p *Poly) BarrettReduce() {
p.barrettReduceGeneric()
}
// Normalizes coefficients.
//
// Ensures each coefficient is in {0, …, q-1}.
func (p *Poly) Normalize() {
p.normalizeGeneric()
}