poulpy/math/src/modulus.rs
math/src/modulus.rsRaw
1pub mod barrett;
2pub mod impl_u64;
3pub mod montgomery;
4pub mod prime;
5
6pub type REDUCEMOD = u8;
7
8pub const NONE: REDUCEMOD = 0;
9pub const ONCE: REDUCEMOD = 1;
10pub const TWICE: REDUCEMOD = 2;
11pub const FOURTIMES: REDUCEMOD = 3;
12pub const BARRETT: REDUCEMOD = 4;
13pub const BARRETTLAZY: REDUCEMOD = 5;
14
15pub trait WordOps<O> {
16 fn log2(self) -> usize;
17 fn reverse_bits_msb(self, n: u32) -> O;
18 fn mask(self) -> O;
19}
20
21impl WordOps<u64> for u64 {
22 #[inline(always)]
23 fn log2(self) -> usize {
24 (u64::BITS - (self - 1).leading_zeros()) as _
25 }
26 #[inline(always)]
27 fn reverse_bits_msb(self, n: u32) -> u64 {
28 self.reverse_bits() >> (usize::BITS - n)
29 }
30 #[inline(always)]
31 fn mask(self) -> u64 {
32 (1 << self.log2()) - 1
33 }
34}
35
36impl WordOps<usize> for usize {
37 #[inline(always)]
38 fn log2(self) -> usize {
39 (usize::BITS - (self - 1).leading_zeros()) as _
40 }
41 #[inline(always)]
42 fn reverse_bits_msb(self, n: u32) -> usize {
43 self.reverse_bits() >> (usize::BITS - n)
44 }
45 #[inline(always)]
46 fn mask(self) -> usize {
47 (1 << self.log2()) - 1
48 }
49}
50
51pub trait ReduceOnce<O> {
52 /// Assigns self-q to self if self >= q in constant time.
53 /// User must ensure that 2q fits in O.
54 fn reduce_once_constant_time_assign(&mut self, q: O);
55 /// Returns self-q if self >= q else self in constant time.
56 /// /// User must ensure that 2q fits in O.
57 fn reduce_once_constant_time(&self, q: O) -> O;
58 /// Assigns self-q to self if self >= q.
59 /// /// User must ensure that 2q fits in O.
60 fn reduce_once_assign(&mut self, q: O);
61 /// Returns self-q if self >= q else self.
62 /// /// User must ensure that 2q fits in O.
63 fn reduce_once(&self, q: O) -> O;
64}
65
66pub trait ScalarOperations<O> {
67 // Applies a parameterized modular reduction.
68 fn sa_reduce_into_sa<const REDUCE: REDUCEMOD>(&self, x: &mut O);
69
70 // Assigns a + b to c.
71 fn sa_add_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &O, b: &O, c: &mut O);
72
73 // Assigns a + b to b.
74 fn sa_add_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
75
76 // Assigns a - b to c.
77 fn sa_sub_sb_into_sc<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
78 &self,
79 a: &O,
80 b: &O,
81 c: &mut O,
82 );
83
84 // Assigns a - b to b.
85 fn sa_sub_sb_into_sb<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
86
87 // Assigns a - b to a.
88 fn sa_sub_sb_into_sa<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, b: &O, a: &mut O);
89
90 // Assigns -a to a.
91 fn sa_neg_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut O);
92
93 // Assigns -a to b.
94 fn sa_neg_into_sb<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
95
96 // Assigns a * 2^64 to a.
97 fn sa_prepare_montgomery_into_sa<const REDUCE: REDUCEMOD>(
98 &self,
99 a: &mut montgomery::Montgomery<O>,
100 );
101
102 // Assigns a * 2^64 to b.
103 fn sa_prepare_montgomery_into_sb<const REDUCE: REDUCEMOD>(
104 &self,
105 a: &O,
106 b: &mut montgomery::Montgomery<O>,
107 );
108
109 // Assigns a * b to c.
110 fn sa_mul_sb_montgomery_into_sc<const REDUCE: REDUCEMOD>(
111 &self,
112 a: &O,
113 b: &montgomery::Montgomery<O>,
114 c: &mut O,
115 );
116
117 // Assigns a * b + c to c.
118 fn sa_mul_sb_montgomery_add_sc_into_sc<const REDUCE1: REDUCEMOD, const REDUCE2: REDUCEMOD>(
119 &self,
120 a: &O,
121 b: &montgomery::Montgomery<O>,
122 c: &mut O,
123 );
124
125 // Assigns a * b to b.
126 fn sa_mul_sb_montgomery_into_sa<const REDUCE: REDUCEMOD>(
127 &self,
128 b: &montgomery::Montgomery<O>,
129 a: &mut O,
130 );
131
132 // Assigns a * b to c.
133 fn sa_mul_sb_barrett_into_sc<const REDUCE: REDUCEMOD>(
134 &self,
135 a: &O,
136 b: &barrett::Barrett<O>,
137 c: &mut O,
138 );
139
140 // Assigns a * b to a.
141 fn sa_mul_sb_barrett_into_sa<const REDUCE: REDUCEMOD>(
142 &self,
143 b: &barrett::Barrett<O>,
144 a: &mut O,
145 );
146
147 // Assigns (a + q - b) * c to d.
148 fn sa_sub_sb_mul_sc_barrett_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
149 &self,
150 a: &O,
151 b: &O,
152 c: &barrett::Barrett<O>,
153 d: &mut O,
154 );
155
156 // Assigns (a + q - b) * c to b.
157 fn sa_sub_sb_mul_sc_barrett_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
158 &self,
159 a: &u64,
160 c: &barrett::Barrett<u64>,
161 b: &mut u64,
162 );
163
164 // Assigns (a + b) * c to a.
165 fn sa_add_sb_mul_sc_barrett_into_sa<const REDUCE: REDUCEMOD>(
166 &self,
167 b: &u64,
168 c: &barrett::Barrett<u64>,
169 a: &mut u64,
170 );
171
172 // Assigns (a + b) * c to d.
173 fn sa_add_sb_mul_sc_barrett_into_sd<const REDUCE: REDUCEMOD>(
174 &self,
175 a: &u64,
176 b: &u64,
177 c: &barrett::Barrett<u64>,
178 d: &mut u64,
179 );
180
181 // Assigns (a - b + c) * d to e.
182 fn sb_sub_sa_add_sc_mul_sd_barrett_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
183 &self,
184 a: &u64,
185 b: &u64,
186 c: &u64,
187 d: &barrett::Barrett<u64>,
188 e: &mut u64,
189 );
190
191 fn sb_sub_sa_add_sc_mul_sd_barrett_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
192 &self,
193 b: &u64,
194 c: &u64,
195 d: &barrett::Barrett<u64>,
196 a: &mut u64,
197 );
198
199 fn sa_rsh_sb_mask_sc_into_sa(&self, c: &usize, b: &u64, a: &mut u64);
200
201 fn sa_rsh_sb_mask_sc_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64);
202
203 fn sa_rsh_sb_mask_sc_add_sd_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64);
204
205 fn sa_signed_digit_into_sb<const CARRYOVERWRITE: bool, const BALANCED: bool>(
206 &self,
207 a: &u64,
208 base: &u64,
209 shift: &usize,
210 mask: &u64,
211 carry: &mut u64,
212 b: &mut u64,
213 );
214}
215
216pub trait VectorOperations<O> {
217 // Applies a parameterized modular reduction.
218 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, x: &mut [O]);
219
220 // ADD
221 // vec(c) <- vec(a) + vec(b).
222 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
223 &self,
224 va: &[O],
225 vb: &[O],
226 vc: &mut [O],
227 );
228
229 // vec(b) <- vec(a) + vec(b).
230 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &[O], b: &mut [O]);
231
232 // vec(c) <- vec(a) + scalar(b).
233 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
234 &self,
235 a: &[O],
236 b: &O,
237 c: &mut [O],
238 );
239
240 // vec(b) <- vec(b) + scalar(a).
241 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut [O]);
242
243 // vec(b) <- vec(a) - vec(b).
244 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
245 &self,
246 a: &[O],
247 b: &mut [O],
248 );
249
250 // vec(a) <- vec(a) - vec(b).
251 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
252 &self,
253 b: &[O],
254 a: &mut [O],
255 );
256
257 // vec(c) <- vec(a) - vec(b).
258 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
259 &self,
260 a: &[O],
261 b: &[O],
262 c: &mut [O],
263 );
264
265 // vec(a) <- -vec(a).
266 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
267 &self,
268 a: &mut [O],
269 );
270
271 // vec(b) <- -vec(a).
272 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
273 &self,
274 a: &[O],
275 b: &mut [O],
276 );
277
278 // vec(b) <- vec(a)
279 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
280 &self,
281 a: &[O],
282 b: &mut [montgomery::Montgomery<O>],
283 );
284
285 // vec(a) <- vec(a).
286 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
287 &self,
288 a: &mut [montgomery::Montgomery<O>],
289 );
290
291 // vec(c) <- vec(a) * vec(b).
292 fn va_mul_vb_montgomery_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
293 &self,
294 a: &[O],
295 b: &[montgomery::Montgomery<O>],
296 c: &mut [O],
297 );
298
299 // vec(c) <- vec(a) * vec(b) + vec(c).
300 fn va_mul_vb_montgomery_add_vc_into_vc<
301 const CHUNK: usize,
302 const REDUCE1: REDUCEMOD,
303 const REDUCE2: REDUCEMOD,
304 >(
305 &self,
306 a: &[O],
307 b: &[montgomery::Montgomery<O>],
308 c: &mut [O],
309 );
310
311 // vec(a) <- vec(a) * vec(b).
312 fn va_mul_vb_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
313 &self,
314 b: &[montgomery::Montgomery<O>],
315 a: &mut [O],
316 );
317
318 // vec(b) <- vec(a) * scalar(b).
319 fn va_mul_sb_barrett_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
320 &self,
321 b: &barrett::Barrett<u64>,
322 a: &mut [u64],
323 );
324
325 // vec(c) <- vec(a) * scalar(b).
326 fn va_mul_sb_barrett_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
327 &self,
328 a: &[u64],
329 b: &barrett::Barrett<u64>,
330 c: &mut [u64],
331 );
332
333 // vec(d) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
334 fn va_sub_vb_mul_sc_barrett_into_vd<
335 const CHUNK: usize,
336 const VBRANGE: u8,
337 const REDUCE: REDUCEMOD,
338 >(
339 &self,
340 a: &[u64],
341 b: &[u64],
342 c: &barrett::Barrett<u64>,
343 d: &mut [u64],
344 );
345
346 // vec(b) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
347 fn va_sub_vb_mul_sc_barrett_into_vb<
348 const CHUNK: usize,
349 const VBRANGE: u8,
350 const REDUCE: REDUCEMOD,
351 >(
352 &self,
353 a: &[u64],
354 c: &barrett::Barrett<u64>,
355 b: &mut [u64],
356 );
357
358 // vec(c) <- (vec(a) + scalar(b)) * scalar(c).
359 fn va_add_sb_mul_sc_barrett_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
360 &self,
361 va: &[u64],
362 sb: &u64,
363 sc: &barrett::Barrett<u64>,
364 vd: &mut [u64],
365 );
366
367 // vec(a) <- (vec(a) + scalar(b)) * scalar(c).
368 fn va_add_sb_mul_sc_barrett_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
369 &self,
370 sb: &u64,
371 sc: &barrett::Barrett<u64>,
372 va: &mut [u64],
373 );
374
375 // vec(e) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
376 fn vb_sub_va_add_sc_mul_sd_barrett_into_ve<
377 const CHUNK: usize,
378 const VBRANGE: u8,
379 const REDUCE: REDUCEMOD,
380 >(
381 &self,
382 va: &[u64],
383 vb: &[u64],
384 sc: &u64,
385 sd: &barrett::Barrett<u64>,
386 ve: &mut [u64],
387 );
388
389 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
390 fn vb_sub_va_add_sc_mul_sd_barrett_into_va<
391 const CHUNK: usize,
392 const VBRANGE: u8,
393 const REDUCE: REDUCEMOD,
394 >(
395 &self,
396 vb: &[u64],
397 sc: &u64,
398 sd: &barrett::Barrett<u64>,
399 va: &mut [u64],
400 );
401
402 // vec(a) <- (vec(a)>>scalar(b)) & scalar(c).
403 fn va_rsh_sb_mask_sc_into_va<const CHUNK: usize>(&self, sb: &usize, sc: &u64, va: &mut [u64]);
404
405 // vec(d) <- (vec(a)>>scalar(b)) & scalar(c).
406 fn va_rsh_sb_mask_sc_into_vd<const CHUNK: usize>(
407 &self,
408 va: &[u64],
409 sb: &usize,
410 sc: &u64,
411 vd: &mut [u64],
412 );
413
414 // vec(d) <- vec(d) + (vec(a)>>scalar(b)) & scalar(c).
415 fn va_rsh_sb_mask_sc_add_vd_into_vd<const CHUNK: usize>(
416 &self,
417 va: &[u64],
418 sb: &usize,
419 sc: &u64,
420 vd: &mut [u64],
421 );
422
423 // vec(c) <- i-th unsigned digit base 2^{sb} of vec(a).
424 // vec(c) is ensured to be in the range [0, 2^{sb}-1[ with E[vec(c)] = 2^{sb}-1.
425 fn va_ith_digit_unsigned_base_sb_into_vc<const CHUNK: usize>(
426 &self,
427 i: usize,
428 va: &[u64],
429 sb: &usize,
430 vc: &mut [u64],
431 );
432
433 // vec(c) <- i-th signed digit base 2^{w} of vec(a).
434 // Reads the carry of the i-1-th iteration and write the carry on the i-th iteration on carry.
435 // if i > 0, carry of the i-1th iteration must be provided.
436 // if BALANCED: vec(c) is ensured to be [-2^{sb-1}, 2^{sb-1}[ with E[vec(c)] = 0, else E[vec(c)] = -0.5
437 fn va_ith_digit_signed_base_sb_into_vc<const CHUNK: usize, const BALANCED: bool>(
438 &self,
439 i: usize,
440 va: &[u64],
441 sb: &usize,
442 carry: &mut [u64],
443 vc: &mut [u64],
444 );
445}