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_vssv, apply_vsv, apply_vv, apply_vvssv,
8 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
216impl VectorOperations<u64> for Prime<u64> {
217 /// Applies a modular reduction on x based on REDUCE:
218 /// - LAZY: no modular reduction.
219 /// - ONCE: subtracts q if x >= q.
220 /// - TWO: subtracts 2q if x >= 2q.
221 /// - FOUR: subtracts 4q if x >= 4q.
222 /// - BARRETT: maps x to x mod q using Barrett reduction.
223 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
224 #[inline(always)]
225 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
226 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
227 }
228
229 #[inline(always)]
230 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
231 &self,
232 a: &[u64],
233 b: &[u64],
234 c: &mut [u64],
235 ) {
236 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
237 }
238
239 #[inline(always)]
240 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
241 &self,
242 a: &[u64],
243 b: &mut [u64],
244 ) {
245 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
246 }
247
248 #[inline(always)]
249 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
250 &self,
251 b: &u64,
252 a: &mut [u64],
253 ) {
254 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
255 }
256
257 #[inline(always)]
258 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
259 &self,
260 a: &[u64],
261 b: &u64,
262 c: &mut [u64],
263 ) {
264 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
265 }
266
267 #[inline(always)]
268 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
269 &self,
270 a: &[u64],
271 b: &[u64],
272 c: &mut [u64],
273 ) {
274 apply_vvv!(
275 self,
276 Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>,
277 a,
278 b,
279 c,
280 CHUNK
281 );
282 }
283
284 #[inline(always)]
285 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
286 &self,
287 b: &[u64],
288 a: &mut [u64],
289 ) {
290 apply_vv!(
291 self,
292 Self::sa_sub_sb_into_sa::<VBRANGE, REDUCE>,
293 b,
294 a,
295 CHUNK
296 );
297 }
298
299 #[inline(always)]
300 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
301 &self,
302 a: &[u64],
303 b: &mut [u64],
304 ) {
305 apply_vv!(
306 self,
307 Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>,
308 a,
309 b,
310 CHUNK
311 );
312 }
313
314 #[inline(always)]
315 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
316 &self,
317 a: &mut [u64],
318 ) {
319 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
320 }
321
322 #[inline(always)]
323 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
324 &self,
325 a: &[u64],
326 b: &mut [u64],
327 ) {
328 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
329 }
330
331 #[inline(always)]
332 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
333 &self,
334 a: &[u64],
335 b: &mut [Montgomery<u64>],
336 ) {
337 apply_vv!(
338 self,
339 Self::sa_prepare_montgomery_into_sb::<REDUCE>,
340 a,
341 b,
342 CHUNK
343 );
344 }
345
346 #[inline(always)]
347 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
348 &self,
349 a: &mut [Montgomery<u64>],
350 ) {
351 apply_v!(
352 self,
353 Self::sa_prepare_montgomery_into_sa::<REDUCE>,
354 a,
355 CHUNK
356 );
357 }
358
359 #[inline(always)]
360 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
361 &self,
362 a: &[Montgomery<u64>],
363 b: &[u64],
364 c: &mut [u64],
365 ) {
366 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
367 }
368
369 #[inline(always)]
370 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
371 &self,
372 a: &[Montgomery<u64>],
373 b: &mut [u64],
374 ) {
375 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
376 }
377
378 #[inline(always)]
379 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
380 &self,
381 a: &Barrett<u64>,
382 b: &[u64],
383 c: &mut [u64],
384 ) {
385 apply_svv!(
386 self,
387 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
388 a,
389 b,
390 c,
391 CHUNK
392 );
393 }
394
395 #[inline(always)]
396 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
397 &self,
398 a: &Barrett<u64>,
399 b: &mut [u64],
400 ) {
401 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
402 }
403
404 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
405 &self,
406 a: &[u64],
407 b: &[u64],
408 c: &Barrett<u64>,
409 d: &mut [u64],
410 ) {
411 apply_vvsv!(
412 self,
413 Self::sa_sub_sb_mul_sc_into_sd::<VBRANGE, REDUCE>,
414 a,
415 b,
416 c,
417 d,
418 CHUNK
419 );
420 }
421
422 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
423 &self,
424 a: &[u64],
425 b: &Barrett<u64>,
426 c: &mut [u64],
427 ) {
428 apply_vsv!(
429 self,
430 Self::sa_sub_sb_mul_sc_into_sb::<VBRANGE, REDUCE>,
431 a,
432 b,
433 c,
434 CHUNK
435 );
436 }
437
438 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
439 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
440 &self,
441 b: &u64,
442 c: &Barrett<u64>,
443 a: &mut [u64],
444 ) {
445 apply_ssv!(
446 self,
447 Self::sa_add_sb_mul_sc_into_sa::<REDUCE>,
448 b,
449 c,
450 a,
451 CHUNK
452 );
453 }
454
455 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
456 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
457 &self,
458 a: &[u64],
459 b: &u64,
460 c: &Barrett<u64>,
461 d: &mut [u64],
462 ) {
463 apply_vssv!(
464 self,
465 Self::sa_add_sb_mul_sc_into_sd::<REDUCE>,
466 a,
467 b,
468 c,
469 d,
470 CHUNK
471 );
472 }
473
474 // vec(e) <- (vec(a) - vec(b) + scalar(c)) * scalar(e).
475 fn vb_sub_va_add_sc_mul_sd_into_ve<
476 const CHUNK: usize,
477 const VBRANGE: u8,
478 const REDUCE: REDUCEMOD,
479 >(
480 &self,
481 va: &[u64],
482 vb: &[u64],
483 sc: &u64,
484 sd: &Barrett<u64>,
485 ve: &mut [u64],
486 ) {
487 apply_vvssv!(
488 self,
489 Self::sb_sub_sa_add_sc_mul_sd_into_se::<VBRANGE, REDUCE>,
490 va,
491 vb,
492 sc,
493 sd,
494 ve,
495 CHUNK
496 );
497 }
498
499 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
500 fn vb_sub_va_add_sc_mul_sd_into_va<
501 const CHUNK: usize,
502 const VBRANGE: u8,
503 const REDUCE: REDUCEMOD,
504 >(
505 &self,
506 vb: &[u64],
507 sc: &u64,
508 sd: &Barrett<u64>,
509 va: &mut [u64],
510 ) {
511 apply_vssv!(
512 self,
513 Self::sb_sub_sa_add_sc_mul_sd_into_sa::<VBRANGE, REDUCE>,
514 vb,
515 sc,
516 sd,
517 va,
518 CHUNK
519 );
520 }
521}