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::ReduceOnce;
5use crate::modulus::REDUCEMOD;
6use crate::modulus::{ScalarOperations, VectorOperations};
7use crate::{apply_sv, apply_svv, apply_v, apply_vsv, apply_vv, apply_vvsv, apply_vvv};
8use itertools::izip;
9
10impl ScalarOperations<u64> for Prime<u64> {
11 /// Applies a modular reduction on x based on REDUCE:
12 /// - LAZY: no modular reduction.
13 /// - ONCE: subtracts q if x >= q.
14 /// - TWO: subtracts 2q if x >= 2q.
15 /// - FOUR: subtracts 4q if x >= 4q.
16 /// - BARRETT: maps x to x mod q using Barrett reduction.
17 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
18 #[inline(always)]
19 fn sa_reduce_into_sa<const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
20 self.montgomery.reduce_assign::<REDUCE>(a);
21 }
22
23 #[inline(always)]
24 fn sa_add_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &u64, c: &mut u64) {
25 *c = a.wrapping_add(*b);
26 self.sa_reduce_into_sa::<REDUCE>(c);
27 }
28
29 #[inline(always)]
30 fn sa_add_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
31 *b = a.wrapping_add(*b);
32 self.sa_reduce_into_sa::<REDUCE>(b);
33 }
34
35 #[inline(always)]
36 fn sa_sub_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &u64, c: &mut u64) {
37 *c = a.wrapping_add(self.q.wrapping_sub(*b)).reduce_once(self.q);
38 }
39
40 #[inline(always)]
41 fn sa_sub_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
42 *b = a.wrapping_add(self.q.wrapping_sub(*b)).reduce_once(self.q);
43 }
44
45 #[inline(always)]
46 fn sa_neg_into_sa<const REDUCE: REDUCEMOD>(&self, a: &mut u64) {
47 *a = self.q.wrapping_sub(*a);
48 self.sa_reduce_into_sa::<REDUCE>(a)
49 }
50
51 #[inline(always)]
52 fn sa_neg_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut u64) {
53 *b = self.q.wrapping_sub(*a);
54 self.sa_reduce_into_sa::<REDUCE>(b)
55 }
56
57 #[inline(always)]
58 fn sa_prep_mont_into_sb<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut Montgomery<u64>) {
59 self.montgomery.prepare_assign::<REDUCE>(*a, b);
60 }
61
62 #[inline(always)]
63 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
64 &self,
65 a: &Montgomery<u64>,
66 b: &u64,
67 c: &mut u64,
68 ) {
69 *c = self.montgomery.mul_external::<REDUCE>(*a, *b);
70 }
71
72 #[inline(always)]
73 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Montgomery<u64>, b: &mut u64) {
74 self.montgomery.mul_external_assign::<REDUCE>(*a, b);
75 }
76
77 #[inline(always)]
78 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
79 &self,
80 a: &Barrett<u64>,
81 b: &u64,
82 c: &mut u64,
83 ) {
84 *c = self.barrett.mul_external::<REDUCE>(*a, *b);
85 }
86
87 #[inline(always)]
88 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &Barrett<u64>, b: &mut u64) {
89 self.barrett.mul_external_assign::<REDUCE>(*a, b);
90 }
91
92 #[inline(always)]
93 fn sa_sub_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
94 &self,
95 a: &u64,
96 b: &u64,
97 c: &Barrett<u64>,
98 d: &mut u64,
99 ) {
100 *d = self.two_q.wrapping_sub(*b).wrapping_add(*a);
101 self.barrett.mul_external_assign::<REDUCE>(*c, d);
102 }
103
104 #[inline(always)]
105 fn sa_sub_sb_mul_sc_into_sb<const REDUCE: REDUCEMOD>(
106 &self,
107 a: &u64,
108 c: &Barrett<u64>,
109 b: &mut u64,
110 ) {
111 *b = self.two_q.wrapping_sub(*b).wrapping_add(*a);
112 self.barrett.mul_external_assign::<REDUCE>(*c, b);
113 }
114}
115
116impl VectorOperations<u64> for Prime<u64> {
117 /// Applies a modular reduction on x based on REDUCE:
118 /// - LAZY: no modular reduction.
119 /// - ONCE: subtracts q if x >= q.
120 /// - TWO: subtracts 2q if x >= 2q.
121 /// - FOUR: subtracts 4q if x >= 4q.
122 /// - BARRETT: maps x to x mod q using Barrett reduction.
123 /// - BARRETTLAZY: maps x to x mod q using Barrett reduction with values in [0, 2q-1].
124 #[inline(always)]
125 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
126 apply_v!(self, Self::sa_reduce_into_sa::<REDUCE>, a, CHUNK);
127 }
128
129 #[inline(always)]
130 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
131 &self,
132 a: &[u64],
133 b: &[u64],
134 c: &mut [u64],
135 ) {
136 apply_vvv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
137 }
138
139 #[inline(always)]
140 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
141 &self,
142 a: &[u64],
143 b: &mut [u64],
144 ) {
145 apply_vv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
146 }
147
148 #[inline(always)]
149 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
150 &self,
151 a: &[u64],
152 b: &u64,
153 c: &mut [u64],
154 ) {
155 apply_vsv!(self, Self::sa_add_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
156 }
157
158 #[inline(always)]
159 fn sa_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
160 &self,
161 a: &u64,
162 b: &mut [u64],
163 ) {
164 apply_sv!(self, Self::sa_add_sb_into_sb::<REDUCE>, a, b, CHUNK);
165 }
166
167 #[inline(always)]
168 fn va_sub_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
169 &self,
170 a: &[u64],
171 b: &[u64],
172 c: &mut [u64],
173 ) {
174 apply_vvv!(self, Self::sa_sub_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
175 }
176
177 #[inline(always)]
178 fn va_sub_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
179 &self,
180 a: &[u64],
181 b: &mut [u64],
182 ) {
183 apply_vv!(self, Self::sa_sub_sb_into_sb::<REDUCE>, a, b, CHUNK);
184 }
185
186 #[inline(always)]
187 fn va_neg_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &mut [u64]) {
188 apply_v!(self, Self::sa_neg_into_sa::<REDUCE>, a, CHUNK);
189 }
190
191 #[inline(always)]
192 fn va_neg_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
193 &self,
194 a: &[u64],
195 b: &mut [u64],
196 ) {
197 apply_vv!(self, Self::sa_neg_into_sb::<REDUCE>, a, b, CHUNK);
198 }
199
200 #[inline(always)]
201 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
202 &self,
203 a: &[u64],
204 b: &mut [Montgomery<u64>],
205 ) {
206 apply_vv!(self, Self::sa_prep_mont_into_sb::<REDUCE>, a, b, CHUNK);
207 }
208
209 #[inline(always)]
210 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
211 &self,
212 a: &[Montgomery<u64>],
213 b: &[u64],
214 c: &mut [u64],
215 ) {
216 apply_vvv!(self, Self::sa_mont_mul_sb_into_sc::<REDUCE>, a, b, c, CHUNK);
217 }
218
219 #[inline(always)]
220 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
221 &self,
222 a: &[Montgomery<u64>],
223 b: &mut [u64],
224 ) {
225 apply_vv!(self, Self::sa_mont_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
226 }
227
228 #[inline(always)]
229 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
230 &self,
231 a: &Barrett<u64>,
232 b: &[u64],
233 c: &mut [u64],
234 ) {
235 apply_svv!(
236 self,
237 Self::sa_barrett_mul_sb_into_sc::<REDUCE>,
238 a,
239 b,
240 c,
241 CHUNK
242 );
243 }
244
245 #[inline(always)]
246 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
247 &self,
248 a: &Barrett<u64>,
249 b: &mut [u64],
250 ) {
251 apply_sv!(self, Self::sa_barrett_mul_sb_into_sb::<REDUCE>, a, b, CHUNK);
252 }
253
254 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
255 &self,
256 a: &[u64],
257 b: &[u64],
258 c: &Barrett<u64>,
259 d: &mut [u64],
260 ) {
261 apply_vvsv!(
262 self,
263 Self::sa_sub_sb_mul_sc_into_sd::<REDUCE>,
264 a,
265 b,
266 c,
267 d,
268 CHUNK
269 );
270 }
271
272 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
273 &self,
274 a: &[u64],
275 b: &Barrett<u64>,
276 c: &mut [u64],
277 ) {
278 apply_vsv!(
279 self,
280 Self::sa_sub_sb_mul_sc_into_sb::<REDUCE>,
281 a,
282 b,
283 c,
284 CHUNK
285 );
286 }
287}