poulpy/math/src/ring/impl_u64/ring.rs
math/src/ring/impl_u64/ring.rsRaw
1use crate::dft::ntt::Table;
2use crate::modulus::barrett::Barrett;
3use crate::modulus::montgomery::Montgomery;
4use crate::modulus::prime::Prime;
5use crate::modulus::VectorOperations;
6use crate::modulus::{BARRETT, REDUCEMOD};
7use crate::poly::Poly;
8use crate::ring::Ring;
9use crate::CHUNK;
10use crate::GALOISGENERATOR;
11use num_bigint::BigInt;
12use num_traits::ToPrimitive;
13
14impl Ring<u64> {
15 pub fn new(n: usize, q_base: u64, q_power: usize) -> Self {
16 let prime: Prime<u64> = Prime::<u64>::new(q_base, q_power);
17 Self {
18 n: n,
19 modulus: prime.clone(),
20 dft: Box::new(Table::<u64>::new(prime, n << 1)),
21 }
22 }
23
24 pub fn from_bigint(&self, coeffs: &[BigInt], step: usize, a: &mut Poly<u64>) {
25 assert!(
26 step <= a.n(),
27 "invalid step: step={} > a.n()={}",
28 step,
29 a.n()
30 );
31 assert!(
32 coeffs.len() <= a.n() / step,
33 "invalid coeffs: coeffs.len()={} > a.n()/step={}",
34 coeffs.len(),
35 a.n() / step
36 );
37 let q_big: BigInt = BigInt::from(self.modulus.q);
38 a.0.iter_mut()
39 .step_by(step)
40 .enumerate()
41 .for_each(|(i, v)| *v = (&coeffs[i] % &q_big).to_u64().unwrap());
42 }
43
44 // Returns GALOISGENERATOR^gen_1 * (-1)^gen_2 mod 2^log_nth_root.
45 pub fn galois_element(&self, gen_1: usize, gen_2: bool, log_nth_root: usize) -> usize {
46 let mut gal_el: usize = 1;
47 let mut gen_1_pow: usize = GALOISGENERATOR;
48 let mut e: usize = gen_1;
49 while e > 0 {
50 if e & 1 == 1 {
51 gal_el = gal_el.wrapping_mul(gen_1_pow);
52 }
53
54 gen_1_pow = gen_1_pow.wrapping_mul(gen_1_pow);
55 e >>= 1;
56 }
57
58 let nth_root = 1 << log_nth_root;
59 gal_el &= nth_root - 1;
60
61 if gen_2 {
62 return nth_root - gal_el;
63 }
64 gal_el
65 }
66}
67
68impl Ring<u64> {
69 pub fn ntt_inplace<const LAZY: bool>(&self, poly: &mut Poly<u64>) {
70 match LAZY {
71 true => self.dft.forward_inplace_lazy(&mut poly.0),
72 false => self.dft.forward_inplace(&mut poly.0),
73 }
74 }
75
76 pub fn intt_inplace<const LAZY: bool>(&self, poly: &mut Poly<u64>) {
77 match LAZY {
78 true => self.dft.backward_inplace_lazy(&mut poly.0),
79 false => self.dft.backward_inplace(&mut poly.0),
80 }
81 }
82
83 pub fn ntt<const LAZY: bool>(&self, poly_in: &Poly<u64>, poly_out: &mut Poly<u64>) {
84 poly_out.0.copy_from_slice(&poly_in.0);
85 match LAZY {
86 true => self.dft.forward_inplace_lazy(&mut poly_out.0),
87 false => self.dft.forward_inplace(&mut poly_out.0),
88 }
89 }
90
91 pub fn intt<const LAZY: bool>(&self, poly_in: &Poly<u64>, poly_out: &mut Poly<u64>) {
92 poly_out.0.copy_from_slice(&poly_in.0);
93 match LAZY {
94 true => self.dft.backward_inplace_lazy(&mut poly_out.0),
95 false => self.dft.backward_inplace(&mut poly_out.0),
96 }
97 }
98}
99
100impl Ring<u64> {
101 #[inline(always)]
102 pub fn a_add_b_into_b<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>) {
103 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
104 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
105 self.modulus
106 .va_add_vb_into_vb::<CHUNK, REDUCE>(&a.0, &mut b.0);
107 }
108
109 #[inline(always)]
110 pub fn a_add_b_into_c<const REDUCE: REDUCEMOD>(
111 &self,
112 a: &Poly<u64>,
113 b: &Poly<u64>,
114 c: &mut Poly<u64>,
115 ) {
116 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
117 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
118 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
119 self.modulus
120 .va_add_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
121 }
122
123 #[inline(always)]
124 pub fn a_add_b_scalar_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut Poly<u64>) {
125 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
126 self.modulus.va_add_sb_into_va::<CHUNK, REDUCE>(b, &mut a.0);
127 }
128
129 #[inline(always)]
130 pub fn a_add_b_scalar_into_c<const REDUCE: REDUCEMOD>(
131 &self,
132 a: &Poly<u64>,
133 b: &u64,
134 c: &mut Poly<u64>,
135 ) {
136 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
137 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
138 self.modulus
139 .va_add_sb_into_vc::<CHUNK, REDUCE>(&a.0, b, &mut c.0);
140 }
141
142 #[inline(always)]
143 pub fn a_add_scalar_b_mul_c_scalar_barrett_into_a<const REDUCE: REDUCEMOD>(
144 &self,
145 b: &u64,
146 c: &Barrett<u64>,
147 a: &mut Poly<u64>,
148 ) {
149 debug_assert!(a.n() == self.n(), "b.n()={} != n={}", a.n(), self.n());
150 self.modulus
151 .va_add_sb_mul_sc_into_va::<CHUNK, REDUCE>(b, c, &mut a.0);
152 }
153
154 #[inline(always)]
155 pub fn add_scalar_then_mul_scalar_barrett<const REDUCE: REDUCEMOD>(
156 &self,
157 a: &Poly<u64>,
158 b: &u64,
159 c: &Barrett<u64>,
160 d: &mut Poly<u64>,
161 ) {
162 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
163 debug_assert!(d.n() == self.n(), "c.n()={} != n={}", d.n(), self.n());
164 self.modulus
165 .va_add_sb_mul_sc_into_vd::<CHUNK, REDUCE>(&a.0, b, c, &mut d.0);
166 }
167
168 #[inline(always)]
169 pub fn a_sub_b_into_b<const BRANGE: u8, const REDUCE: REDUCEMOD>(
170 &self,
171 a: &Poly<u64>,
172 b: &mut Poly<u64>,
173 ) {
174 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
175 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
176 self.modulus
177 .va_sub_vb_into_vb::<CHUNK, BRANGE, REDUCE>(&a.0, &mut b.0);
178 }
179
180 #[inline(always)]
181 pub fn a_sub_b_into_a<const BRANGE: u8, const REDUCE: REDUCEMOD>(
182 &self,
183 b: &Poly<u64>,
184 a: &mut Poly<u64>,
185 ) {
186 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
187 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
188 self.modulus
189 .va_sub_vb_into_va::<CHUNK, BRANGE, REDUCE>(&b.0, &mut a.0);
190 }
191
192 #[inline(always)]
193 pub fn a_sub_b_into_c<const BRANGE: u8, const REDUCE: REDUCEMOD>(
194 &self,
195 a: &Poly<u64>,
196 b: &Poly<u64>,
197 c: &mut Poly<u64>,
198 ) {
199 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
200 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
201 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
202 self.modulus
203 .va_sub_vb_into_vc::<CHUNK, BRANGE, REDUCE>(&a.0, &b.0, &mut c.0);
204 }
205
206 #[inline(always)]
207 pub fn a_neg_into_b<const ARANGE: u8, const REDUCE: REDUCEMOD>(
208 &self,
209 a: &Poly<u64>,
210 b: &mut Poly<u64>,
211 ) {
212 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
213 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
214 self.modulus
215 .va_neg_into_vb::<CHUNK, ARANGE, REDUCE>(&a.0, &mut b.0);
216 }
217
218 #[inline(always)]
219 pub fn a_neg_into_a<const ARANGE: u8, const REDUCE: REDUCEMOD>(&self, a: &mut Poly<u64>) {
220 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
221 self.modulus
222 .va_neg_into_va::<CHUNK, ARANGE, REDUCE>(&mut a.0);
223 }
224
225 #[inline(always)]
226 pub fn a_prepare_montgomery_into_a<const REDUCE: REDUCEMOD>(
227 &self,
228 a: &mut Poly<Montgomery<u64>>,
229 ) {
230 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
231 self.modulus
232 .va_prepare_montgomery_into_va::<CHUNK, REDUCE>(&mut a.0);
233 }
234
235 #[inline(always)]
236 pub fn a_mul_b_montgomery_into_c<const REDUCE: REDUCEMOD>(
237 &self,
238 a: &Poly<Montgomery<u64>>,
239 b: &Poly<u64>,
240 c: &mut Poly<u64>,
241 ) {
242 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
243 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
244 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
245 self.modulus
246 .va_mont_mul_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
247 }
248
249 #[inline(always)]
250 pub fn a_mul_b_montgomery_into_a<const REDUCE: REDUCEMOD>(
251 &self,
252 b: &Poly<Montgomery<u64>>,
253 a: &mut Poly<u64>,
254 ) {
255 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
256 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
257 self.modulus
258 .va_mont_mul_vb_into_vb::<CHUNK, REDUCE>(&b.0, &mut a.0);
259 }
260
261 #[inline(always)]
262 pub fn a_mul_b_scalar_into_c<const REDUCE: REDUCEMOD>(
263 &self,
264 a: &Poly<u64>,
265 b: &u64,
266 c: &mut Poly<u64>,
267 ) {
268 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
269 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
270 self.modulus.sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(
271 &self.modulus.barrett.prepare(*b),
272 &a.0,
273 &mut c.0,
274 );
275 }
276
277 #[inline(always)]
278 pub fn a_mul_b_scalar_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut Poly<u64>) {
279 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
280 self.modulus.sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(
281 &self
282 .modulus
283 .barrett
284 .prepare(self.modulus.barrett.reduce::<BARRETT>(b)),
285 &mut a.0,
286 );
287 }
288
289 #[inline(always)]
290 pub fn a_mul_b_scalar_barrett_into_a<const REDUCE: REDUCEMOD>(
291 &self,
292 b: &Barrett<u64>,
293 a: &mut Poly<u64>,
294 ) {
295 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
296 self.modulus
297 .sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(b, &mut a.0);
298 }
299
300 #[inline(always)]
301 pub fn a_mul_b_scalar_barrett_into_c<const REDUCE: REDUCEMOD>(
302 &self,
303 a: &Barrett<u64>,
304 b: &Poly<u64>,
305 c: &mut Poly<u64>,
306 ) {
307 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
308 self.modulus
309 .sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(a, &b.0, &mut c.0);
310 }
311
312 #[inline(always)]
313 pub fn a_sub_b_mul_c_scalar_barrett_into_d<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
314 &self,
315 a: &Poly<u64>,
316 b: &Poly<u64>,
317 c: &Barrett<u64>,
318 d: &mut Poly<u64>,
319 ) {
320 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
321 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
322 debug_assert!(d.n() == self.n(), "d.n()={} != n={}", d.n(), self.n());
323 self.modulus
324 .va_sub_vb_mul_sc_into_vd::<CHUNK, VBRANGE, REDUCE>(&a.0, &b.0, c, &mut d.0);
325 }
326
327 #[inline(always)]
328 pub fn b_sub_a_mul_c_scalar_barrett_into_a<const BRANGE: u8, const REDUCE: REDUCEMOD>(
329 &self,
330 b: &Poly<u64>,
331 c: &Barrett<u64>,
332 a: &mut Poly<u64>,
333 ) {
334 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
335 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
336 self.modulus
337 .va_sub_vb_mul_sc_into_vb::<CHUNK, BRANGE, REDUCE>(&b.0, c, &mut a.0);
338 }
339
340 #[inline(always)]
341 pub fn a_sub_b_add_c_scalar_mul_d_scalar_barrett_into_e<
342 const BRANGE: u8,
343 const REDUCE: REDUCEMOD,
344 >(
345 &self,
346 a: &Poly<u64>,
347 b: &Poly<u64>,
348 c: &u64,
349 d: &Barrett<u64>,
350 e: &mut Poly<u64>,
351 ) {
352 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
353 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
354 debug_assert!(e.n() == self.n(), "e.n()={} != n={}", e.n(), self.n());
355 self.modulus
356 .vb_sub_va_add_sc_mul_sd_into_ve::<CHUNK, BRANGE, REDUCE>(&a.0, &b.0, c, d, &mut e.0);
357 }
358
359 #[inline(always)]
360 pub fn b_sub_a_add_c_scalar_mul_d_scalar_barrett_into_a<
361 const BRANGE: u8,
362 const REDUCE: REDUCEMOD,
363 >(
364 &self,
365 b: &Poly<u64>,
366 c: &u64,
367 d: &Barrett<u64>,
368 a: &mut Poly<u64>,
369 ) {
370 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
371 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
372 self.modulus
373 .vb_sub_va_add_sc_mul_sd_into_va::<CHUNK, BRANGE, REDUCE>(&b.0, c, d, &mut a.0);
374 }
375}