poulpy/math/src/modulus/impl_u64/operations.rs
math/src/modulus/impl_u64/operations.rsRaw
1use crate::modulus::barrett::Barrett;
2use crate::modulus::montgomery::Montgomery;
3use crate::modulus::prime::Prime;
4use crate::modulus::{ScalarOperations, VectorOperations};
5use crate::modulus::{NONE, REDUCEMOD};
6use crate::{
7 apply_ssv, apply_sv, apply_svv, apply_v, apply_vsssvv, apply_vssv, apply_vsv, apply_vv,
8 apply_vvssv, apply_vvsv, apply_vvv,
9};
10use itertools::izip;
11
12impl ScalarOperations<u64> for Prime<u64> {
13 /// Applies a modular reduction on x based on REDUCE:
14 /// - LAZY: no modular reduction.
15 /// - ONCE: subtracts q if x >= q.
16 /// - TWO: subtracts 2q if x >= 2q.
17 /// - FOUR: subtracts 4q if x >= 4q.
18 /// - BARRETT: maps x to x mod q using Barrett reduction.
19 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
20 #[inline(always)]
21 fn sa_reduce_into_sa<const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
22 self.montgomery.reduce_assign::<REDUCE>(a);
23 }
24
25 #[inline(always)]
26 fn sa_add_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &u64, c: &mut u64) {
27 *c = a.wrapping_add(*b);
28 self.sa_reduce_into_sa::<REDUCE>(c);
29 }
30
31 #[inline(always)]
32 fn sa_add_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
33 *b = a.wrapping_add(*b);
34 self.sa_reduce_into_sa::<REDUCE>(b);
35 }
36
37 #[inline(always)]
38 fn sa_sub_sb_into_sc<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
39 &self,
40 a: &u64,
41 b: &u64,
42 c: &mut u64,
43 ) {
44 match SBRANGE {
45 1 => *c = *a + self.q - *b,
46 2 => *c = *a + self.two_q - *b,
47 4 => *c = *a + self.four_q - *b,
48 _ => unreachable!("invalid SBRANGE argument"),
49 }
50 self.sa_reduce_into_sa::<REDUCE>(c)
51 }
52
53 #[inline(always)]
54 fn sa_sub_sb_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut u64) {
55 match SBRANGE {
56 1 => *a = *a + self.q - *b,
57 2 => *a = *a + self.two_q - *b,
58 4 => *a = *a + self.four_q - *b,
59 _ => unreachable!("invalid SBRANGE argument"),
60 }
61 self.sa_reduce_into_sa::<REDUCE>(a)
62 }
63
64 #[inline(always)]
65 fn sa_sub_sb_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
66 match SBRANGE {
67 1 => *b = *a + self.q - *b,
68 2 => *b = *a + self.two_q - *b,
69 4 => *b = *a + self.four_q - *b,
70 _ => unreachable!("invalid SBRANGE argument"),
71 }
72 self.sa_reduce_into_sa::<REDUCE>(b)
73 }
74
75 #[inline(always)]
76 fn sa_neg_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
77 match SBRANGE {
78 1 => *a = self.q - *a,
79 2 => *a = self.two_q - *a,
80 4 => *a = self.four_q - *a,
81 _ => unreachable!("invalid SBRANGE argument"),
82 }
83 self.sa_reduce_into_sa::<REDUCE>(a)
84 }
85
86 #[inline(always)]
87 fn sa_neg_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
88 match SBRANGE {
89 1 => *b = self.q - *a,
90 2 => *b = self.two_q - *a,
91 4 => *b = self.four_q - *a,
92 _ => unreachable!("invalid SBRANGE argument"),
93 }
94 self.sa_reduce_into_sa::<REDUCE>(b)
95 }
96
97 #[inline(always)]
98 fn sa_prepare_montgomery_into_sa<const REDUCE: REDUCEMOD>(&self, a: &mut Montgomery<u64>) {
99 *a = self.montgomery.prepare::<REDUCE>(*a);
100 }
101
102 #[inline(always)]
103 fn sa_prepare_montgomery_into_sb<const REDUCE: REDUCEMOD>(
104 &self,
105 a: &u64,
106 b: &mut Montgomery<u64>,
107 ) {
108 self.montgomery.prepare_assign::<REDUCE>(*a, b);
109 }
110
111 #[inline(always)]
112 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
113 &self,
114 a: &Montgomery<u64>,
115 b: &u64,
116 c: &mut u64,
117 ) {
118 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
119 }
120
121 #[inline(always)]
122 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Montgomery<u64>, b: &mut u64) {
123 self.montgomery.mul_external_assign::<REDUCE>(*a, b);
124 }
125
126 #[inline(always)]
127 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
128 &self,
129 a: &Barrett<u64>,
130 b: &u64,
131 c: &mut u64,
132 ) {
133 *c = self.barrett.mul_external::<REDUCE>(*a, *b);
134 }
135
136 #[inline(always)]
137 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Barrett<u64>, b: &mut u64) {
138 self.barrett.mul_external_assign::<REDUCE>(*a, b);
139 }
140
141 #[inline(always)]
142 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
143 &self,
144 a: &u64,
145 b: &u64,
146 c: &Barrett<u64>,
147 d: &mut u64,
148 ) {
149 match VBRANGE {
150 1 => *d = a + self.q - b,
151 2 => *d = a + self.two_q - b,
152 4 => *d = a + self.four_q - b,
153 _ => unreachable!("invalid SBRANGE argument"),
154 }
155 self.barrett.mul_external_assign::<REDUCE>(*c, d);
156 }
157
158 #[inline(always)]
159 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
160 &self,
161 a: &u64,
162 c: &Barrett<u64>,
163 b: &mut u64,
164 ) {
165 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(a, b);
166 self.barrett.mul_external_assign::<REDUCE>(*c, b);
167 }
168
169 #[inline(always)]
170 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
171 &self,
172 a: &u64,
173 b: &u64,
174 c: &Barrett<u64>,
175 d: &mut u64,
176 ) {
177 *d = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
178 }
179
180 #[inline(always)]
181 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
182 &self,
183 b: &u64,
184 c: &Barrett<u64>,
185 a: &mut u64,
186 ) {
187 *a = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
188 }
189
190 #[inline(always)]
191 fn sb_sub_sa_add_sc_mul_sd_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
192 &self,
193 a: &u64,
194 b: &u64,
195 c: &u64,
196 d: &Barrett<u64>,
197 e: &mut u64,
198 ) {
199 self.sa_sub_sb_into_sc::<SBRANGE, NONE>(&(b + c), a, e);
200 self.barrett.mul_external_assign::<REDUCE>(*d, e);
201 }
202
203 #[inline(always)]
204 fn sb_sub_sa_add_sc_mul_sd_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
205 &self,
206 b: &u64,
207 c: &u64,
208 d: &Barrett<u64>,
209 a: &mut u64,
210 ) {
211 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(&(b + c), a);
212 self.barrett.mul_external_assign::<REDUCE>(*d, a);
213 }
214
215 #[inline(always)]
216 fn sa_rsh_sb_mask_sc_into_sa(&self, b: &usize, c: &u64, a: &mut u64) {
217 *a = (*a >> b) & c
218 }
219
220 #[inline(always)]
221 fn sa_rsh_sb_mask_sc_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64) {
222 *d = (*a >> b) & c
223 }
224
225 #[inline(always)]
226 fn sa_rsh_sb_mask_sc_add_sd_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64) {
227 *d += (*a >> b) & c
228 }
229
230 #[inline(always)]
231 fn sa_signed_digit_into_sb<const CARRYOVERWRITE: bool, const BALANCED: bool>(
232 &self,
233 a: &u64,
234 base: &u64,
235 shift: &usize,
236 mask: &u64,
237 carry: &mut u64,
238 b: &mut u64,
239 ) {
240 if CARRYOVERWRITE {
241 self.sa_rsh_sb_mask_sc_into_sd(a, shift, mask, carry);
242 } else {
243 self.sa_rsh_sb_mask_sc_add_sd_into_sd(a, shift, mask, carry);
244 }
245
246 let c: u64 = if BALANCED && *carry == base >> 1 {
247 a & 1
248 } else {
249 ((*carry | (*carry << 1)) >> shift) & 1
250 };
251
252 *b = *carry + (self.q - base) * c;
253 *carry = c;
254 }
255}
256
257impl VectorOperations<u64> for Prime<u64> {
258 /// Applies a modular reduction on x based on REDUCE:
259 /// - LAZY: no modular reduction.
260 /// - ONCE: subtracts q if x >= q.
261 /// - TWO: subtracts 2q if x >= 2q.
262 /// - FOUR: subtracts 4q if x >= 4q.
263 /// - BARRETT: maps x to x mod q using Barrett reduction.
264 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
265 #[inline(always)]
266 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
267 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
268 }
269
270 #[inline(always)]
271 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
272 &self,
273 a: &[u64],
274 b: &[u64],
275 c: &mut [u64],
276 ) {
277 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
278 }
279
280 #[inline(always)]
281 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
282 &self,
283 a: &[u64],
284 b: &mut [u64],
285 ) {
286 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
287 }
288
289 #[inline(always)]
290 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
291 &self,
292 b: &u64,
293 a: &mut [u64],
294 ) {
295 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
296 }
297
298 #[inline(always)]
299 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
300 &self,
301 a: &[u64],
302 b: &u64,
303 c: &mut [u64],
304 ) {
305 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
306 }
307
308 #[inline(always)]
309 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
310 &self,
311 a: &[u64],
312 b: &[u64],
313 c: &mut [u64],
314 ) {
315 apply_vvv!(
316 self,
317 Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>,
318 a,
319 b,
320 c,
321 CHUNK
322 );
323 }
324
325 #[inline(always)]
326 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
327 &self,
328 b: &[u64],
329 a: &mut [u64],
330 ) {
331 apply_vv!(
332 self,
333 Self::sa_sub_sb_into_sa::<VBRANGE, REDUCE>,
334 b,
335 a,
336 CHUNK
337 );
338 }
339
340 #[inline(always)]
341 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
342 &self,
343 a: &[u64],
344 b: &mut [u64],
345 ) {
346 apply_vv!(
347 self,
348 Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>,
349 a,
350 b,
351 CHUNK
352 );
353 }
354
355 #[inline(always)]
356 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
357 &self,
358 a: &mut [u64],
359 ) {
360 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
361 }
362
363 #[inline(always)]
364 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
365 &self,
366 a: &[u64],
367 b: &mut [u64],
368 ) {
369 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
370 }
371
372 #[inline(always)]
373 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
374 &self,
375 a: &[u64],
376 b: &mut [Montgomery<u64>],
377 ) {
378 apply_vv!(
379 self,
380 Self::sa_prepare_montgomery_into_sb::<REDUCE>,
381 a,
382 b,
383 CHUNK
384 );
385 }
386
387 #[inline(always)]
388 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
389 &self,
390 a: &mut [Montgomery<u64>],
391 ) {
392 apply_v!(
393 self,
394 Self::sa_prepare_montgomery_into_sa::<REDUCE>,
395 a,
396 CHUNK
397 );
398 }
399
400 #[inline(always)]
401 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
402 &self,
403 a: &[Montgomery<u64>],
404 b: &[u64],
405 c: &mut [u64],
406 ) {
407 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
408 }
409
410 #[inline(always)]
411 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
412 &self,
413 a: &[Montgomery<u64>],
414 b: &mut [u64],
415 ) {
416 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
417 }
418
419 #[inline(always)]
420 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
421 &self,
422 a: &Barrett<u64>,
423 b: &[u64],
424 c: &mut [u64],
425 ) {
426 apply_svv!(
427 self,
428 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
429 a,
430 b,
431 c,
432 CHUNK
433 );
434 }
435
436 #[inline(always)]
437 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
438 &self,
439 a: &Barrett<u64>,
440 b: &mut [u64],
441 ) {
442 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
443 }
444
445 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
446 &self,
447 a: &[u64],
448 b: &[u64],
449 c: &Barrett<u64>,
450 d: &mut [u64],
451 ) {
452 apply_vvsv!(
453 self,
454 Self::sa_sub_sb_mul_sc_into_sd::<VBRANGE, REDUCE>,
455 a,
456 b,
457 c,
458 d,
459 CHUNK
460 );
461 }
462
463 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
464 &self,
465 a: &[u64],
466 b: &Barrett<u64>,
467 c: &mut [u64],
468 ) {
469 apply_vsv!(
470 self,
471 Self::sa_sub_sb_mul_sc_into_sb::<VBRANGE, REDUCE>,
472 a,
473 b,
474 c,
475 CHUNK
476 );
477 }
478
479 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
480 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
481 &self,
482 b: &u64,
483 c: &Barrett<u64>,
484 a: &mut [u64],
485 ) {
486 apply_ssv!(
487 self,
488 Self::sa_add_sb_mul_sc_into_sa::<REDUCE>,
489 b,
490 c,
491 a,
492 CHUNK
493 );
494 }
495
496 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
497 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
498 &self,
499 a: &[u64],
500 b: &u64,
501 c: &Barrett<u64>,
502 d: &mut [u64],
503 ) {
504 apply_vssv!(
505 self,
506 Self::sa_add_sb_mul_sc_into_sd::<REDUCE>,
507 a,
508 b,
509 c,
510 d,
511 CHUNK
512 );
513 }
514
515 // vec(e) <- (vec(a) - vec(b) + scalar(c)) * scalar(e).
516 fn vb_sub_va_add_sc_mul_sd_into_ve<
517 const CHUNK: usize,
518 const VBRANGE: u8,
519 const REDUCE: REDUCEMOD,
520 >(
521 &self,
522 va: &[u64],
523 vb: &[u64],
524 sc: &u64,
525 sd: &Barrett<u64>,
526 ve: &mut [u64],
527 ) {
528 apply_vvssv!(
529 self,
530 Self::sb_sub_sa_add_sc_mul_sd_into_se::<VBRANGE, REDUCE>,
531 va,
532 vb,
533 sc,
534 sd,
535 ve,
536 CHUNK
537 );
538 }
539
540 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
541 fn vb_sub_va_add_sc_mul_sd_into_va<
542 const CHUNK: usize,
543 const VBRANGE: u8,
544 const REDUCE: REDUCEMOD,
545 >(
546 &self,
547 vb: &[u64],
548 sc: &u64,
549 sd: &Barrett<u64>,
550 va: &mut [u64],
551 ) {
552 apply_vssv!(
553 self,
554 Self::sb_sub_sa_add_sc_mul_sd_into_sa::<VBRANGE, REDUCE>,
555 vb,
556 sc,
557 sd,
558 va,
559 CHUNK
560 );
561 }
562
563 // vec(a) <- (vec(a)>>scalar(b)) & scalar(c).
564 fn va_rsh_sb_mask_sc_into_va<const CHUNK: usize>(&self, sb: &usize, sc: &u64, va: &mut [u64]) {
565 apply_ssv!(self, Self::sa_rsh_sb_mask_sc_into_sa, sb, sc, va, CHUNK);
566 }
567
568 // vec(d) <- (vec(a)>>scalar(b)) & scalar(c).
569 fn va_rsh_sb_mask_sc_into_vd<const CHUNK: usize>(
570 &self,
571 va: &[u64],
572 sb: &usize,
573 sc: &u64,
574 vd: &mut [u64],
575 ) {
576 apply_vssv!(self, Self::sa_rsh_sb_mask_sc_into_sd, va, sb, sc, vd, CHUNK);
577 }
578
579 // vec(d) <- vec(d) + (vec(a)>>scalar(b)) & scalar(c).
580 fn va_rsh_sb_mask_sc_add_vd_into_vd<const CHUNK: usize>(
581 &self,
582 va: &[u64],
583 sb: &usize,
584 sc: &u64,
585 vd: &mut [u64],
586 ) {
587 apply_vssv!(
588 self,
589 Self::sa_rsh_sb_mask_sc_add_sd_into_sd,
590 va,
591 sb,
592 sc,
593 vd,
594 CHUNK
595 );
596 }
597
598 // vec(c) <- i-th unsigned digit base 2^{sb} of vec(a).
599 // vec(c) is ensured to be in the range [0, 2^{sb}-1[ with E[vec(c)] = 2^{sb}-1.
600 fn va_ith_digit_unsigned_base_sb_into_vc<const CHUNK: usize>(
601 &self,
602 i: usize,
603 va: &[u64],
604 sb: &usize,
605 vc: &mut [u64],
606 ) {
607 self.va_rsh_sb_mask_sc_into_vd::<CHUNK>(va, &(i * sb), &((1 << sb) - 1), vc);
608 }
609
610 // vec(c) <- i-th signed digit base 2^{w} of vec(a).
611 // Reads the carry of the i-1-th iteration and write the carry on the i-th iteration on carry.
612 // if i > 0, carry of the i-1th iteration must be provided.
613 // 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
614 fn va_ith_digit_signed_base_sb_into_vc<const CHUNK: usize, const BALANCED: bool>(
615 &self,
616 i: usize,
617 va: &[u64],
618 sb: &usize,
619 carry: &mut [u64],
620 vc: &mut [u64],
621 ) {
622 let base: u64 = 1 << sb;
623 let mask: u64 = base - 1;
624 if i == 0 {
625 apply_vsssvv!(
626 self,
627 Self::sa_signed_digit_into_sb::<true, BALANCED>,
628 va,
629 &base,
630 &(i * sb),
631 &mask,
632 carry,
633 vc,
634 CHUNK
635 );
636 } else {
637 apply_vsssvv!(
638 self,
639 Self::sa_signed_digit_into_sb::<false, BALANCED>,
640 va,
641 &base,
642 &(i * sb),
643 &mask,
644 carry,
645 vc,
646 CHUNK
647 );
648 }
649 }
650}