1use crate::modulus::WordOps;
 2use crate::poly::Poly;
 3use crate::ring::Ring;
 4
 5/// Returns a lookup table for the automorphism X^{i} -> X^{i * k mod nth_root}.
 6/// Method will panic if n or nth_root are not power-of-two.
 7/// Method will panic if gal_el is not coprime with nth_root.
 8pub fn automorphism_index_ntt(n: usize, nth_root: u64, gal_el: u64) -> Vec<u64> {
 9    assert!(n & (n - 1) != 0, "invalid n={}: not a power-of-two", n);
10    assert!(
11        nth_root & (nth_root - 1) != 0,
12        "invalid nth_root={}: not a power-of-two",
13        n
14    );
15    assert!(
16        gal_el & 1 == 1,
17        "invalid gal_el={}: not coprime with nth_root={}",
18        gal_el,
19        nth_root
20    );
21
22    let mask = nth_root - 1;
23    let log_nth_root: u32 = nth_root.log2() as u32;
24    let mut index: Vec<u64> = Vec::with_capacity(n);
25    for i in 0..n {
26        let i_rev: usize = 2 * i.reverse_bits_msb(log_nth_root) + 1;
27        let gal_el_i: u64 = (gal_el * (i_rev as u64) & mask) >> 1;
28        index.push(gal_el_i.reverse_bits_msb(log_nth_root));
29    }
30    index
31}
32
33impl Ring<u64> {
34    pub fn automorphism(&self, a: Poly<u64>, gal_el: u64, b: &mut Poly<u64>) {
35        debug_assert!(
36            a.n() == b.n(),
37            "invalid inputs: a.n() = {} != b.n() = {}",
38            a.n(),
39            b.n()
40        );
41        debug_assert!(gal_el & 1 == 1, "invalid gal_el = {}: not odd", gal_el);
42
43        let n: usize = a.n();
44        let mask: u64 = (n - 1) as u64;
45        let log_n: usize = n.log2();
46        let q: u64 = self.modulus.q();
47        let b_vec: &mut _ = &mut b.0;
48        let a_vec: &_ = &a.0;
49
50        a_vec.iter().enumerate().for_each(|(i, ai)| {
51            let gal_el_i: u64 = i as u64 * gal_el;
52            let sign: u64 = (gal_el_i >> log_n) & 1;
53            let i_out: u64 = gal_el_i & mask;
54            b_vec[i_out as usize] = ai * (sign ^ 1) | (q - ai) * sign
55        });
56    }
57}