1use crate::modulus::WordOps;
 2use crate::ring::Ring;
 3use crate::poly::Poly;
 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!(nth_root&(nth_root-1) != 0, "invalid nth_root={}: not a power-of-two", n);
11    assert!(gal_el & 1 == 1, "invalid gal_el={}: not coprime with nth_root={}", gal_el, nth_root);
12
13    let mask = nth_root-1;
14    let log_nth_root: u32 = nth_root.log2() as u32;
15    let mut index: Vec<u64> = Vec::with_capacity(n);
16    for i in 0..n{
17        let i_rev: usize = 2*i.reverse_bits_msb(log_nth_root)+1;
18        let gal_el_i: u64 = (gal_el * (i_rev as u64) & mask)>>1;
19        index.push(gal_el_i.reverse_bits_msb(log_nth_root));
20    }
21    index
22}
23
24impl Ring<u64>{
25    pub fn automorphism(&self, a:Poly<u64>, gal_el: u64, b:&mut Poly<u64>){
26        debug_assert!(a.n() == b.n(), "invalid inputs: a.n() = {} != b.n() = {}", a.n(), b.n());
27        debug_assert!(gal_el&1 == 1, "invalid gal_el = {}: not odd", gal_el);
28
29        let n: usize = a.n();
30        let mask: u64 = (n-1) as u64;
31        let log_n: usize = n.log2();
32        let q: u64 = self.modulus.q();
33        let b_vec: &mut _ = &mut b.0;
34        let a_vec: &_ = &a.0;
35
36        for i in 0..n{
37            let i_in: u64 = i as u64 * gal_el;
38            let i_out: u64 = i_in & mask;
39            let sign: u64 = (i_in>>log_n) & 1;
40            b_vec[i_out as usize] = a_vec[i_in as usize] * (sign^1) | (q - a_vec[i_in as usize]) * sign
41        }
42    }
43}