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