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};
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_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
47 match SBRANGE{
48 1 =>{*b = *a + self.q - *b}
49 2 =>{*b = *a + self.two_q - *b}
50 4 =>{*b = *a + self.four_q - *b}
51 _ => unreachable!("invalid SBRANGE argument"),
52 }
53 self.sa_reduce_into_sa::<REDUCE>(b)
54 }
55
56 #[inline(always)]
57 fn sa_neg_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
58 match SBRANGE{
59 1 =>{*a = self.q - *a}
60 2 =>{*a = self.two_q - *a}
61 4 =>{*a = self.four_q - *a}
62 _ => unreachable!("invalid SBRANGE argument"),
63 }
64 self.sa_reduce_into_sa::<REDUCE>(a)
65 }
66
67 #[inline(always)]
68 fn sa_neg_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
69 match SBRANGE{
70 1 =>{*b = self.q - *a}
71 2 =>{*b = self.two_q - *a}
72 4 =>{*b = self.four_q - *a}
73 _ => unreachable!("invalid SBRANGE argument"),
74 }
75 self.sa_reduce_into_sa::<REDUCE>(b)
76 }
77
78 #[inline(always)]
79 fn sa_prep_mont_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut Montgomery<u64>) {
80 self.montgomery.prepare_assign::<REDUCE>(*a, b);
81 }
82
83 #[inline(always)]
84 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
85 &self,
86 a: &Montgomery<u64>,
87 b: &u64,
88 c: &mut u64,
89 ) {
90 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
91 }
92
93 #[inline(always)]
94 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Montgomery<u64>, b: &mut u64) {
95 self.montgomery.mul_external_assign::<REDUCE>(*a, b);
96 }
97
98 #[inline(always)]
99 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
100 &self,
101 a: &Barrett<u64>,
102 b: &u64,
103 c: &mut u64,
104 ) {
105 *c = self.barrett.mul_external::<REDUCE>(*a, *b);
106 }
107
108 #[inline(always)]
109 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Barrett<u64>, b: &mut u64) {
110 self.barrett.mul_external_assign::<REDUCE>(*a, b);
111 }
112
113 #[inline(always)]
114 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
115 &self,
116 a: &u64,
117 b: &u64,
118 c: &Barrett<u64>,
119 d: &mut u64,
120 ) {
121 match VBRANGE{
122 1 =>{*d = a + self.q - b}
123 2 =>{*d = a + self.two_q - b}
124 4 =>{*d = a + self.four_q - b}
125 _ => unreachable!("invalid SBRANGE argument"),
126 }
127 self.barrett.mul_external_assign::<REDUCE>(*c, d);
128 }
129
130 #[inline(always)]
131 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
132 &self,
133 a: &u64,
134 c: &Barrett<u64>,
135 b: &mut u64,
136 ) {
137 self.sa_sub_sb_into_sb::<SBRANGE, NONE>(a, b);
138 self.barrett.mul_external_assign::<REDUCE>(*c, b);
139 }
140
141 #[inline(always)]
142 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
143 &self,
144 a: &u64,
145 b: &u64,
146 c: &Barrett<u64>,
147 d: &mut u64
148 ) {
149 *d = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
150 }
151
152 #[inline(always)]
153 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
154 &self,
155 b: &u64,
156 c: &Barrett<u64>,
157 a: &mut u64
158 ) {
159 *a = self.barrett.mul_external::<REDUCE>(*c, *a + *b);
160 }
161
162}
163
164impl VectorOperations<u64> for Prime<u64> {
165 /// Applies a modular reduction on x based on REDUCE:
166 /// - LAZY: no modular reduction.
167 /// - ONCE: subtracts q if x >= q.
168 /// - TWO: subtracts 2q if x >= 2q.
169 /// - FOUR: subtracts 4q if x >= 4q.
170 /// - BARRETT: maps x to x mod q using Barrett reduction.
171 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
172 #[inline(always)]
173 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
174 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
175 }
176
177 #[inline(always)]
178 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
179 &self,
180 a: &[u64],
181 b: &[u64],
182 c: &mut [u64],
183 ) {
184 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
185 }
186
187 #[inline(always)]
188 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
189 &self,
190 a: &[u64],
191 b: &mut [u64],
192 ) {
193 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
194 }
195
196 #[inline(always)]
197 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
198 &self,
199 b: &u64,
200 a: &mut [u64],
201 ) {
202 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, b, a, CHUNK);
203 }
204
205 #[inline(always)]
206 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
207 &self,
208 a: &[u64],
209 b: &u64,
210 c: &mut [u64],
211 ) {
212 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
213 }
214
215 #[inline(always)]
216 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
217 &self,
218 a: &[u64],
219 b: &[u64],
220 c: &mut [u64],
221 ) {
222 apply_vvv!(self, Self::sa_sub_sb_into_sc::<VBRANGE, REDUCE>, a, b, c, CHUNK);
223 }
224
225 #[inline(always)]
226 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
227 &self,
228 a: &[u64],
229 b: &mut [u64],
230 ) {
231 apply_vv!(self, Self::sa_sub_sb_into_sb::<VBRANGE, REDUCE>, a, b, CHUNK);
232 }
233
234 #[inline(always)]
235 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
236 apply_v!(self, Self::sa_neg_into_sa::<VARANGE, REDUCE>, a, CHUNK);
237 }
238
239 #[inline(always)]
240 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
241 &self,
242 a: &[u64],
243 b: &mut [u64],
244 ) {
245 apply_vv!(self, Self::sa_neg_into_sb::<VARANGE, REDUCE>, a, b, CHUNK);
246 }
247
248 #[inline(always)]
249 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
250 &self,
251 a: &[u64],
252 b: &mut [Montgomery<u64>],
253 ) {
254 apply_vv!(self, Self::sa_prep_mont_into_sb::<REDUCE>, a, b, CHUNK);
255 }
256
257 #[inline(always)]
258 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
259 &self,
260 a: &[Montgomery<u64>],
261 b: &[u64],
262 c: &mut [u64],
263 ) {
264 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
265 }
266
267 #[inline(always)]
268 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
269 &self,
270 a: &[Montgomery<u64>],
271 b: &mut [u64],
272 ) {
273 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
274 }
275
276 #[inline(always)]
277 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
278 &self,
279 a: &Barrett<u64>,
280 b: &[u64],
281 c: &mut [u64],
282 ) {
283 apply_svv!(
284 self,
285 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
286 a,
287 b,
288 c,
289 CHUNK
290 );
291 }
292
293 #[inline(always)]
294 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
295 &self,
296 a: &Barrett<u64>,
297 b: &mut [u64],
298 ) {
299 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
300 }
301
302 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
303 &self,
304 a: &[u64],
305 b: &[u64],
306 c: &Barrett<u64>,
307 d: &mut [u64],
308 ) {
309 apply_vvsv!(
310 self,
311 Self::sa_sub_sb_mul_sc_into_sd::<VBRANGE, REDUCE>,
312 a,
313 b,
314 c,
315 d,
316 CHUNK
317 );
318 }
319
320 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
321 &self,
322 a: &[u64],
323 b: &Barrett<u64>,
324 c: &mut [u64],
325 ) {
326 apply_vsv!(
327 self,
328 Self::sa_sub_sb_mul_sc_into_sb::<VBRANGE, REDUCE>,
329 a,
330 b,
331 c,
332 CHUNK
333 );
334 }
335
336 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
337 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
338 &self,
339 b: &u64,
340 c: &Barrett<u64>,
341 a: &mut [u64],
342 ) {
343 apply_ssv!(
344 self,
345 Self::sa_add_sb_mul_sc_into_sa::<REDUCE>,
346 b,
347 c,
348 a,
349 CHUNK
350 );
351 }
352
353 // vec(a) <- (vec(a) + scalar(b)) * scalar(c);
354 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
355 &self,
356 a: &[u64],
357 b: &u64,
358 c: &Barrett<u64>,
359 d: &mut [u64],
360 ) {
361 apply_vssv!(
362 self,
363 Self::sa_add_sb_mul_sc_into_sd::<REDUCE>,
364 a,
365 b,
366 c,
367 d,
368 CHUNK
369 );
370 }
371}