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