1use crate::modulus::montgomery::Montgomery;
 2use crate::modulus::prime::Prime;
 3
 4pub struct Table<'a, O>{
 5    prime:&'a Prime<O>,
 6    pub psi_forward_rev:Vec<Montgomery<O>>,
 7    psi_backward_rev: Vec<Montgomery<O>>,
 8    n_inv: Montgomery<O>,
 9}
10
11impl<'a> Table<'a, u64> {
12    pub fn new(prime: &'a mut Prime<u64>, n: u64, nth_root: u64)->Self{
13
14        assert!(n&(n-1) == 0, "invalid argument: n = {} is not a power of two", n);
15        assert!(n&(n-1) == 0, "invalid argument: nth_root = {} is not a power of two", nth_root);
16        assert!(n < nth_root, "invalid argument: n = {} cannot be greater or equal to nth_root = {}", n, nth_root);
17
18        let psi: u64 = prime.primitive_nth_root(nth_root);
19
20        let psi_mont: Montgomery<u64> = prime.montgomery.prepare(psi);
21        let psi_inv_mont: Montgomery<u64> = prime.montgomery.pow(psi_mont, prime.phi-1);
22        
23        let mut psi_forward_rev: Vec<Montgomery<u64>> = vec![Montgomery(0); (nth_root >> 1) as usize];
24        let mut psi_backward_rev: Vec<Montgomery<u64>> = vec![Montgomery(0); (nth_root >> 1) as usize];
25
26        psi_forward_rev[0] = prime.montgomery.one();
27        psi_backward_rev[0] = prime.montgomery.one();
28
29        let log_nth_root_half: usize = (usize::MAX - ((nth_root>>1 as usize)-1).leading_zeros() as usize) as usize;
30
31        for i in 1..(nth_root>>1) as usize{
32
33            let i_rev_prev: usize = (i-1).reverse_bits() >> (usize::MAX - log_nth_root_half) as usize;
34            let i_rev_next: usize = i.reverse_bits() >> (usize::MAX - log_nth_root_half) as usize;
35
36            psi_forward_rev[i_rev_next] = prime.montgomery.mul_internal(psi_forward_rev[i_rev_prev], psi_mont);
37            psi_backward_rev[i_rev_next] = prime.montgomery.mul_internal(psi_backward_rev[i_rev_prev], psi_inv_mont);
38        }
39
40        let n_inv: Montgomery<u64> = prime.montgomery.pow(prime.montgomery.prepare(nth_root>>1), prime.phi-1);
41
42        Self{ 
43            prime: prime, 
44            psi_forward_rev: psi_forward_rev, 
45            psi_backward_rev: psi_backward_rev, 
46            n_inv: n_inv,
47        }
48    }
49}