use crate::U256;
#[derive(Debug, Clone, Copy)]
pub struct MontgomeryContext {
pub modulus: U256,
pub k0: u64,
}
impl MontgomeryContext {
#[inline(always)]
pub const fn new(modulus: U256, k0: u64) -> Self {
Self { modulus, k0 }
}
#[inline(always)]
pub fn reduce(&self, low: U256, high: U256) -> U256 {
let mut t = [
low.0[0], low.0[1], low.0[2], low.0[3], high.0[0], high.0[1], high.0[2], high.0[3],
];
macro_rules! step {
($i:expr) => {
let m = t[$i].wrapping_mul(self.k0);
let (_lo, hi) = mul64_add(m, self.modulus.0[0], t[$i]);
let mut c = hi;
let (lo1, hi1) = mul64_add2(m, self.modulus.0[1], t[$i + 1], c);
t[$i + 1] = lo1;
c = hi1;
let (lo2, hi2) = mul64_add2(m, self.modulus.0[2], t[$i + 2], c);
t[$i + 2] = lo2;
c = hi2;
let (lo3, hi3) = mul64_add2(m, self.modulus.0[3], t[$i + 3], c);
t[$i + 3] = lo3;
c = hi3;
let (sum, carry) = t[$i + 4].overflowing_add(c);
t[$i + 4] = sum;
if carry {
let mut k = $i + 5;
while k < 8 {
let (s, cy) = t[k].overflowing_add(1);
t[k] = s;
if !cy {
break;
}
k += 1;
}
}
};
}
step!(0);
step!(1);
step!(2);
step!(3);
let res = U256([t[4], t[5], t[6], t[7]]);
if gte(&res, &self.modulus) {
res.wrapping_sub(&self.modulus)
} else {
res
}
}
}
#[inline(always)]
const fn mul64_add(a: u64, b: u64, c: u64) -> (u64, u64) {
let res = (a as u128) * (b as u128) + (c as u128);
(res as u64, (res >> 64) as u64)
}
#[inline(always)]
const fn mul64_add2(a: u64, b: u64, c1: u64, c2: u64) -> (u64, u64) {
let res = (a as u128) * (b as u128) + (c1 as u128) + (c2 as u128);
(res as u64, (res >> 64) as u64)
}
#[inline(always)]
fn gte(a: &U256, b: &U256) -> bool {
if a.0[3] != b.0[3] {
return a.0[3] > b.0[3];
}
if a.0[2] != b.0[2] {
return a.0[2] > b.0[2];
}
if a.0[1] != b.0[1] {
return a.0[1] > b.0[1];
}
a.0[0] >= b.0[0]
}
#[cfg(test)]
mod tests {
use super::*;
const N97: U256 = U256::from_limbs([97, 0, 0, 0]);
const K0_N97: u64 = 0x5c5f02a3a0fd5c5f;
#[test]
fn test_reduce_zero_is_zero() {
let ctx = MontgomeryContext::new(N97, K0_N97);
let res = ctx.reduce(U256::ZERO, U256::ZERO);
assert_eq!(res, U256::ZERO);
}
#[test]
fn test_reduce_known_vector_1() {
let ctx = MontgomeryContext::new(N97, K0_N97);
let low = U256::from_limbs([
0x6671ad11c80317f,
0x46685257bdd640fb,
0x392456de3eb13b90,
0xbc8960a923b8c1e9,
]);
let high = U256::from_limbs([0x51, 0, 0, 0]);
let res = ctx.reduce(low, high);
assert_eq!(res, U256::from_limbs([0x5f, 0, 0, 0])); }
#[test]
fn test_reduce_known_vector_2() {
let ctx = MontgomeryContext::new(N97, K0_N97);
let low = U256::from_limbs([
0xbd9c66b3ad3c2d6d,
0x8b9d2434e465e150,
0x972a846916419f82,
0x0822e8f36c031199,
]);
let high = U256::from_limbs([0xd, 0, 0, 0]);
let res = ctx.reduce(low, high);
assert_eq!(res, U256::from_limbs([0x5f, 0, 0, 0])); }
#[test]
fn test_reduce_known_vector_3() {
let ctx = MontgomeryContext::new(N97, K0_N97);
let low = U256::from_limbs([
0x37f8a88b17fc695a,
0x815ef6d13b8faa18,
0x06cb0fb39a1de644,
0x32e706298fadc1a6,
]);
let high = U256::from_limbs([0x3, 0, 0, 0]);
let res = ctx.reduce(low, high);
assert_eq!(res, U256::from_limbs([0x9, 0, 0, 0])); }
#[test]
fn test_reduce_result_always_below_modulus() {
let ctx = MontgomeryContext::new(N97, K0_N97);
let low = U256::from_limbs([
0x6671ad11c80317f,
0x46685257bdd640fb,
0x392456de3eb13b90,
0xbc8960a923b8c1e9,
]);
let high = U256::from_limbs([0x51, 0, 0, 0]);
let res = ctx.reduce(low, high);
assert!(res.0[0] < 97 && res.0[1] == 0 && res.0[2] == 0 && res.0[3] == 0);
}
}