1use crate::modulus::ONCE;
 2use crate::poly::Poly;
 3use crate::ring::Ring;
 4
 5impl Ring<u64> {
 6    // Generates a vector storing {X^{2^0}, X^{2^1}, .., X^{2^log_n}}.
 7    pub fn gen_x_pow_2<const NTT: bool, const INV: bool>(&self, log_n: usize) -> Vec<Poly<u64>> {
 8        let mut x_pow: Vec<Poly<u64>> = Vec::<Poly<u64>>::with_capacity(log_n);
 9
10        (0..log_n).for_each(|i| {
11            let mut idx: usize = 1 << i;
12
13            if INV {
14                idx = self.n() - idx;
15            }
16
17            x_pow.push(self.new_poly());
18
19            if i == 0 {
20                x_pow[i].0[idx] = self.modulus.montgomery.one();
21                self.ntt_inplace::<false>(&mut x_pow[i]);
22            } else {
23                let (left, right) = x_pow.split_at_mut(i);
24                self.a_mul_b_montgomery_into_c::<ONCE>(&left[i - 1], &left[i - 1], &mut right[0]);
25            }
26        });
27
28        if INV {
29            self.a_neg_into_a::<1, ONCE>(&mut x_pow[0]);
30        }
31
32        if !NTT {
33            x_pow.iter_mut().for_each(|x| self.intt_inplace::<false>(x));
34        }
35
36        x_pow
37    }
38}