1use crate::modulus::barrett::Barrett;
 2use crate::modulus::ONCE;
 3use crate::poly::Poly;
 4use crate::ring::Ring;
 5
 6impl Ring<u64> {
 7    pub fn trace_inplace<const NTT: bool>(&self, step_start: usize, a: &mut Poly<u64>) {
 8        assert!(
 9            step_start <= self.log_n(),
10            "invalid argument step_start: step_start={} > self.log_n()={}",
11            step_start,
12            self.log_n()
13        );
14
15        let log_steps: usize = self.log_n() - step_start;
16        let log_nth_root = self.log_n() + 1;
17        let nth_root: usize = 1 << log_nth_root;
18
19        if log_steps > 0 {
20            let n_inv: Barrett<u64> = self
21                .modulus
22                .barrett
23                .prepare(self.modulus.inv(1 << log_steps));
24            self.a_mul_b_scalar_barrett_into_a::<ONCE>(&n_inv, a);
25
26            let mut tmp: Poly<u64> = self.new_poly();
27
28            (step_start..self.log_n()).for_each(|i| {
29                let gal_el: usize = self.galois_element((1 << i) >> 1, i == 0, log_nth_root);
30
31                self.a_apply_automorphism_into_b::<NTT>(a, gal_el, nth_root, &mut tmp);
32                self.a_add_b_into_b::<ONCE>(&tmp, a);
33            });
34        }
35    }
36}