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_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_mul_sb_montgomery_into_sc<const REDUCE: REDUCEMOD>(
113 &self,
114 a: &u64,
115 b: &Montgomery<u64>,
116 c: &mut u64,
117 ) {
118 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
119 }
120
121 #[inline(always)]
122 fn sa_mul_sb_montgomery_into_sa<const REDUCE: REDUCEMOD>(
123 &self,
124 b: &Montgomery<u64>,
125 a: &mut u64,
126 ) {
127 self.montgomery.mul_external_assign::<REDUCE>(*b, a);
128 }
129
130 #[inline(always)]
131 fn sa_mul_sb_barrett_into_sc<const REDUCE: REDUCEMOD>(
132 &self,
133 a: &u64,
134 b: &Barrett<u64>,
135 c: &mut u64,
136 ) {
137 *c = self.barrett.mul_external::<REDUCE>(b, a);
138 }
139
140 #[inline(always)]
141 fn sa_mul_sb_barrett_into_sa<const REDUCE: REDUCEMOD>(&self, b: &Barrett<u64>, a: &mut u64) {
142 self.barrett.mul_external_assign::<REDUCE>(b, a);
143 }
144
145 #[inline(always)]
146 fn sa_sub_sb_mul_sc_barrett_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
147 &self,
148 a: &u64,
149 b: &u64,
150 c: &Barrett<u64>,
151 d: &mut u64,
152 ) {
153 match VBRANGE {
154 1 => *d = a + self.q - b,
155 2 => *d = a + self.two_q - b,
156 4 => *d = a + self.four_q - b,
157 _ => unreachable!("invalid SBRANGE argument"),
158 }
159 self.barrett.mul_external_assign::<REDUCE>(c, d);
160 }
161
162 #[inline(always)]
163 fn sa_sub_sb_mul_sc_barrett_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
164 &self,
165 a: &u64,
166 c: &Barrett<u64>,
167 b: &mut u64,
168 ) {
169 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(a, b);
170 self.barrett.mul_external_assign::<REDUCE>(c, b);
171 }
172
173 #[inline(always)]
174 fn sa_add_sb_mul_sc_barrett_into_sd<const REDUCE: REDUCEMOD>(
175 &self,
176 a: &u64,
177 b: &u64,
178 c: &Barrett<u64>,
179 d: &mut u64,
180 ) {
181 *d = self.barrett.mul_external::<REDUCE>(c, &(*a + b));
182 }
183
184 #[inline(always)]
185 fn sa_add_sb_mul_sc_barrett_into_sa<const REDUCE: REDUCEMOD>(
186 &self,
187 b: &u64,
188 c: &Barrett<u64>,
189 a: &mut u64,
190 ) {
191 *a = self.barrett.mul_external::<REDUCE>(c, &(*a + b));
192 }
193
194 #[inline(always)]
195 fn sb_sub_sa_add_sc_mul_sd_barrett_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
196 &self,
197 a: &u64,
198 b: &u64,
199 c: &u64,
200 d: &Barrett<u64>,
201 e: &mut u64,
202 ) {
203 self.sa_sub_sb_into_sc::<SBRANGE, NONE>(&(b + c), a, e);
204 self.barrett.mul_external_assign::<REDUCE>(d, e);
205 }
206
207 #[inline(always)]
208 fn sb_sub_sa_add_sc_mul_sd_barrett_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
209 &self,
210 b: &u64,
211 c: &u64,
212 d: &Barrett<u64>,
213 a: &mut u64,
214 ) {
215 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(&(b + c), a);
216 self.barrett.mul_external_assign::<REDUCE>(d, a);
217 }
218
219 #[inline(always)]
220 fn sa_rsh_sb_mask_sc_into_sa(&self, b: &usize, c: &u64, a: &mut u64) {
221 *a = (*a >> b) & c
222 }
223
224 #[inline(always)]
225 fn sa_rsh_sb_mask_sc_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64) {
226 *d = (*a >> b) & c
227 }
228
229 #[inline(always)]
230 fn sa_rsh_sb_mask_sc_add_sd_into_sd(&self, a: &u64, b: &usize, c: &u64, d: &mut u64) {
231 *d += (*a >> b) & c
232 }
233
234 #[inline(always)]
235 fn sa_signed_digit_into_sb<const CARRYOVERWRITE: bool, const BALANCED: bool>(
236 &self,
237 a: &u64,
238 base: &u64,
239 shift: &usize,
240 mask: &u64,
241 carry: &mut u64,
242 b: &mut u64,
243 ) {
244 if CARRYOVERWRITE {
245 self.sa_rsh_sb_mask_sc_into_sd(a, shift, mask, carry);
246 } else {
247 self.sa_rsh_sb_mask_sc_add_sd_into_sd(a, shift, mask, carry);
248 }
249
250 let c: u64 = if BALANCED && *carry == base >> 1 {
251 a & 1
252 } else {
253 ((*carry | (*carry << 1)) >> shift) & 1
254 };
255
256 *b = *carry + (self.q - base) * c;
257 *carry = c;
258 }
259}
260
261impl VectorOperations<u64> for Prime<u64> {
262 /// Applies a modular reduction on x based on REDUCE:
263 /// - LAZY: no modular reduction.
264 /// - ONCE: subtracts q if x >= q.
265 /// - TWO: subtracts 2q if x >= 2q.
266 /// - FOUR: subtracts 4q if x >= 4q.
267 /// - BARRETT: maps x to x mod q using Barrett reduction.
268 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
269 #[inline(always)]
270 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
271 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
272 }
273
274 #[inline(always)]
275 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
276 &self,
277 a: &[u64],
278 b: &[u64],
279 c: &mut [u64],
280 ) {
281 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
282 }
283
284 #[inline(always)]
285 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
286 &self,
287 a: &[u64],
288 b: &mut [u64],
289 ) {
290 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
291 }
292
293 #[inline(always)]
294 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
295 &self,
296 b: &u64,
297 a: &mut [u64],
298 ) {
299 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
300 }
301
302 #[inline(always)]
303 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
304 &self,
305 a: &[u64],
306 b: &u64,
307 c: &mut [u64],
308 ) {
309 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
310 }
311
312 #[inline(always)]
313 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
314 &self,
315 a: &[u64],
316 b: &[u64],
317 c: &mut [u64],
318 ) {
319 apply_vvv!(
320 self,
321 Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>,
322 a,
323 b,
324 c,
325 CHUNK
326 );
327 }
328
329 #[inline(always)]
330 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
331 &self,
332 b: &[u64],
333 a: &mut [u64],
334 ) {
335 apply_vv!(
336 self,
337 Self::sa_sub_sb_into_sa::<VBRANGE, REDUCE>,
338 b,
339 a,
340 CHUNK
341 );
342 }
343
344 #[inline(always)]
345 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
346 &self,
347 a: &[u64],
348 b: &mut [u64],
349 ) {
350 apply_vv!(
351 self,
352 Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>,
353 a,
354 b,
355 CHUNK
356 );
357 }
358
359 #[inline(always)]
360 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
361 &self,
362 a: &mut [u64],
363 ) {
364 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
365 }
366
367 #[inline(always)]
368 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
369 &self,
370 a: &[u64],
371 b: &mut [u64],
372 ) {
373 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
374 }
375
376 #[inline(always)]
377 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
378 &self,
379 a: &[u64],
380 b: &mut [Montgomery<u64>],
381 ) {
382 apply_vv!(
383 self,
384 Self::sa_prepare_montgomery_into_sb::<REDUCE>,
385 a,
386 b,
387 CHUNK
388 );
389 }
390
391 #[inline(always)]
392 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
393 &self,
394 a: &mut [Montgomery<u64>],
395 ) {
396 apply_v!(
397 self,
398 Self::sa_prepare_montgomery_into_sa::<REDUCE>,
399 a,
400 CHUNK
401 );
402 }
403
404 #[inline(always)]
405 fn va_mul_vb_montgomery_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
406 &self,
407 a: &[Montgomery<u64>],
408 b: &[u64],
409 c: &mut [u64],
410 ) {
411 apply_vvv!(
412 self,
413 Self::sa_mul_sb_montgomery_into_sc::<REDUCE>,
414 a,
415 b,
416 c,
417 CHUNK
418 );
419 }
420
421 #[inline(always)]
422 fn va_mul_vb_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
423 &self,
424 b: &[Montgomery<u64>],
425 a: &mut [u64],
426 ) {
427 apply_vv!(
428 self,
429 Self::sa_mul_sb_montgomery_into_sa::<REDUCE>,
430 b,
431 a,
432 CHUNK
433 );
434 }
435
436 #[inline(always)]
437 fn va_mul_sb_barrett_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
438 &self,
439 a: &[u64],
440 b: &Barrett<u64>,
441 c: &mut [u64],
442 ) {
443 apply_vsv!(
444 self,
445 Self::sa_mul_sb_barrett_into_sc::<REDUCE>,
446 a,
447 b,
448 c,
449 CHUNK
450 );
451 }
452
453 #[inline(always)]
454 fn va_mul_sb_barrett_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
455 &self,
456 b: &Barrett<u64>,
457 a: &mut [u64],
458 ) {
459 apply_sv!(self, Self::sa_mul_sb_barrett_into_sa::<REDUCE>, b, a, CHUNK);
460 }
461
462 fn va_sub_vb_mul_sc_barrett_into_vd<
463 const CHUNK: usize,
464 const VBRANGE: u8,
465 const REDUCE: REDUCEMOD,
466 >(
467 &self,
468 a: &[u64],
469 b: &[u64],
470 c: &Barrett<u64>,
471 d: &mut [u64],
472 ) {
473 apply_vvsv!(
474 self,
475 Self::sa_sub_sb_mul_sc_barrett_into_sd::<VBRANGE, REDUCE>,
476 a,
477 b,
478 c,
479 d,
480 CHUNK
481 );
482 }
483
484 fn va_sub_vb_mul_sc_barrett_into_vb<
485 const CHUNK: usize,
486 const VBRANGE: u8,
487 const REDUCE: REDUCEMOD,
488 >(
489 &self,
490 a: &[u64],
491 b: &Barrett<u64>,
492 c: &mut [u64],
493 ) {
494 apply_vsv!(
495 self,
496 Self::sa_sub_sb_mul_sc_barrett_into_sb::<VBRANGE, REDUCE>,
497 a,
498 b,
499 c,
500 CHUNK
501 );
502 }
503
504 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
505 fn va_add_sb_mul_sc_barrett_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
506 &self,
507 b: &u64,
508 c: &Barrett<u64>,
509 a: &mut [u64],
510 ) {
511 apply_ssv!(
512 self,
513 Self::sa_add_sb_mul_sc_barrett_into_sa::<REDUCE>,
514 b,
515 c,
516 a,
517 CHUNK
518 );
519 }
520
521 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
522 fn va_add_sb_mul_sc_barrett_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
523 &self,
524 a: &[u64],
525 b: &u64,
526 c: &Barrett<u64>,
527 d: &mut [u64],
528 ) {
529 apply_vssv!(
530 self,
531 Self::sa_add_sb_mul_sc_barrett_into_sd::<REDUCE>,
532 a,
533 b,
534 c,
535 d,
536 CHUNK
537 );
538 }
539
540 // vec(e) <- (vec(a) - vec(b) + scalar(c)) * scalar(e).
541 fn vb_sub_va_add_sc_mul_sd_barrett_into_ve<
542 const CHUNK: usize,
543 const VBRANGE: u8,
544 const REDUCE: REDUCEMOD,
545 >(
546 &self,
547 va: &[u64],
548 vb: &[u64],
549 sc: &u64,
550 sd: &Barrett<u64>,
551 ve: &mut [u64],
552 ) {
553 apply_vvssv!(
554 self,
555 Self::sb_sub_sa_add_sc_mul_sd_barrett_into_se::<VBRANGE, REDUCE>,
556 va,
557 vb,
558 sc,
559 sd,
560 ve,
561 CHUNK
562 );
563 }
564
565 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
566 fn vb_sub_va_add_sc_mul_sd_barrett_into_va<
567 const CHUNK: usize,
568 const VBRANGE: u8,
569 const REDUCE: REDUCEMOD,
570 >(
571 &self,
572 vb: &[u64],
573 sc: &u64,
574 sd: &Barrett<u64>,
575 va: &mut [u64],
576 ) {
577 apply_vssv!(
578 self,
579 Self::sb_sub_sa_add_sc_mul_sd_barrett_into_sa::<VBRANGE, REDUCE>,
580 vb,
581 sc,
582 sd,
583 va,
584 CHUNK
585 );
586 }
587
588 // vec(a) <- (vec(a)>>scalar(b)) & scalar(c).
589 fn va_rsh_sb_mask_sc_into_va<const CHUNK: usize>(&self, sb: &usize, sc: &u64, va: &mut [u64]) {
590 apply_ssv!(self, Self::sa_rsh_sb_mask_sc_into_sa, sb, sc, va, CHUNK);
591 }
592
593 // vec(d) <- (vec(a)>>scalar(b)) & scalar(c).
594 fn va_rsh_sb_mask_sc_into_vd<const CHUNK: usize>(
595 &self,
596 va: &[u64],
597 sb: &usize,
598 sc: &u64,
599 vd: &mut [u64],
600 ) {
601 apply_vssv!(self, Self::sa_rsh_sb_mask_sc_into_sd, va, sb, sc, vd, CHUNK);
602 }
603
604 // vec(d) <- vec(d) + (vec(a)>>scalar(b)) & scalar(c).
605 fn va_rsh_sb_mask_sc_add_vd_into_vd<const CHUNK: usize>(
606 &self,
607 va: &[u64],
608 sb: &usize,
609 sc: &u64,
610 vd: &mut [u64],
611 ) {
612 apply_vssv!(
613 self,
614 Self::sa_rsh_sb_mask_sc_add_sd_into_sd,
615 va,
616 sb,
617 sc,
618 vd,
619 CHUNK
620 );
621 }
622
623 // vec(c) <- i-th unsigned digit base 2^{sb} of vec(a).
624 // vec(c) is ensured to be in the range [0, 2^{sb}-1[ with E[vec(c)] = 2^{sb}-1.
625 fn va_ith_digit_unsigned_base_sb_into_vc<const CHUNK: usize>(
626 &self,
627 i: usize,
628 va: &[u64],
629 sb: &usize,
630 vc: &mut [u64],
631 ) {
632 self.va_rsh_sb_mask_sc_into_vd::<CHUNK>(va, &(i * sb), &((1 << sb) - 1), vc);
633 }
634
635 // vec(c) <- i-th signed digit base 2^{w} of vec(a).
636 // Reads the carry of the i-1-th iteration and write the carry on the i-th iteration on carry.
637 // if i > 0, carry of the i-1th iteration must be provided.
638 // 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
639 fn va_ith_digit_signed_base_sb_into_vc<const CHUNK: usize, const BALANCED: bool>(
640 &self,
641 i: usize,
642 va: &[u64],
643 sb: &usize,
644 carry: &mut [u64],
645 vc: &mut [u64],
646 ) {
647 let base: u64 = 1 << sb;
648 let mask: u64 = base - 1;
649 if i == 0 {
650 apply_vsssvv!(
651 self,
652 Self::sa_signed_digit_into_sb::<true, BALANCED>,
653 va,
654 &base,
655 &(i * sb),
656 &mask,
657 carry,
658 vc,
659 CHUNK
660 );
661 } else {
662 apply_vsssvv!(
663 self,
664 Self::sa_signed_digit_into_sb::<false, BALANCED>,
665 va,
666 &base,
667 &(i * sb),
668 &mask,
669 carry,
670 vc,
671 CHUNK
672 );
673 }
674 }
675}