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 b.
97 fn sa_prep_mont_into_sb<const REDUCE: REDUCEMOD>(
98 &self,
99 a: &O,
100 b: &mut montgomery::Montgomery<O>,
101 );
102
103 // Assigns a * b to c.
104 fn sa_mont_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
105 &self,
106 a: &montgomery::Montgomery<O>,
107 b: &O,
108 c: &mut O,
109 );
110
111 // Assigns a * b to b.
112 fn sa_mont_mul_sb_into_sb<const REDUCE: REDUCEMOD>(
113 &self,
114 a: &montgomery::Montgomery<O>,
115 b: &mut O,
116 );
117
118 // Assigns a * b to c.
119 fn sa_barrett_mul_sb_into_sc<const REDUCE: REDUCEMOD>(
120 &self,
121 a: &barrett::Barrett<O>,
122 b: &O,
123 c: &mut O,
124 );
125
126 // Assigns a * b to b.
127 fn sa_barrett_mul_sb_into_sb<const REDUCE: REDUCEMOD>(
128 &self,
129 a: &barrett::Barrett<O>,
130 b: &mut O,
131 );
132
133 // Assigns (a + q - b) * c to d.
134 fn sa_sub_sb_mul_sc_into_sd<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
135 &self,
136 a: &O,
137 b: &O,
138 c: &barrett::Barrett<O>,
139 d: &mut O,
140 );
141
142 // Assigns (a + q - b) * c to b.
143 fn sa_sub_sb_mul_sc_into_sb<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
144 &self,
145 a: &u64,
146 c: &barrett::Barrett<u64>,
147 b: &mut u64,
148 );
149
150 // Assigns (a + b) * c to a.
151 fn sa_add_sb_mul_sc_into_sa<const REDUCE: REDUCEMOD>(
152 &self,
153 b: &u64,
154 c: &barrett::Barrett<u64>,
155 a: &mut u64,
156 );
157
158 // Assigns (a + b) * c to d.
159 fn sa_add_sb_mul_sc_into_sd<const REDUCE: REDUCEMOD>(
160 &self,
161 a: &u64,
162 b: &u64,
163 c: &barrett::Barrett<u64>,
164 d: &mut u64,
165 );
166
167 // Assigns (a - b + c) * d to e.
168 fn sb_sub_sa_add_sc_mul_sd_into_se<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
169 &self,
170 a: &u64,
171 b: &u64,
172 c: &u64,
173 d: &barrett::Barrett<u64>,
174 e: &mut u64,
175 );
176
177 fn sb_sub_sa_add_sc_mul_sd_into_sa<const SBRANGE: u8, const REDUCE: REDUCEMOD>(
178 &self,
179 b: &u64,
180 c: &u64,
181 d: &barrett::Barrett<u64>,
182 a: &mut u64,
183 );
184}
185
186pub trait VectorOperations<O> {
187 // Applies a parameterized modular reduction.
188 fn va_reduce_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, x: &mut [O]);
189
190 // ADD
191 // vec(c) <- vec(a) + vec(b).
192 fn va_add_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
193 &self,
194 va: &[O],
195 vb: &[O],
196 vc: &mut [O],
197 );
198
199 // vec(b) <- vec(a) + vec(b).
200 fn va_add_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &[O], b: &mut [O]);
201
202 // vec(c) <- vec(a) + scalar(b).
203 fn va_add_sb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
204 &self,
205 a: &[O],
206 b: &O,
207 c: &mut [O],
208 );
209
210 // vec(b) <- vec(b) + scalar(a).
211 fn va_add_sb_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(&self, a: &O, b: &mut [O]);
212
213 // vec(b) <- vec(a) - vec(b).
214 fn va_sub_vb_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
215 &self,
216 a: &[O],
217 b: &mut [O],
218 );
219
220 // vec(a) <- vec(a) - vec(b).
221 fn va_sub_vb_into_va<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
222 &self,
223 b: &[O],
224 a: &mut [O],
225 );
226
227 // vec(c) <- vec(a) - vec(b).
228 fn va_sub_vb_into_vc<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
229 &self,
230 a: &[O],
231 b: &[O],
232 c: &mut [O],
233 );
234
235 // vec(a) <- -vec(a).
236 fn va_neg_into_va<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
237 &self,
238 a: &mut [O],
239 );
240
241 // vec(b) <- -vec(a).
242 fn va_neg_into_vb<const CHUNK: usize, const VARANGE: u8, const REDUCE: REDUCEMOD>(
243 &self,
244 a: &[O],
245 b: &mut [O],
246 );
247
248 // vec(b) <- vec(a)
249 fn va_prep_mont_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
250 &self,
251 a: &[O],
252 b: &mut [montgomery::Montgomery<O>],
253 );
254
255 // vec(c) <- vec(a) * vec(b).
256 fn va_mont_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
257 &self,
258 a: &[montgomery::Montgomery<O>],
259 b: &[O],
260 c: &mut [O],
261 );
262
263 // vec(b) <- vec(a) * vec(b).
264 fn va_mont_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
265 &self,
266 a: &[montgomery::Montgomery<O>],
267 b: &mut [O],
268 );
269
270 // vec(b) <- vec(b) * scalar(a).
271 fn sa_barrett_mul_vb_into_vb<const CHUNK: usize, const REDUCE: REDUCEMOD>(
272 &self,
273 a: &barrett::Barrett<u64>,
274 b: &mut [u64],
275 );
276
277 // vec(c) <- vec(b) * scalar(a).
278 fn sa_barrett_mul_vb_into_vc<const CHUNK: usize, const REDUCE: REDUCEMOD>(
279 &self,
280 a: &barrett::Barrett<u64>,
281 b: &[u64],
282 c: &mut [u64],
283 );
284
285 // vec(d) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
286 fn va_sub_vb_mul_sc_into_vd<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
287 &self,
288 a: &[u64],
289 b: &[u64],
290 c: &barrett::Barrett<u64>,
291 d: &mut [u64],
292 );
293
294 // vec(b) <- (vec(a) + VBRANGE * q - vec(b)) * scalar(c).
295 fn va_sub_vb_mul_sc_into_vb<const CHUNK: usize, const VBRANGE: u8, const REDUCE: REDUCEMOD>(
296 &self,
297 a: &[u64],
298 c: &barrett::Barrett<u64>,
299 b: &mut [u64],
300 );
301
302 // vec(c) <- (vec(a) + scalar(b)) * scalar(c).
303 fn va_add_sb_mul_sc_into_vd<const CHUNK: usize, const REDUCE: REDUCEMOD>(
304 &self,
305 va: &[u64],
306 sb: &u64,
307 sc: &barrett::Barrett<u64>,
308 vd: &mut [u64],
309 );
310
311 // vec(a) <- (vec(a) + scalar(b)) * scalar(c).
312 fn va_add_sb_mul_sc_into_va<const CHUNK: usize, const REDUCE: REDUCEMOD>(
313 &self,
314 sb: &u64,
315 sc: &barrett::Barrett<u64>,
316 va: &mut [u64],
317 );
318
319 // vec(e) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
320 fn vb_sub_va_add_sc_mul_sd_into_ve<
321 const CHUNK: usize,
322 const VBRANGE: u8,
323 const REDUCE: REDUCEMOD,
324 >(
325 &self,
326 va: &[u64],
327 vb: &[u64],
328 sc: &u64,
329 sd: &barrett::Barrett<u64>,
330 ve: &mut [u64],
331 );
332
333 // vec(a) <- (vec(b) - vec(a) + scalar(c)) * scalar(e).
334 fn vb_sub_va_add_sc_mul_sd_into_va<
335 const CHUNK: usize,
336 const VBRANGE: u8,
337 const REDUCE: REDUCEMOD,
338 >(
339 &self,
340 vb: &[u64],
341 sc: &u64,
342 sd: &barrett::Barrett<u64>,
343 va: &mut [u64],
344 );
345}