use num_traits::Zero;
use tc_bigint::{FixedBigUint, Word};
use tc_constant_time::{Choice, ConditionallySelectable};
use super::add::add_residues;
use crate::wipe::replace_wiped;
use crate::{ModMul, NonZero};
use tc_zeroize::Zeroizing;
impl<const N: usize> ModMul for FixedBigUint<N> {
type Output = Self;
fn mod_mul(&self, rhs: &Self, modulus: &NonZero<Self>) -> Self {
let modulus: &Self = modulus;
let residues = (
Zeroizing::new(self % modulus),
Zeroizing::new(rhs % modulus),
);
mul_residues(&residues.0, &residues.1, modulus)
}
}
pub(super) fn mul_residues<const N: usize>(
lhs: &FixedBigUint<N>,
rhs: &FixedBigUint<N>,
modulus: &FixedBigUint<N>,
) -> FixedBigUint<N> {
let mut product = FixedBigUint::zero();
for index in (0..N as u32 * Word::BITS).rev() {
let doubled = add_residues(&product, &product, modulus);
replace_wiped(&mut product, doubled);
let sum = Zeroizing::new(add_residues(&product, lhs, modulus));
product.conditional_assign(&sum, Choice::from_lsb(u8::from(rhs.bit(index))));
}
product
}
#[cfg(test)]
mod tests {
use tc_bigint::{FixedBigUint, Word};
use crate::{ModMul, NonZero};
const LIMBS: usize = (u128::BITS / Word::BITS) as usize;
const VALUES: [u128; 8] = [
0,
1,
255,
u64::MAX as u128,
u64::MAX as u128 + 1,
i128::MAX as u128,
u128::MAX - 1,
u128::MAX,
];
fn expected(a: u128, b: u128, m: u128) -> u128 {
let add = |x: u128, y: u128| if x >= m - y { x - (m - y) } else { x + y };
let (a, b) = (a % m, b % m);
(0..u128::BITS).rev().fold(0, |product, index| {
let doubled = add(product, product);
if b >> index & 1 == 1 {
add(doubled, a)
} else {
doubled
}
})
}
#[test]
fn the_product_is_the_primitive_product_reduced_by_the_modulus() {
for m in &VALUES[1..] {
let modulus = NonZero::new(FixedBigUint::<LIMBS>::from(*m)).unwrap();
for a in VALUES {
for b in VALUES {
let (x, y) = (
FixedBigUint::<LIMBS>::from(a),
FixedBigUint::<LIMBS>::from(b),
);
let expected = FixedBigUint::<LIMBS>::from(expected(a, b, *m));
assert_eq!(x.mod_mul(&y, &modulus), expected, "{a} {b} {m}");
}
}
}
}
#[test]
fn a_product_wider_than_the_operands_is_reduced() {
let power = FixedBigUint::<LIMBS>::from(u64::MAX as u128 + 1);
let modulus = NonZero::new(FixedBigUint::<LIMBS>::from(i128::MAX as u128)).unwrap();
assert_eq!(
power.mod_mul(&power, &modulus),
FixedBigUint::<LIMBS>::from(2u8)
);
let below = FixedBigUint::<LIMBS>::from(u128::MAX - 1);
let modulus = NonZero::new(FixedBigUint::<LIMBS>::from(u128::MAX)).unwrap();
assert_eq!(
below.mod_mul(&below, &modulus),
FixedBigUint::<LIMBS>::from(1u8)
);
}
}