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