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, (2 * n) as u64)),
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>(&self, a: &Poly<u64>, b: &Poly<u64>, c: &mut Poly<u64>) {
87 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
88 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
89 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
90 self.modulus
91 .va_add_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
92 }
93
94 #[inline(always)]
95 pub fn a_add_b_scalar_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut Poly<u64>) {
96 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
97 self.modulus.va_add_sb_into_va::<CHUNK, REDUCE>(b, &mut a.0);
98 }
99
100 #[inline(always)]
101 pub fn a_add_b_scalar_into_c<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &u64, c: &mut Poly<u64>) {
102 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
103 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
104 self.modulus
105 .va_add_sb_into_vc::<CHUNK, REDUCE>(&a.0, b, &mut c.0);
106 }
107
108 #[inline(always)]
109 pub fn a_add_scalar_b_mul_c_scalar_barrett_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, c: &Barrett<u64>, a: &mut Poly<u64>) {
110 debug_assert!(a.n() == self.n(), "b.n()={} != n={}", a.n(), self.n());
111 self.modulus.va_add_sb_mul_sc_into_va::<CHUNK, REDUCE>(b, c, &mut a.0);
112 }
113
114 #[inline(always)]
115 pub fn add_scalar_then_mul_scalar_barrett<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &u64, c: &Barrett<u64>, d: &mut Poly<u64>) {
116 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
117 debug_assert!(d.n() == self.n(), "c.n()={} != n={}", d.n(), self.n());
118 self.modulus
119 .va_add_sb_mul_sc_into_vd::<CHUNK, REDUCE>(&a.0, b, c, &mut d.0);
120 }
121
122 #[inline(always)]
123 pub fn a_sub_b_into_b<const BRANGE:u8, const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>) {
124 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
125 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
126 self.modulus
127 .va_sub_vb_into_vb::<CHUNK, BRANGE, REDUCE>(&a.0, &mut b.0);
128 }
129
130 #[inline(always)]
131 pub fn a_sub_b_into_a<const BRANGE:u8, const REDUCE: REDUCEMOD>(&self, b: &Poly<u64>, a: &mut Poly<u64>) {
132 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
133 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
134 self.modulus
135 .va_sub_vb_into_va::<CHUNK, BRANGE, REDUCE>(&b.0, &mut a.0);
136 }
137
138 #[inline(always)]
139 pub fn a_sub_b_into_c<const BRANGE:u8, const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &Poly<u64>, c: &mut Poly<u64>) {
140 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
141 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
142 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
143 self.modulus
144 .va_sub_vb_into_vc::<CHUNK, BRANGE, REDUCE>(&a.0, &b.0, &mut c.0);
145 }
146
147 #[inline(always)]
148 pub fn a_neg_into_b<const ARANGE:u8, const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>) {
149 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
150 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
151 self.modulus.va_neg_into_vb::<CHUNK, ARANGE, REDUCE>(&a.0, &mut b.0);
152 }
153
154 #[inline(always)]
155 pub fn a_neg_into_a<const ARANGE:u8,const REDUCE: REDUCEMOD>(&self, a: &mut Poly<u64>) {
156 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
157 self.modulus.va_neg_into_va::<CHUNK, ARANGE, REDUCE>(&mut a.0);
158 }
159
160 #[inline(always)]
161 pub fn a_mul_b_montgomery_into_c<const REDUCE: REDUCEMOD>(
162 &self,
163 a: &Poly<Montgomery<u64>>,
164 b: &Poly<u64>,
165 c: &mut Poly<u64>,
166 ) {
167 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
168 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
169 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
170 self.modulus
171 .va_mont_mul_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
172 }
173
174 #[inline(always)]
175 pub fn a_mul_b_montgomery_into_a<const REDUCE: REDUCEMOD>(
176 &self,
177 b: &Poly<Montgomery<u64>>,
178 a: &mut Poly<u64>,
179 ) {
180 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
181 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
182 self.modulus
183 .va_mont_mul_vb_into_vb::<CHUNK, REDUCE>(&b.0, &mut a.0);
184 }
185
186 #[inline(always)]
187 pub fn a_mul_b_scalar_into_c<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &u64, c: &mut Poly<u64>) {
188 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
189 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
190 self.modulus.sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(
191 &self.modulus.barrett.prepare(*b),
192 &a.0,
193 &mut c.0,
194 );
195 }
196
197 #[inline(always)]
198 pub fn a_mul_b_scalar_into_a<const REDUCE: REDUCEMOD>(&self, b: &u64, a: &mut Poly<u64>) {
199 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
200 self.modulus.sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(
201 &self
202 .modulus
203 .barrett
204 .prepare(self.modulus.barrett.reduce::<BARRETT>(b)),
205 &mut a.0,
206 );
207 }
208
209 #[inline(always)]
210 pub fn a_mul_b_scalar_barrett_into_a<const REDUCE: REDUCEMOD>(
211 &self,
212 b: &Barrett<u64>,
213 a: &mut Poly<u64>,
214 ) {
215 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
216 self.modulus
217 .sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(b, &mut a.0);
218 }
219
220 #[inline(always)]
221 pub fn a_mul_b_scalar_barrett_into_c<const REDUCE: REDUCEMOD>(
222 &self,
223 a: &Barrett<u64>,
224 b: &Poly<u64>,
225 c: &mut Poly<u64>,
226 ) {
227 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
228 self.modulus
229 .sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(a, &b.0, &mut c.0);
230 }
231
232 #[inline(always)]
233 pub fn a_sub_b_mul_c_scalar_barrett_into_d<const VBRANGE: u8, const REDUCE: REDUCEMOD>(
234 &self,
235 a: &Poly<u64>,
236 b: &Poly<u64>,
237 c: &Barrett<u64>,
238 d: &mut Poly<u64>,
239 ) {
240 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
241 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
242 debug_assert!(d.n() == self.n(), "d.n()={} != n={}", d.n(), self.n());
243 self.modulus
244 .va_sub_vb_mul_sc_into_vd::<CHUNK, VBRANGE, REDUCE>(&a.0, &b.0, c, &mut d.0);
245 }
246
247 #[inline(always)]
248 pub fn b_sub_a_mul_c_scalar_barrett_into_a<const BRANGE: u8, const REDUCE: REDUCEMOD>(
249 &self,
250 b: &Poly<u64>,
251 c: &Barrett<u64>,
252 a: &mut Poly<u64>,
253 ) {
254 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
255 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
256 self.modulus
257 .va_sub_vb_mul_sc_into_vb::<CHUNK, BRANGE, REDUCE>(&b.0, c, &mut a.0);
258 }
259
260 #[inline(always)]
261 pub fn a_sub_b_add_c_scalar_mul_d_scalar_barrett_into_e<const BRANGE: u8, const REDUCE: REDUCEMOD>(
262 &self,
263 a: &Poly<u64>,
264 b: &Poly<u64>,
265 c: &u64,
266 d: &Barrett<u64>,
267 e: &mut Poly<u64>,
268 ){
269 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
270 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
271 debug_assert!(e.n() == self.n(), "e.n()={} != n={}", e.n(), self.n());
272 self.modulus
273 .vb_sub_va_add_sc_mul_sd_into_ve::<CHUNK, BRANGE, REDUCE>(&a.0, &b.0, c, d, &mut e.0);
274 }
275
276 #[inline(always)]
277 pub fn b_sub_a_add_c_scalar_mul_d_scalar_barrett_into_a<const BRANGE: u8, const REDUCE: REDUCEMOD>(
278 &self,
279 b: &Poly<u64>,
280 c: &u64,
281 d: &Barrett<u64>,
282 a: &mut Poly<u64>,
283 ){
284 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
285 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
286 self.modulus
287 .vb_sub_va_add_sc_mul_sd_into_va::<CHUNK, BRANGE, REDUCE>(&b.0, c, d, &mut a.0);
288 }
289
290}