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