1use crate::modulus::barrett::BarrettPrecomp;
  2use crate::modulus::ReduceOnce;
  3
  4pub struct Montgomery<O>(O);
  5
  6
  7impl<O> Montgomery<O>{
  8
  9    #[inline(always)]
 10    pub fn new(lhs: O) -> Self{
 11        Self(lhs)
 12    }
 13
 14    #[inline(always)]
 15    pub fn value(&self) -> &O{
 16        &self.0
 17    }
 18
 19    pub fn value_mut(&mut self) -> &mut O{
 20        &mut self.0
 21    }
 22}
 23
 24pub struct MontgomeryPrecomp<O>{
 25    q: O,
 26    q_barrett: BarrettPrecomp<O>,
 27    q_inv: O,
 28}
 29
 30impl MontgomeryPrecomp<u64>{
 31
 32    #[inline(always)]
 33    fn new(&self, q: u64) -> MontgomeryPrecomp<u64>{
 34        let mut r: u64 = 1;
 35        let mut q_pow = q;
 36        for _i in 0..63{
 37            r = r.wrapping_mul(r);
 38            q_pow = q_pow.wrapping_mul(q_pow)
 39        }
 40        Self{ q: q, q_barrett: BarrettPrecomp::new(q, q), q_inv: q_pow}
 41    }
 42
 43    #[inline(always)]
 44    fn prepare(&self, lhs: u64) -> Montgomery<u64>{
 45        let mut rhs = Montgomery(0);
 46        self.prepare_assign(lhs, &mut rhs);
 47        rhs
 48    }
 49
 50    fn prepare_assign(&self, lhs: u64, rhs: &mut Montgomery<u64>){
 51        self.prepare_lazy_assign(lhs, rhs);
 52        rhs.value_mut().reduce_once_assign(self.q);
 53    }
 54
 55    #[inline(always)]
 56    fn prepare_lazy(&self, lhs: u64) -> Montgomery<u64>{
 57        let mut rhs = Montgomery(0);
 58        self.prepare_lazy_assign(lhs, &mut rhs);
 59        rhs
 60    }
 61
 62    fn prepare_lazy_assign(&self, lhs: u64, rhs: &mut Montgomery<u64>){
 63        let (mhi, _) = lhs.widening_mul(*self.q_barrett.value_lo());
 64        *rhs = Montgomery((lhs.wrapping_mul(*self.q_barrett.value_hi()).wrapping_add(mhi)).wrapping_mul(self.q).wrapping_neg());
 65    }
 66
 67    #[inline(always)]
 68    fn mul_external(&self, lhs: Montgomery<u64>, rhs: u64) -> u64{
 69        let mut r = self.mul_external_lazy(lhs, rhs);
 70        r.reduce_once_assign(self.q);
 71        r
 72    }
 73
 74    #[inline(always)]
 75    fn mul_external_assign(&self, lhs: Montgomery<u64>, rhs: &mut u64){
 76        self.mul_external_lazy_assign(lhs, rhs);
 77        rhs.reduce_once_assign(self.q);
 78    }
 79
 80    #[inline(always)]
 81    fn mul_external_lazy(&self, lhs: Montgomery<u64>, rhs: u64) -> u64{
 82        let mut result = rhs;
 83        self.mul_external_lazy_assign(lhs, &mut result);
 84        result
 85    }
 86
 87    #[inline(always)]
 88    fn mul_external_lazy_assign(&self, lhs: Montgomery<u64>, rhs: &mut u64){
 89        let (mhi, mlo) = lhs.value().widening_mul(*rhs);
 90        let (hhi, _) = self.q.widening_mul(mlo * self.q_inv);
 91        *rhs = mhi - hhi + self.q
 92    }
 93
 94    #[inline(always)]
 95    fn mul_internal(&self, lhs: Montgomery<u64>, rhs: Montgomery<u64>) -> Montgomery<u64>{
 96        Montgomery(self.mul_external(lhs, *rhs.value()))
 97    }
 98
 99    #[inline(always)]
100    fn mul_internal_assign(&self, lhs: Montgomery<u64>, rhs: &mut Montgomery<u64>){
101        self.mul_external_assign(lhs, rhs.value_mut());
102    }
103
104    #[inline(always)]
105    fn mul_internal_lazy(&self, lhs: Montgomery<u64>, rhs: Montgomery<u64>) -> Montgomery<u64>{
106        Montgomery(self.mul_external_lazy(lhs, *rhs.value()))
107    }
108
109    #[inline(always)]
110    fn mul_internal_lazy_assign(&self, lhs: Montgomery<u64>, rhs: &mut Montgomery<u64>){
111        self.mul_external_lazy_assign(lhs, rhs.value_mut());
112    }
113}