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;
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>(&self, a: &mut Poly<Montgomery<u64>>){
227 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
228 self.modulus.va_prepare_montgomery_into_va::<CHUNK, REDUCE>(&mut a.0);
229 }
230
231 #[inline(always)]
232 pub fn a_mul_b_montgomery_into_c<const REDUCE: REDUCEMOD>(
233 &self,
234 a: &Poly<Montgomery<u64>>,
235 b: &Poly<u64>,
236 c: &mut Poly<u64>,
237 ) {
238 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
239 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
240 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
241 self.modulus
242 .va_mont_mul_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
243 }
244
245 #[inline(always)]
246 pub fn a_mul_b_montgomery_into_a<const REDUCE: REDUCEMOD>(
247 &self,
248 b: &Poly<Montgomery<u64>>,
249 a: &mut Poly<u64>,
250 ) {
251 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
252 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
253 self.modulus
254 .va_mont_mul_vb_into_vb::<CHUNK, REDUCE>(&b.0, &mut a.0);
255 }
256
257 #[inline(always)]
258 pub fn a_mul_b_scalar_into_c<const REDUCE: REDUCEMOD>(
259 &self,
260 a: &Poly<u64>,
261 b: &u64,
262 c: &mut Poly<u64>,
263 ) {
264 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
265 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
266 self.modulus.sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(
267 &self.modulus.barrett.prepare(*b),
268 &a.0,
269 &mut c.0,
270 );
271 }
272
273 #[inline(always)]
274 pub fn a_mul_b_scalar_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut Poly<u64>) {
275 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
276 self.modulus.sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(
277 &self
278 .modulus
279 .barrett
280 .prepare(self.modulus.barrett.reduce::<BARRETT>(b)),
281 &mut a.0,
282 );
283 }
284
285 #[inline(always)]
286 pub fn a_mul_b_scalar_barrett_into_a<const REDUCE: REDUCEMOD>(
287 &self,
288 b: &Barrett<u64>,
289 a: &mut Poly<u64>,
290 ) {
291 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
292 self.modulus
293 .sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(b, &mut a.0);
294 }
295
296 #[inline(always)]
297 pub fn a_mul_b_scalar_barrett_into_c<const REDUCE: REDUCEMOD>(
298 &self,
299 a: &Barrett<u64>,
300 b: &Poly<u64>,
301 c: &mut Poly<u64>,
302 ) {
303 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
304 self.modulus
305 .sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(a, &b.0, &mut c.0);
306 }
307
308 #[inline(always)]
309 pub fn a_sub_b_mul_c_scalar_barrett_into_d<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
310 &self,
311 a: &Poly<u64>,
312 b: &Poly<u64>,
313 c: &Barrett<u64>,
314 d: &mut Poly<u64>,
315 ) {
316 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
317 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
318 debug_assert!(d.n() == self.n(), "d.n()={} != n={}", d.n(), self.n());
319 self.modulus
320 .va_sub_vb_mul_sc_into_vd::<CHUNK, VBRANGE, REDUCE>(&a.0, &b.0, c, &mut d.0);
321 }
322
323 #[inline(always)]
324 pub fn b_sub_a_mul_c_scalar_barrett_into_a<const BRANGE: u8, const REDUCE: REDUCEMOD>(
325 &self,
326 b: &Poly<u64>,
327 c: &Barrett<u64>,
328 a: &mut Poly<u64>,
329 ) {
330 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
331 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
332 self.modulus
333 .va_sub_vb_mul_sc_into_vb::<CHUNK, BRANGE, REDUCE>(&b.0, c, &mut a.0);
334 }
335
336 #[inline(always)]
337 pub fn a_sub_b_add_c_scalar_mul_d_scalar_barrett_into_e<
338 const BRANGE: u8,
339 const REDUCE: REDUCEMOD,
340 >(
341 &self,
342 a: &Poly<u64>,
343 b: &Poly<u64>,
344 c: &u64,
345 d: &Barrett<u64>,
346 e: &mut Poly<u64>,
347 ) {
348 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
349 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
350 debug_assert!(e.n() == self.n(), "e.n()={} != n={}", e.n(), self.n());
351 self.modulus
352 .vb_sub_va_add_sc_mul_sd_into_ve::<CHUNK, BRANGE, REDUCE>(&a.0, &b.0, c, d, &mut e.0);
353 }
354
355 #[inline(always)]
356 pub fn b_sub_a_add_c_scalar_mul_d_scalar_barrett_into_a<
357 const BRANGE: u8,
358 const REDUCE: REDUCEMOD,
359 >(
360 &self,
361 b: &Poly<u64>,
362 c: &u64,
363 d: &Barrett<u64>,
364 a: &mut Poly<u64>,
365 ) {
366 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
367 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
368 self.modulus
369 .vb_sub_va_add_sc_mul_sd_into_va::<CHUNK, BRANGE, REDUCE>(&b.0, c, d, &mut a.0);
370 }
371}