1 //! [`Uint`] multiplication modulus operations.
3 use crate::{Limb, Uint, WideWord, Word}
;
5 impl<const LIMBS
: usize> Uint
<LIMBS
> {
6 /// Computes `self * rhs mod p` for the special modulus
7 /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
8 /// For the modulus reduction, this function implements Algorithm 14.47 from
9 /// the "Handbook of Applied Cryptography", by A. Menezes, P. van Oorschot,
10 /// and S. Vanstone, CRC Press, 1996.
11 pub const fn mul_mod_special(&self, rhs
: &Self, c
: Limb
) -> Self {
12 // We implicitly assume `LIMBS > 0`, because `Uint<0>` doesn't compile.
13 // Still the case `LIMBS == 1` needs special handling.
15 let prod
= self.limbs
[0].0 as WideWord
* rhs
.limbs
[0].0 as WideWord
;
16 let reduced
= prod
% Word
::MIN
.wrapping_sub(c
.0) as WideWord
;
17 return Self::from_word(reduced
as Word
);
20 let (lo
, hi
) = self.mul_wide(rhs
);
22 // Now use Algorithm 14.47 for the reduction
23 let (lo
, carry
) = mac_by_limb(&lo
, &hi
, c
, Limb
::ZERO
);
26 let rhs
= (carry
.0 + 1) as WideWord
* c
.0 as WideWord
;
27 lo
.adc(&Self::from_wide_word(rhs
), Limb
::ZERO
)
31 let rhs
= carry
.0.wrapping_sub(1) & c
.0;
32 lo
.sbb(&Self::from_word(rhs
), Limb
::ZERO
)
39 /// Computes `a + (b * c) + carry`, returning the result along with the new carry.
40 const fn mac_by_limb
<const LIMBS
: usize>(
45 ) -> (Uint
<LIMBS
>, Limb
) {
48 let mut carry
= carry
;
51 let (n
, c
) = a
.limbs
[i
].mac(b
.limbs
[i
], c
, carry
);
60 #[cfg(all(test, feature = "rand"))]
62 use crate::{Limb, NonZero, Random, RandomMod, Uint}
;
63 use rand_core
::SeedableRng
;
65 macro_rules
! test_mul_mod_special
{
66 ($size
:expr
, $test_name
:ident
) => {
69 let mut rng
= rand_chacha
::ChaCha8Rng
::seed_from_u64(1);
71 NonZero
::<Limb
>::random(&mut rng
),
72 NonZero
::<Limb
>::random(&mut rng
),
75 for special
in &moduli
{
76 let p
= &NonZero
::new(Uint
::ZERO
.wrapping_sub(&Uint
::from_word(special
.0)))
79 let minus_one
= p
.wrapping_sub(&Uint
::ONE
);
82 (Uint
::ZERO
, Uint
::ZERO
, Uint
::ZERO
),
83 (Uint
::ONE
, Uint
::ZERO
, Uint
::ZERO
),
84 (Uint
::ZERO
, Uint
::ONE
, Uint
::ZERO
),
85 (Uint
::ONE
, Uint
::ONE
, Uint
::ONE
),
86 (minus_one
, minus_one
, Uint
::ONE
),
87 (minus_one
, Uint
::ONE
, minus_one
),
88 (Uint
::ONE
, minus_one
, minus_one
),
90 for (a
, b
, c
) in &base_cases
{
91 let x
= a
.mul_mod_special(&b
, *special
.as_ref());
92 assert_eq
!(*c
, x
, "{} * {} mod {} = {} != {}", a
, b
, p
, x
, c
);
96 let a
= Uint
::<$size
>::random_mod(&mut rng
, p
);
97 let b
= Uint
::<$size
>::random_mod(&mut rng
, p
);
99 let c
= a
.mul_mod_special(&b
, *special
.as_ref());
100 assert
!(c
< **p
, "not reduced: {} >= {} ", c
, p
);
103 let (lo
, hi
) = a
.mul_wide(&b
);
104 let mut prod
= Uint
::<{ 2 * $size }
>::ZERO
;
105 prod
.limbs
[..$size
].clone_from_slice(&lo
.limbs
);
106 prod
.limbs
[$size
..].clone_from_slice(&hi
.limbs
);
107 let mut modulus
= Uint
::ZERO
;
108 modulus
.limbs
[..$size
].clone_from_slice(&p
.as_ref().limbs
);
109 let reduced
= prod
.rem(&NonZero
::new(modulus
).unwrap());
110 let mut expected
= Uint
::ZERO
;
111 expected
.limbs
[..].clone_from_slice(&reduced
.limbs
[..$size
]);
114 assert_eq
!(c
, expected
, "incorrect result");
121 test_mul_mod_special
!(1, mul_mod_special_1
);
122 test_mul_mod_special
!(2, mul_mod_special_2
);
123 test_mul_mod_special
!(3, mul_mod_special_3
);
124 test_mul_mod_special
!(4, mul_mod_special_4
);
125 test_mul_mod_special
!(5, mul_mod_special_5
);
126 test_mul_mod_special
!(6, mul_mod_special_6
);
127 test_mul_mod_special
!(7, mul_mod_special_7
);
128 test_mul_mod_special
!(8, mul_mod_special_8
);
129 test_mul_mod_special
!(9, mul_mod_special_9
);
130 test_mul_mod_special
!(10, mul_mod_special_10
);
131 test_mul_mod_special
!(11, mul_mod_special_11
);
132 test_mul_mod_special
!(12, mul_mod_special_12
);