1use crate::modulus::barrett::BarrettPrecomp;
  2use crate::modulus::ReduceOnce;
  3
  4extern crate test;
  5
  6/// Montgomery is a generic struct storing
  7/// an element in the Montgomery domain.
  8#[derive(Clone, Copy, Debug, PartialEq, Eq)]
  9pub struct Montgomery<O>(O);
 10
 11/// Implements helper methods on the struct Montgomery<O>.
 12impl<O> Montgomery<O>{
 13
 14    #[inline(always)]
 15    pub fn new(lhs: O) -> Self{
 16        Self(lhs)
 17    }
 18
 19    #[inline(always)]
 20    pub fn value(&self) -> &O{
 21        &self.0
 22    }
 23
 24    pub fn value_mut(&mut self) -> &mut O{
 25        &mut self.0
 26    }
 27}
 28
 29/// MontgomeryPrecomp is a generic struct storing 
 30/// precomputations for Montgomery arithmetic.
 31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
 32pub struct MontgomeryPrecomp<O>{
 33    q: O,
 34    q_barrett: BarrettPrecomp<O>,
 35    q_inv: O,
 36}
 37
 38/// MontgomeryPrecomp is a set of methods implemented for MontgomeryPrecomp<u64>
 39/// enabling Montgomery arithmetic over u64 values.
 40impl MontgomeryPrecomp<u64>{
 41
 42    /// Returns an new instance of MontgomeryPrecomp<u64>.
 43    /// This method will fail if gcd(q, 2^64) != 1.
 44    #[inline(always)]
 45    fn new(q: u64) -> MontgomeryPrecomp<u64>{
 46        assert!(q & 1 != 0, "Invalid argument: gcd(q={}, radix=2^64) != 1", q);
 47        let mut q_inv: u64 = 1;
 48        let mut q_pow = q;
 49        for _i in 0..63{
 50            q_inv = q_inv.wrapping_mul(q_pow);
 51            q_pow = q_pow.wrapping_mul(q_pow);
 52        }
 53        Self{ q: q, q_barrett: BarrettPrecomp::new(q), q_inv: q_inv}
 54    }
 55
 56    /// Returns (lhs<<64)%q as a Montgomery<u64>.
 57    #[inline(always)]
 58    fn prepare(&self, lhs: u64) -> Montgomery<u64>{
 59        let mut rhs = Montgomery(0);
 60        self.prepare_assign(lhs, &mut rhs);
 61        rhs
 62    }
 63
 64    /// Assigns (lhs<<64)%q to rhs.
 65    #[inline(always)]
 66    fn prepare_assign(&self, lhs: u64, rhs: &mut Montgomery<u64>){
 67        self.prepare_lazy_assign(lhs, rhs);
 68        rhs.value_mut().reduce_once_assign(self.q);
 69    }
 70
 71    /// Returns (lhs<<64)%q in range [0, 2q-1] as a Montgomery<u64>.
 72    #[inline(always)]
 73    fn prepare_lazy(&self, lhs: u64) -> Montgomery<u64>{
 74        let mut rhs = Montgomery(0);
 75        self.prepare_lazy_assign(lhs, &mut rhs);
 76        rhs
 77    }
 78
 79    /// Assigns (lhs<<64)%q in range [0, 2q-1] to rhs.
 80    #[inline(always)]
 81    fn prepare_lazy_assign(&self, lhs: u64, rhs: &mut Montgomery<u64>){
 82        let (_, mhi) = lhs.widening_mul(*self.q_barrett.value_lo());
 83        *rhs = Montgomery((lhs.wrapping_mul(*self.q_barrett.value_hi()).wrapping_add(mhi)).wrapping_mul(self.q).wrapping_neg());
 84    }
 85
 86    /// Returns lhs * rhs * (2^{64})^-1 mod q.
 87    #[inline(always)]
 88    fn mul_external(&self, lhs: Montgomery<u64>, rhs: u64) -> u64{
 89        let mut r = self.mul_external_lazy(lhs, rhs);
 90        r.reduce_once_assign(self.q);
 91        r
 92    }
 93
 94    /// Assigns lhs * rhs * (2^{64})^-1 mod q to rhs.
 95    #[inline(always)]
 96    fn mul_external_assign(&self, lhs: Montgomery<u64>, rhs: &mut u64){
 97        self.mul_external_lazy_assign(lhs, rhs);
 98        rhs.reduce_once_assign(self.q);
 99    }
100
101    /// Returns lhs * rhs * (2^{64})^-1 mod q in range [0, 2q-1].
102    #[inline(always)]
103    fn mul_external_lazy(&self, lhs: Montgomery<u64>, rhs: u64) -> u64{
104        let mut result = rhs;
105        self.mul_external_lazy_assign(lhs, &mut result);
106        result
107    }
108
109    /// Assigns lhs * rhs * (2^{64})^-1 mod q in range [0, 2q-1] to rhs.
110    #[inline(always)]
111    fn mul_external_lazy_assign(&self, lhs: Montgomery<u64>, rhs: &mut u64){
112        let (mlo, mhi) = lhs.value().widening_mul(*rhs);
113        let (_, hhi) = self.q.widening_mul(mlo.wrapping_mul(self.q_inv));
114        *rhs = mhi.wrapping_add(self.q - hhi)
115    }
116
117    /// Returns lhs * rhs * (2^{64})^-1 mod q in range [0, 2q-1].
118    #[inline(always)]
119    fn mul_internal(&self, lhs: Montgomery<u64>, rhs: Montgomery<u64>) -> Montgomery<u64>{
120        Montgomery(self.mul_external(lhs, *rhs.value()))
121    }
122
123    /// Assigns lhs * rhs * (2^{64})^-1 mod q to rhs.
124    #[inline(always)]
125    fn mul_internal_assign(&self, lhs: Montgomery<u64>, rhs: &mut Montgomery<u64>){
126        self.mul_external_assign(lhs, rhs.value_mut());
127    }
128
129    /// Returns lhs * rhs * (2^{64})^-1 mod q in range [0, 2q-1].
130    #[inline(always)]
131    fn mul_internal_lazy(&self, lhs: Montgomery<u64>, rhs: Montgomery<u64>) -> Montgomery<u64>{
132        Montgomery(self.mul_external_lazy(lhs, *rhs.value()))
133    }
134
135    /// Assigns lhs * rhs * (2^{64})^-1 mod q in range [0, 2q-1] to rhs.
136    #[inline(always)]
137    fn mul_internal_lazy_assign(&self, lhs: Montgomery<u64>, rhs: &mut Montgomery<u64>){
138        self.mul_external_lazy_assign(lhs, rhs.value_mut());
139    }
140}
141
142
143#[cfg(test)]
144mod tests {
145    use crate::modulus::montgomery;
146    use super::*;
147    use test::Bencher;
148
149    #[test]
150    fn test_mul_external() {
151        let q: u64 = 0x1fffffffffe00001;
152    	let m_precomp = montgomery::MontgomeryPrecomp::new(q);
153        let x: u64 = 0x5f876e514845cc8b;
154        let y: u64 = 0xad726f98f24a761a;
155        let y_mont = m_precomp.prepare(y);
156    	assert!(m_precomp.mul_external(y_mont, x) == (x as u128 * y as u128 % q as u128) as u64);
157    }
158
159    #[bench]
160    fn bench_mul_external(b: &mut Bencher){
161        let q: u64 = 0x1fffffffffe00001;
162    	let m_precomp = montgomery::MontgomeryPrecomp::new(q);
163        let mut x: u64 = 0x5f876e514845cc8b;
164        let y: u64 = 0xad726f98f24a761a;
165        let y_mont = m_precomp.prepare(y);
166        b.iter(|| m_precomp.mul_external_assign(y_mont, &mut x));
167    }
168}