ring.mx raw
1 // Package ring implements polynomial arithmetic over R_q = Z_q[x]/(x^n + 1).
2 //
3 // The ring R_q = Z_q[x]/(x^n + 1) is a quotient of the polynomial ring Z_q[x]
4 // by the cyclotomic polynomial Phi_{2n}(x) = x^n + 1. When n is a power of 2
5 // and q = 1 (mod 2n), this ring supports a negacyclic NTT, enabling O(n log n)
6 // polynomial multiplication.
7 package ring
8
9 type Params struct {
10 N int32
11 Q uint32
12 RootOfUnity uint32
13 MontR uint64
14 QInv uint64
15 }
16
17 func Falcon512() (p Params) {
18 return Params{
19 N: 512,
20 Q: 12289,
21 RootOfUnity: 49,
22 MontR: 1 << 16,
23 QInv: qinv(12289, 16),
24 }
25 }
26
27 func NewHope256() (p Params) {
28 return Params{
29 N: 256,
30 Q: 7681,
31 RootOfUnity: 4055,
32 MontR: 1 << 16,
33 QInv: qinv(7681, 16),
34 }
35 }
36
37 func HE64() (p Params) {
38 return Params{
39 N: 64,
40 Q: 10000769,
41 RootOfUnity: 6028202,
42 MontR: 1 << 32,
43 QInv: qinv(10000769, 32),
44 }
45 }
46
47 func Falcon1024() (p Params) {
48 return Params{
49 N: 1024,
50 Q: 12289,
51 RootOfUnity: 1945,
52 MontR: 1 << 16,
53 QInv: qinv(12289, 16),
54 }
55 }
56
57 func qinv(q uint32, k int32) (result uint64) {
58 inv := uint64(1)
59 for i := int32(1); i < k; i++ {
60 inv = inv * (2 - inv*uint64(q))
61 }
62 mask := (uint64(1) << uint32(k)) - 1
63 return (-inv) & mask
64 }
65
66 type Poly struct {
67 Coeffs []uint32
68 params Params
69 isNTT bool
70 }
71
72 func New(p Params) (poly *Poly) {
73 return &Poly{
74 Coeffs: []uint32{:p.N},
75 params: p,
76 }
77 }
78
79 func NewFromCoeffs(p Params, coeffs []uint32) (poly *Poly) {
80 poly = New(p)
81 n := int32(len(coeffs))
82 if n > p.N {
83 n = p.N
84 }
85 for i := int32(0); i < n; i++ {
86 poly.Coeffs[i] = coeffs[i] % p.Q
87 }
88 return poly
89 }
90
91 func (a *Poly) Clone() (b *Poly) {
92 b = &Poly{
93 Coeffs: []uint32{:int32(len(a.Coeffs))},
94 params: a.params,
95 isNTT: a.isNTT,
96 }
97 copy(b.Coeffs, a.Coeffs)
98 return b
99 }
100
101 func (a *Poly) RingParams() (p Params) { return a.params }
102 func (a *Poly) IsNTT() (v bool) { return a.isNTT }
103
104 func addMod(a, b, q uint32) (result uint32) {
105 sum := a + b
106 if sum >= q {
107 sum -= q
108 }
109 return sum
110 }
111
112 func subMod(a, b, q uint32) (result uint32) {
113 if a >= b {
114 return a - b
115 }
116 return q - b + a
117 }
118
119 func mulMod(a, b, q uint32) (result uint32) {
120 return uint32((uint64(a) * uint64(b)) % uint64(q))
121 }
122
123 func Add(a, b *Poly) (c *Poly) {
124 c = New(a.params)
125 c.isNTT = a.isNTT
126 q := a.params.Q
127 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
128 c.Coeffs[i] = addMod(a.Coeffs[i], b.Coeffs[i], q)
129 }
130 return c
131 }
132
133 func Sub(a, b *Poly) (c *Poly) {
134 c = New(a.params)
135 c.isNTT = a.isNTT
136 q := a.params.Q
137 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
138 c.Coeffs[i] = subMod(a.Coeffs[i], b.Coeffs[i], q)
139 }
140 return c
141 }
142
143 func Neg(a *Poly) (c *Poly) {
144 c = New(a.params)
145 c.isNTT = a.isNTT
146 q := a.params.Q
147 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
148 if a.Coeffs[i] != 0 {
149 c.Coeffs[i] = q - a.Coeffs[i]
150 }
151 }
152 return c
153 }
154
155 func MulPointwise(a, b *Poly) (c *Poly) {
156 c = New(a.params)
157 c.isNTT = true
158 q := a.params.Q
159 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
160 c.Coeffs[i] = mulMod(a.Coeffs[i], b.Coeffs[i], q)
161 }
162 return c
163 }
164
165 func MulAdd(c, a, b *Poly) {
166 q := a.params.Q
167 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
168 c.Coeffs[i] = addMod(c.Coeffs[i], mulMod(a.Coeffs[i], b.Coeffs[i], q), q)
169 }
170 }
171
172 func ScalarMul(a *Poly, s uint32) (c *Poly) {
173 c = New(a.params)
174 c.isNTT = a.isNTT
175 q := a.params.Q
176 s = s % q
177 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
178 c.Coeffs[i] = mulMod(a.Coeffs[i], s, q)
179 }
180 return c
181 }
182
183 func Equal(a, b *Poly) (result bool) {
184 if int32(len(a.Coeffs)) != int32(len(b.Coeffs)) {
185 return false
186 }
187 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
188 if a.Coeffs[i] != b.Coeffs[i] {
189 return false
190 }
191 }
192 return true
193 }
194
195 // LE byte helpers (replacing encoding/binary).
196 func leU16(b []byte) (v uint16) {
197 return uint16(b[0]) | uint16(b[1])<<8
198 }
199
200 func leU32(b []byte) (v uint32) {
201 return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
202 }
203
204 func leU64(b []byte) (v uint64) {
205 return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
206 uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
207 }
208
209 func putLeU64(b []byte, v uint64) {
210 b[0] = byte(v)
211 b[1] = byte(v >> 8)
212 b[2] = byte(v >> 16)
213 b[3] = byte(v >> 24)
214 b[4] = byte(v >> 32)
215 b[5] = byte(v >> 40)
216 b[6] = byte(v >> 48)
217 b[7] = byte(v >> 56)
218 }
219
220 func putLeU16(b []byte, v uint16) {
221 b[0] = byte(v)
222 b[1] = byte(v >> 8)
223 }
224
225 func Serialize(a *Poly) (out []byte) {
226 q := a.params.Q
227 bits := int32(0)
228 for v := q - 1; v > 0; v >>= 1 {
229 bits++
230 }
231
232 totalBits := bits * int32(len(a.Coeffs))
233 out = []byte{:(totalBits + 7) / 8}
234
235 bitPos := int32(0)
236 for i := int32(0); i < int32(len(a.Coeffs)); i++ {
237 c := a.Coeffs[i]
238 for b := int32(0); b < bits; b++ {
239 if c&(1<<uint32(b)) != 0 {
240 out[bitPos/8] |= 1 << uint32(bitPos%8)
241 }
242 bitPos++
243 }
244 }
245 return out
246 }
247
248 func Deserialize(p Params, data []byte) (poly *Poly) {
249 q := p.Q
250 bits := int32(0)
251 for v := q - 1; v > 0; v >>= 1 {
252 bits++
253 }
254
255 poly = New(p)
256 bitPos := int32(0)
257 for i := int32(0); i < int32(len(poly.Coeffs)); i++ {
258 var v uint32
259 for b := int32(0); b < bits; b++ {
260 if bitPos/8 < int32(len(data)) && data[bitPos/8]&(1<<uint32(bitPos%8)) != 0 {
261 v |= 1 << uint32(b)
262 }
263 bitPos++
264 }
265 if v >= q {
266 v = q - 1
267 }
268 poly.Coeffs[i] = v
269 }
270 return poly
271 }
272