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::{REDUCEMOD, NONE};
5use crate::modulus::{ScalarOperations, VectorOperations};
6use crate::{apply_sv, apply_svv, apply_v, apply_vsv, apply_vv, apply_vvsv, apply_vvv, apply_ssv, apply_vssv, apply_vvssv};
7use itertools::izip;
8
9impl ScalarOperations<u64> for Prime<u64> {
10 /// Applies a modular reduction on x based on REDUCE:
11 /// - LAZY: no modular reduction.
12 /// - ONCE: subtracts q if x >= q.
13 /// - TWO: subtracts 2q if x >= 2q.
14 /// - FOUR: subtracts 4q if x >= 4q.
15 /// - BARRETT: maps x to x mod q using Barrett reduction.
16 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
17 #[inline(always)]
18 fn sa_reduce_into_sa<const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
19 self.montgomery.reduce_assign::<REDUCE>(a);
20 }
21
22 #[inline(always)]
23 fn sa_add_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &u64, c: &mut u64) {
24 *c = a.wrapping_add(*b);
25 self.sa_reduce_into_sa::<REDUCE>(c);
26 }
27
28 #[inline(always)]
29 fn sa_add_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
30 *b = a.wrapping_add(*b);
31 self.sa_reduce_into_sa::<REDUCE>(b);
32 }
33
34 #[inline(always)]
35 fn sa_sub_sb_into_sc<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &u64, c: &mut u64) {
36 match SBRANGE{
37 1 =>{*c = *a + self.q - *b}
38 2 =>{*c = *a + self.two_q - *b}
39 4 =>{*c = *a + self.four_q - *b}
40 _ => unreachable!("invalid SBRANGE argument"),
41 }
42 self.sa_reduce_into_sa::<REDUCE>(c)
43 }
44
45 #[inline(always)]
46 fn sa_sub_sb_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut u64) {
47 match SBRANGE{
48 1 =>{*a = *a + self.q - *b}
49 2 =>{*a = *a + self.two_q - *b}
50 4 =>{*a = *a + self.four_q - *b}
51 _ => unreachable!("invalid SBRANGE argument"),
52 }
53 self.sa_reduce_into_sa::<REDUCE>(a)
54 }
55
56 #[inline(always)]
57 fn sa_sub_sb_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
58 match SBRANGE{
59 1 =>{*b = *a + self.q - *b}
60 2 =>{*b = *a + self.two_q - *b}
61 4 =>{*b = *a + self.four_q - *b}
62 _ => unreachable!("invalid SBRANGE argument"),
63 }
64 self.sa_reduce_into_sa::<REDUCE>(b)
65 }
66
67 #[inline(always)]
68 fn sa_neg_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
69 match SBRANGE{
70 1 =>{*a = self.q - *a}
71 2 =>{*a = self.two_q - *a}
72 4 =>{*a = self.four_q - *a}
73 _ => unreachable!("invalid SBRANGE argument"),
74 }
75 self.sa_reduce_into_sa::<REDUCE>(a)
76 }
77
78 #[inline(always)]
79 fn sa_neg_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
80 match SBRANGE{
81 1 =>{*b = self.q - *a}
82 2 =>{*b = self.two_q - *a}
83 4 =>{*b = self.four_q - *a}
84 _ => unreachable!("invalid SBRANGE argument"),
85 }
86 self.sa_reduce_into_sa::<REDUCE>(b)
87 }
88
89 #[inline(always)]
90 fn sa_prep_mont_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut Montgomery<u64>) {
91 self.montgomery.prepare_assign::<REDUCE>(*a, b);
92 }
93
94 #[inline(always)]
95 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
96 &self,
97 a: &Montgomery<u64>,
98 b: &u64,
99 c: &mut u64,
100 ) {
101 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
102 }
103
104 #[inline(always)]
105 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Montgomery<u64>, b: &mut u64) {
106 self.montgomery.mul_external_assign::<REDUCE>(*a, b);
107 }
108
109 #[inline(always)]
110 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
111 &self,
112 a: &Barrett<u64>,
113 b: &u64,
114 c: &mut u64,
115 ) {
116 *c = self.barrett.mul_external::<REDUCE>(*a, *b);
117 }
118
119 #[inline(always)]
120 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Barrett<u64>, b: &mut u64) {
121 self.barrett.mul_external_assign::<REDUCE>(*a, b);
122 }
123
124 #[inline(always)]
125 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
126 &self,
127 a: &u64,
128 b: &u64,
129 c: &Barrett<u64>,
130 d: &mut u64,
131 ) {
132 match VBRANGE{
133 1 =>{*d = a + self.q - b}
134 2 =>{*d = a + self.two_q - b}
135 4 =>{*d = a + self.four_q - b}
136 _ => unreachable!("invalid SBRANGE argument"),
137 }
138 self.barrett.mul_external_assign::<REDUCE>(*c, d);
139 }
140
141 #[inline(always)]
142 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
143 &self,
144 a: &u64,
145 c: &Barrett<u64>,
146 b: &mut u64,
147 ) {
148 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(a, b);
149 self.barrett.mul_external_assign::<REDUCE>(*c, b);
150 }
151
152 #[inline(always)]
153 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
154 &self,
155 a: &u64,
156 b: &u64,
157 c: &Barrett<u64>,
158 d: &mut u64
159 ) {
160 *d = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
161 }
162
163 #[inline(always)]
164 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
165 &self,
166 b: &u64,
167 c: &Barrett<u64>,
168 a: &mut u64
169 ) {
170 *a = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
171 }
172
173 #[inline(always)]
174 fn sb_sub_sa_add_sc_mul_sd_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
175 &self,
176 a: &u64,
177 b: &u64,
178 c: &u64,
179 d: &Barrett<u64>,
180 e: &mut u64
181 ) {
182 self.sa_sub_sb_into_sc::<SBRANGE, NONE>(&(b + c), a, e);
183 self.barrett.mul_external_assign::<REDUCE>(*d, e);
184 }
185
186 #[inline(always)]
187 fn sb_sub_sa_add_sc_mul_sd_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
188 &self,
189 b: &u64,
190 c: &u64,
191 d: &Barrett<u64>,
192 a: &mut u64
193 ) {
194 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(&(b + c), a);
195 self.barrett.mul_external_assign::<REDUCE>(*d, a);
196 }
197
198}
199
200impl VectorOperations<u64> for Prime<u64> {
201 /// Applies a modular reduction on x based on REDUCE:
202 /// - LAZY: no modular reduction.
203 /// - ONCE: subtracts q if x >= q.
204 /// - TWO: subtracts 2q if x >= 2q.
205 /// - FOUR: subtracts 4q if x >= 4q.
206 /// - BARRETT: maps x to x mod q using Barrett reduction.
207 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
208 #[inline(always)]
209 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
210 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
211 }
212
213 #[inline(always)]
214 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
215 &self,
216 a: &[u64],
217 b: &[u64],
218 c: &mut [u64],
219 ) {
220 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
221 }
222
223 #[inline(always)]
224 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
225 &self,
226 a: &[u64],
227 b: &mut [u64],
228 ) {
229 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
230 }
231
232 #[inline(always)]
233 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
234 &self,
235 b: &u64,
236 a: &mut [u64],
237 ) {
238 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
239 }
240
241 #[inline(always)]
242 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
243 &self,
244 a: &[u64],
245 b: &u64,
246 c: &mut [u64],
247 ) {
248 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
249 }
250
251 #[inline(always)]
252 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
253 &self,
254 a: &[u64],
255 b: &[u64],
256 c: &mut [u64],
257 ) {
258 apply_vvv!(self, Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>, a, b, c, CHUNK);
259 }
260
261 #[inline(always)]
262 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
263 &self,
264 b: &[u64],
265 a: &mut [u64],
266 ) {
267 apply_vv!(self, Self::sa_sub_sb_into_sa::<VBRANGE, REDUCE>, b, a, CHUNK);
268 }
269
270 #[inline(always)]
271 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
272 &self,
273 a: &[u64],
274 b: &mut [u64],
275 ) {
276 apply_vv!(self, Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>, a, b, CHUNK);
277 }
278
279 #[inline(always)]
280 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
281 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
282 }
283
284 #[inline(always)]
285 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
286 &self,
287 a: &[u64],
288 b: &mut [u64],
289 ) {
290 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
291 }
292
293 #[inline(always)]
294 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
295 &self,
296 a: &[u64],
297 b: &mut [Montgomery<u64>],
298 ) {
299 apply_vv!(self, Self::sa_prep_mont_into_sb::<REDUCE>, a, b, CHUNK);
300 }
301
302 #[inline(always)]
303 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
304 &self,
305 a: &[Montgomery<u64>],
306 b: &[u64],
307 c: &mut [u64],
308 ) {
309 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
310 }
311
312 #[inline(always)]
313 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
314 &self,
315 a: &[Montgomery<u64>],
316 b: &mut [u64],
317 ) {
318 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
319 }
320
321 #[inline(always)]
322 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
323 &self,
324 a: &Barrett<u64>,
325 b: &[u64],
326 c: &mut [u64],
327 ) {
328 apply_svv!(
329 self,
330 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
331 a,
332 b,
333 c,
334 CHUNK
335 );
336 }
337
338 #[inline(always)]
339 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
340 &self,
341 a: &Barrett<u64>,
342 b: &mut [u64],
343 ) {
344 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
345 }
346
347 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
348 &self,
349 a: &[u64],
350 b: &[u64],
351 c: &Barrett<u64>,
352 d: &mut [u64],
353 ) {
354 apply_vvsv!(
355 self,
356 Self::sa_sub_sb_mul_sc_into_sd::<VBRANGE, REDUCE>,
357 a,
358 b,
359 c,
360 d,
361 CHUNK
362 );
363 }
364
365 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
366 &self,
367 a: &[u64],
368 b: &Barrett<u64>,
369 c: &mut [u64],
370 ) {
371 apply_vsv!(
372 self,
373 Self::sa_sub_sb_mul_sc_into_sb::<VBRANGE, REDUCE>,
374 a,
375 b,
376 c,
377 CHUNK
378 );
379 }
380
381 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
382 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
383 &self,
384 b: &u64,
385 c: &Barrett<u64>,
386 a: &mut [u64],
387 ) {
388 apply_ssv!(
389 self,
390 Self::sa_add_sb_mul_sc_into_sa::<REDUCE>,
391 b,
392 c,
393 a,
394 CHUNK
395 );
396 }
397
398 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
399 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
400 &self,
401 a: &[u64],
402 b: &u64,
403 c: &Barrett<u64>,
404 d: &mut [u64],
405 ) {
406 apply_vssv!(
407 self,
408 Self::sa_add_sb_mul_sc_into_sd::<REDUCE>,
409 a,
410 b,
411 c,
412 d,
413 CHUNK
414 );
415 }
416
417 // vec(e) <- (vec(a) - vec(b) + scalar(c)) * scalar(e).
418 fn vb_sub_va_add_sc_mul_sd_into_ve<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
419 &self,
420 va: &[u64],
421 vb: &[u64],
422 sc: &u64,
423 sd: &Barrett<u64>,
424 ve: &mut [u64],
425 ){
426 apply_vvssv!(
427 self,
428 Self::sb_sub_sa_add_sc_mul_sd_into_se::<VBRANGE, REDUCE>,
429 va,
430 vb,
431 sc,
432 sd,
433 ve,
434 CHUNK
435 );
436 }
437
438 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
439 fn vb_sub_va_add_sc_mul_sd_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
440 &self,
441 vb: &[u64],
442 sc: &u64,
443 sd: &Barrett<u64>,
444 va: &mut [u64],
445 ){
446
447 apply_vssv!(
448 self,
449 Self::sb_sub_sa_add_sc_mul_sd_into_sa::<VBRANGE, REDUCE>,
450 vb,
451 sc,
452 sd,
453 va,
454 CHUNK
455 );
456 }
457}