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