poulpy/math/src/modulus.rs
math/src/modulus.rsRaw
1pub mod barrett;
2pub mod impl_u64;
3pub mod montgomery;
4pub mod prime;
5
6pub type REDUCEMOD = u8;
7
8pub const NONE: REDUCEMOD = 0;
9pub const ONCE: REDUCEMOD = 1;
10pub const TWICE: REDUCEMOD = 2;
11pub const FOURTIMES: REDUCEMOD = 3;
12pub const BARRETT: REDUCEMOD = 4;
13pub const BARRETTLAZY: REDUCEMOD = 5;
14
15pub trait WordOps<O> {
16 fn log2(self) -> O;
17 fn reverse_bits_msb(self, n: u32) -> O;
18 fn mask(self) -> O;
19}
20
21impl WordOps<u64> for u64 {
22 #[inline(always)]
23 fn log2(self) -> u64 {
24 (u64::BITS - (self - 1).leading_zeros()) as _
25 }
26 #[inline(always)]
27 fn reverse_bits_msb(self, n: u32) -> u64 {
28 self.reverse_bits() >> (usize::BITS - n)
29 }
30 #[inline(always)]
31 fn mask(self) -> u64 {
32 (1 << self.log2()) - 1
33 }
34}
35
36impl WordOps<usize> for usize {
37 #[inline(always)]
38 fn log2(self) -> usize {
39 (usize::BITS - (self - 1).leading_zeros()) as _
40 }
41 #[inline(always)]
42 fn reverse_bits_msb(self, n: u32) -> usize {
43 self.reverse_bits() >> (usize::BITS - n)
44 }
45 #[inline(always)]
46 fn mask(self) -> usize {
47 (1 << self.log2()) - 1
48 }
49}
50
51pub trait ReduceOnce<O> {
52 /// Assigns self-q to self if self >= q in constant time.
53 /// User must ensure that 2q fits in O.
54 fn reduce_once_constant_time_assign(&mut self, q: O);
55 /// Returns self-q if self >= q else self in constant time.
56 /// /// User must ensure that 2q fits in O.
57 fn reduce_once_constant_time(&self, q: O) -> O;
58 /// Assigns self-q to self if self >= q.
59 /// /// User must ensure that 2q fits in O.
60 fn reduce_once_assign(&mut self, q: O);
61 /// Returns self-q if self >= q else self.
62 /// /// User must ensure that 2q fits in O.
63 fn reduce_once(&self, q: O) -> O;
64}
65
66pub trait ScalarOperations<O> {
67 // Applies a parameterized modular reduction.
68 fn sa_reduce_into_sa<const REDUCE: REDUCEMOD>(&self, x: &mut O);
69
70 // Assigns a + b to c.
71 fn sa_add_sb_into_sc<const REDUCE: REDUCEMOD>(&self, a: &O, b: &O, c: &mut O);
72
73 // Assigns a + b to b.
74 fn sa_add_sb_into_sb<const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
75
76 // Assigns a - b to c.
77 fn sa_sub_sb_into_sc<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
78 &self,
79 a: &O,
80 b: &O,
81 c: &mut O,
82 );
83
84 // Assigns a - b to b.
85 fn sa_sub_sb_into_sb<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
86
87 // Assigns a - b to a.
88 fn sa_sub_sb_into_sa<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, b: &O, a: &mut O);
89
90 // Assigns -a to a.
91 fn sa_neg_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut O);
92
93 // Assigns -a to b.
94 fn sa_neg_into_sb<const SARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut O);
95
96 // Assigns a * 2^64 to a.
97 fn sa_prepare_montgomery_into_sa<const REDUCE: REDUCEMOD>(
98 &self,
99 a: &mut montgomery::Montgomery<O>,
100 );
101
102 // Assigns a * 2^64 to b.
103 fn sa_prepare_montgomery_into_sb<const REDUCE: REDUCEMOD>(
104 &self,
105 a: &O,
106 b: &mut montgomery::Montgomery<O>,
107 );
108
109 // Assigns a * b to c.
110 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
111 &self,
112 a: &montgomery::Montgomery<O>,
113 b: &O,
114 c: &mut O,
115 );
116
117 // Assigns a * b to b.
118 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(
119 &self,
120 a: &montgomery::Montgomery<O>,
121 b: &mut O,
122 );
123
124 // Assigns a * b to c.
125 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
126 &self,
127 a: &barrett::Barrett<O>,
128 b: &O,
129 c: &mut O,
130 );
131
132 // Assigns a * b to b.
133 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(
134 &self,
135 a: &barrett::Barrett<O>,
136 b: &mut O,
137 );
138
139 // Assigns (a + q - b) * c to d.
140 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
141 &self,
142 a: &O,
143 b: &O,
144 c: &barrett::Barrett<O>,
145 d: &mut O,
146 );
147
148 // Assigns (a + q - b) * c to b.
149 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
150 &self,
151 a: &u64,
152 c: &barrett::Barrett<u64>,
153 b: &mut u64,
154 );
155
156 // Assigns (a + b) * c to a.
157 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
158 &self,
159 b: &u64,
160 c: &barrett::Barrett<u64>,
161 a: &mut u64,
162 );
163
164 // Assigns (a + b) * c to d.
165 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
166 &self,
167 a: &u64,
168 b: &u64,
169 c: &barrett::Barrett<u64>,
170 d: &mut u64,
171 );
172
173 // Assigns (a - b + c) * d to e.
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::Barrett<u64>,
180 e: &mut u64,
181 );
182
183 fn sb_sub_sa_add_sc_mul_sd_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
184 &self,
185 b: &u64,
186 c: &u64,
187 d: &barrett::Barrett<u64>,
188 a: &mut u64,
189 );
190}
191
192pub trait VectorOperations<O> {
193 // Applies a parameterized modular reduction.
194 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, x: &mut [O]);
195
196 // ADD
197 // vec(c) <- vec(a) + vec(b).
198 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
199 &self,
200 va: &[O],
201 vb: &[O],
202 vc: &mut [O],
203 );
204
205 // vec(b) <- vec(a) + vec(b).
206 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &[O], b: &mut [O]);
207
208 // vec(c) <- vec(a) + scalar(b).
209 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
210 &self,
211 a: &[O],
212 b: &O,
213 c: &mut [O],
214 );
215
216 // vec(b) <- vec(b) + scalar(a).
217 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut [O]);
218
219 // vec(b) <- vec(a) - vec(b).
220 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
221 &self,
222 a: &[O],
223 b: &mut [O],
224 );
225
226 // vec(a) <- vec(a) - vec(b).
227 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
228 &self,
229 b: &[O],
230 a: &mut [O],
231 );
232
233 // vec(c) <- vec(a) - vec(b).
234 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
235 &self,
236 a: &[O],
237 b: &[O],
238 c: &mut [O],
239 );
240
241 // vec(a) <- -vec(a).
242 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
243 &self,
244 a: &mut [O],
245 );
246
247 // vec(b) <- -vec(a).
248 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
249 &self,
250 a: &[O],
251 b: &mut [O],
252 );
253
254 // vec(b) <- vec(a)
255 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
256 &self,
257 a: &[O],
258 b: &mut [montgomery::Montgomery<O>],
259 );
260
261 // vec(a) <- vec(a).
262 fn va_prepare_montgomery_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
263 &self,
264 a: &mut [montgomery::Montgomery<O>],
265 );
266
267 // vec(c) <- vec(a) * vec(b).
268 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
269 &self,
270 a: &[montgomery::Montgomery<O>],
271 b: &[O],
272 c: &mut [O],
273 );
274
275 // vec(b) <- vec(a) * vec(b).
276 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
277 &self,
278 a: &[montgomery::Montgomery<O>],
279 b: &mut [O],
280 );
281
282 // vec(b) <- vec(b) * scalar(a).
283 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
284 &self,
285 a: &barrett::Barrett<u64>,
286 b: &mut [u64],
287 );
288
289 // vec(c) <- vec(b) * scalar(a).
290 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
291 &self,
292 a: &barrett::Barrett<u64>,
293 b: &[u64],
294 c: &mut [u64],
295 );
296
297 // vec(d) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
298 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
299 &self,
300 a: &[u64],
301 b: &[u64],
302 c: &barrett::Barrett<u64>,
303 d: &mut [u64],
304 );
305
306 // vec(b) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
307 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
308 &self,
309 a: &[u64],
310 c: &barrett::Barrett<u64>,
311 b: &mut [u64],
312 );
313
314 // vec(c) <- (vec(a) + scalar(b)) * scalar(c).
315 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
316 &self,
317 va: &[u64],
318 sb: &u64,
319 sc: &barrett::Barrett<u64>,
320 vd: &mut [u64],
321 );
322
323 // vec(a) <- (vec(a) + scalar(b)) * scalar(c).
324 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
325 &self,
326 sb: &u64,
327 sc: &barrett::Barrett<u64>,
328 va: &mut [u64],
329 );
330
331 // vec(e) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
332 fn vb_sub_va_add_sc_mul_sd_into_ve<
333 const CHUNK: usize,
334 const VBRANGE: u8,
335 const REDUCE: REDUCEMOD,
336 >(
337 &self,
338 va: &[u64],
339 vb: &[u64],
340 sc: &u64,
341 sd: &barrett::Barrett<u64>,
342 ve: &mut [u64],
343 );
344
345 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
346 fn vb_sub_va_add_sc_mul_sd_into_va<
347 const CHUNK: usize,
348 const VBRANGE: u8,
349 const REDUCE: REDUCEMOD,
350 >(
351 &self,
352 vb: &[u64],
353 sc: &u64,
354 sd: &barrett::Barrett<u64>,
355 va: &mut [u64],
356 );
357}