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>(&self, a: &u64, b: &mut Montgomery<u64>) {
104 self.montgomery.prepare_assign::<REDUCE>(*a, b);
105 }
106
107 #[inline(always)]
108 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
109 &self,
110 a: &Montgomery<u64>,
111 b: &u64,
112 c: &mut u64,
113 ) {
114 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
115 }
116
117 #[inline(always)]
118 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Montgomery<u64>, b: &mut u64) {
119 self.montgomery.mul_external_assign::<REDUCE>(*a, b);
120 }
121
122 #[inline(always)]
123 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
124 &self,
125 a: &Barrett<u64>,
126 b: &u64,
127 c: &mut u64,
128 ) {
129 *c = self.barrett.mul_external::<REDUCE>(*a, *b);
130 }
131
132 #[inline(always)]
133 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Barrett<u64>, b: &mut u64) {
134 self.barrett.mul_external_assign::<REDUCE>(*a, b);
135 }
136
137 #[inline(always)]
138 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
139 &self,
140 a: &u64,
141 b: &u64,
142 c: &Barrett<u64>,
143 d: &mut u64,
144 ) {
145 match VBRANGE {
146 1 => *d = a + self.q - b,
147 2 => *d = a + self.two_q - b,
148 4 => *d = a + self.four_q - b,
149 _ => unreachable!("invalid SBRANGE argument"),
150 }
151 self.barrett.mul_external_assign::<REDUCE>(*c, d);
152 }
153
154 #[inline(always)]
155 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
156 &self,
157 a: &u64,
158 c: &Barrett<u64>,
159 b: &mut u64,
160 ) {
161 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(a, b);
162 self.barrett.mul_external_assign::<REDUCE>(*c, b);
163 }
164
165 #[inline(always)]
166 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
167 &self,
168 a: &u64,
169 b: &u64,
170 c: &Barrett<u64>,
171 d: &mut u64,
172 ) {
173 *d = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
174 }
175
176 #[inline(always)]
177 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
178 &self,
179 b: &u64,
180 c: &Barrett<u64>,
181 a: &mut u64,
182 ) {
183 *a = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
184 }
185
186 #[inline(always)]
187 fn sb_sub_sa_add_sc_mul_sd_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
188 &self,
189 a: &u64,
190 b: &u64,
191 c: &u64,
192 d: &Barrett<u64>,
193 e: &mut u64,
194 ) {
195 self.sa_sub_sb_into_sc::<SBRANGE, NONE>(&(b + c), a, e);
196 self.barrett.mul_external_assign::<REDUCE>(*d, e);
197 }
198
199 #[inline(always)]
200 fn sb_sub_sa_add_sc_mul_sd_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
201 &self,
202 b: &u64,
203 c: &u64,
204 d: &Barrett<u64>,
205 a: &mut u64,
206 ) {
207 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(&(b + c), a);
208 self.barrett.mul_external_assign::<REDUCE>(*d, a);
209 }
210}
211
212impl VectorOperations<u64> for Prime<u64> {
213 /// Applies a modular reduction on x based on REDUCE:
214 /// - LAZY: no modular reduction.
215 /// - ONCE: subtracts q if x >= q.
216 /// - TWO: subtracts 2q if x >= 2q.
217 /// - FOUR: subtracts 4q if x >= 4q.
218 /// - BARRETT: maps x to x mod q using Barrett reduction.
219 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
220 #[inline(always)]
221 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
222 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
223 }
224
225 #[inline(always)]
226 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
227 &self,
228 a: &[u64],
229 b: &[u64],
230 c: &mut [u64],
231 ) {
232 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
233 }
234
235 #[inline(always)]
236 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
237 &self,
238 a: &[u64],
239 b: &mut [u64],
240 ) {
241 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
242 }
243
244 #[inline(always)]
245 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
246 &self,
247 b: &u64,
248 a: &mut [u64],
249 ) {
250 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
251 }
252
253 #[inline(always)]
254 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
255 &self,
256 a: &[u64],
257 b: &u64,
258 c: &mut [u64],
259 ) {
260 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
261 }
262
263 #[inline(always)]
264 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
265 &self,
266 a: &[u64],
267 b: &[u64],
268 c: &mut [u64],
269 ) {
270 apply_vvv!(
271 self,
272 Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>,
273 a,
274 b,
275 c,
276 CHUNK
277 );
278 }
279
280 #[inline(always)]
281 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
282 &self,
283 b: &[u64],
284 a: &mut [u64],
285 ) {
286 apply_vv!(
287 self,
288 Self::sa_sub_sb_into_sa::<VBRANGE, REDUCE>,
289 b,
290 a,
291 CHUNK
292 );
293 }
294
295 #[inline(always)]
296 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
297 &self,
298 a: &[u64],
299 b: &mut [u64],
300 ) {
301 apply_vv!(
302 self,
303 Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>,
304 a,
305 b,
306 CHUNK
307 );
308 }
309
310 #[inline(always)]
311 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
312 &self,
313 a: &mut [u64],
314 ) {
315 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
316 }
317
318 #[inline(always)]
319 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
320 &self,
321 a: &[u64],
322 b: &mut [u64],
323 ) {
324 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
325 }
326
327 #[inline(always)]
328 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
329 &self,
330 a: &[u64],
331 b: &mut [Montgomery<u64>],
332 ) {
333 apply_vv!(self, Self::sa_prepare_montgomery_into_sb::<REDUCE>, a, b, CHUNK);
334 }
335
336 #[inline(always)]
337 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
338 &self,
339 a: &mut [Montgomery<u64>],
340 ) {
341 apply_v!(self, Self::sa_prepare_montgomery_into_sa::<REDUCE>, a, CHUNK);
342 }
343
344 #[inline(always)]
345 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
346 &self,
347 a: &[Montgomery<u64>],
348 b: &[u64],
349 c: &mut [u64],
350 ) {
351 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
352 }
353
354 #[inline(always)]
355 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
356 &self,
357 a: &[Montgomery<u64>],
358 b: &mut [u64],
359 ) {
360 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
361 }
362
363 #[inline(always)]
364 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
365 &self,
366 a: &Barrett<u64>,
367 b: &[u64],
368 c: &mut [u64],
369 ) {
370 apply_svv!(
371 self,
372 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
373 a,
374 b,
375 c,
376 CHUNK
377 );
378 }
379
380 #[inline(always)]
381 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
382 &self,
383 a: &Barrett<u64>,
384 b: &mut [u64],
385 ) {
386 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
387 }
388
389 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
390 &self,
391 a: &[u64],
392 b: &[u64],
393 c: &Barrett<u64>,
394 d: &mut [u64],
395 ) {
396 apply_vvsv!(
397 self,
398 Self::sa_sub_sb_mul_sc_into_sd::<VBRANGE, REDUCE>,
399 a,
400 b,
401 c,
402 d,
403 CHUNK
404 );
405 }
406
407 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
408 &self,
409 a: &[u64],
410 b: &Barrett<u64>,
411 c: &mut [u64],
412 ) {
413 apply_vsv!(
414 self,
415 Self::sa_sub_sb_mul_sc_into_sb::<VBRANGE, REDUCE>,
416 a,
417 b,
418 c,
419 CHUNK
420 );
421 }
422
423 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
424 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
425 &self,
426 b: &u64,
427 c: &Barrett<u64>,
428 a: &mut [u64],
429 ) {
430 apply_ssv!(
431 self,
432 Self::sa_add_sb_mul_sc_into_sa::<REDUCE>,
433 b,
434 c,
435 a,
436 CHUNK
437 );
438 }
439
440 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
441 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
442 &self,
443 a: &[u64],
444 b: &u64,
445 c: &Barrett<u64>,
446 d: &mut [u64],
447 ) {
448 apply_vssv!(
449 self,
450 Self::sa_add_sb_mul_sc_into_sd::<REDUCE>,
451 a,
452 b,
453 c,
454 d,
455 CHUNK
456 );
457 }
458
459 // vec(e) <- (vec(a) - vec(b) + scalar(c)) * scalar(e).
460 fn vb_sub_va_add_sc_mul_sd_into_ve<
461 const CHUNK: usize,
462 const VBRANGE: u8,
463 const REDUCE: REDUCEMOD,
464 >(
465 &self,
466 va: &[u64],
467 vb: &[u64],
468 sc: &u64,
469 sd: &Barrett<u64>,
470 ve: &mut [u64],
471 ) {
472 apply_vvssv!(
473 self,
474 Self::sb_sub_sa_add_sc_mul_sd_into_se::<VBRANGE, REDUCE>,
475 va,
476 vb,
477 sc,
478 sd,
479 ve,
480 CHUNK
481 );
482 }
483
484 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
485 fn vb_sub_va_add_sc_mul_sd_into_va<
486 const CHUNK: usize,
487 const VBRANGE: u8,
488 const REDUCE: REDUCEMOD,
489 >(
490 &self,
491 vb: &[u64],
492 sc: &u64,
493 sd: &Barrett<u64>,
494 va: &mut [u64],
495 ) {
496 apply_vssv!(
497 self,
498 Self::sb_sub_sa_add_sc_mul_sd_into_sa::<VBRANGE, REDUCE>,
499 vb,
500 sc,
501 sd,
502 va,
503 CHUNK
504 );
505 }
506}