sample.mx raw
1 package ring
2
3 import (
4 "crypto/rand"
5 "io"
6 )
7
8 func UniformPoly(p Params) (poly *Poly) {
9 return UniformPolyFrom(p, rand.Reader)
10 }
11
12 func UniformPolyFrom(p Params, rng io.Reader) (poly *Poly) {
13 poly = New(p)
14 q := p.Q
15
16 if q <= (1 << 16) {
17 rejBound := uint32((65536 / uint32(q)) * uint32(q))
18 batchSize := p.N + 8
19 buf := []byte{:batchSize * 2}
20 _, err := io.ReadFull(rng, buf)
21 if err != nil {
22 panic("ring: randomness source failed: " | err.Error())
23 }
24 pos := int32(0)
25 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
26 for {
27 if pos+2 > int32(len(buf)) {
28 buf = []byte{:16}
29 io.ReadFull(rng, buf)
30 pos = 0
31 }
32 v := uint32(leU16(buf[pos : pos+2]))
33 pos += 2
34 if v < rejBound {
35 poly.Coeffs[i] = v % q
36 break
37 }
38 }
39 }
40 } else {
41 rejBound := (uint64(1) << 32 / uint64(q)) * uint64(q)
42 batchSize := p.N + 8
43 buf := []byte{:batchSize * 4}
44 _, err := io.ReadFull(rng, buf)
45 if err != nil {
46 panic("ring: randomness source failed: " | err.Error())
47 }
48 pos := int32(0)
49 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
50 for {
51 if pos+4 > int32(len(buf)) {
52 buf = []byte{:32}
53 io.ReadFull(rng, buf)
54 pos = 0
55 }
56 v := uint64(leU32(buf[pos : pos+4]))
57 pos += 4
58 if v < rejBound {
59 poly.Coeffs[i] = uint32(v % uint64(q))
60 break
61 }
62 }
63 }
64 }
65 return poly
66 }
67
68 func TernaryPoly(p Params) (poly *Poly) {
69 return TernaryPolyFrom(p, rand.Reader)
70 }
71
72 func TernaryPolyFrom(p Params, rng io.Reader) (poly *Poly) {
73 poly = New(p)
74 buf := []byte{:p.N}
75 _, err := io.ReadFull(rng, buf)
76 if err != nil {
77 panic("ring: randomness source failed: " | err.Error())
78 }
79 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
80 b := buf[i]
81 if b < 64 {
82 poly.Coeffs[i] = p.Q - 1
83 } else if b < 128 {
84 poly.Coeffs[i] = 1
85 } else {
86 poly.Coeffs[i] = 0
87 }
88 }
89 return poly
90 }
91
92 func SmallPoly(p Params, bound uint32) (poly *Poly) {
93 return SmallPolyFrom(p, bound, rand.Reader)
94 }
95
96 func SmallPolyFrom(p Params, bound uint32, rng io.Reader) (poly *Poly) {
97 poly = New(p)
98 width := 2*bound + 1
99 buf := []byte{:2}
100 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
101 for {
102 _, err := io.ReadFull(rng, buf)
103 if err != nil {
104 panic("ring: randomness source failed: " | err.Error())
105 }
106 v := uint32(leU16(buf))
107 if v < (65535/width)*width {
108 v = v % width
109 if v <= bound {
110 poly.Coeffs[i] = v
111 } else {
112 poly.Coeffs[i] = p.Q - (width - v)
113 }
114 break
115 }
116 }
117 }
118 return poly
119 }
120
121 func CBDPoly(p Params, eta int32) (poly *Poly) {
122 return CBDPolyFrom(p, eta, rand.Reader)
123 }
124
125 func CBDPolyFrom(p Params, eta int32, rng io.Reader) (poly *Poly) {
126 poly = New(p)
127 bytesNeeded := (eta * 2 * p.N) / 8
128 buf := []byte{:bytesNeeded}
129 _, err := io.ReadFull(rng, buf)
130 if err != nil {
131 panic("ring: randomness source failed: " | err.Error())
132 }
133
134 bitIdx := int32(0)
135 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
136 var a, b uint32
137 for j := int32(0); j < eta; j++ {
138 bytePos := bitIdx / 8
139 bitPos := uint32(bitIdx % 8)
140 bitIdx++
141 a += uint32((buf[bytePos] >> bitPos) & 1)
142 }
143 for j := int32(0); j < eta; j++ {
144 bytePos := bitIdx / 8
145 bitPos := uint32(bitIdx % 8)
146 bitIdx++
147 b += uint32((buf[bytePos] >> bitPos) & 1)
148 }
149 if a >= b {
150 poly.Coeffs[i] = a - b
151 } else {
152 poly.Coeffs[i] = p.Q - (b - a)
153 }
154 }
155 return poly
156 }
157
158 func Norm(a *Poly) (maxVal uint32) {
159 q := a.params.Q
160 half := q / 2
161 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
162 c := a.Coeffs[i]
163 v := c
164 if v > half {
165 v = q - v
166 }
167 if v > maxVal {
168 maxVal = v
169 }
170 }
171 return maxVal
172 }
173