1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//! Reduction of a [`U256`] into `[0, modulus)`.
//!
//! Dispatches to `modulo_ct` (constant-time, branchless) when the `ct-field`
//! feature is enabled, or `modulo_vt` (variable-time, loop) by default.
use super::U256;
impl U256 {
/// Reduces `self` modulo `modulus`, returning a value in `[0, modulus)`.
///
/// With the `ct-field` feature enabled, this is constant-time (three branchless
/// conditional subtractions, valid for inputs up to `3 * modulus - 1`).
/// Without the feature, this uses a variable-time subtraction loop that
/// handles arbitrary inputs.
///
/// # Panics
///
/// Without `ct-field`: loops indefinitely if `modulus` is zero.
/// With `ct-field`: produces incorrect results if `self >= 4 * modulus`.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
/// let P = U256::from_be_limbs([
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
/// ]);
///
/// let max = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
/// assert_eq!(max.modulo(&P), U256::from_be_limbs([0, 0, 0, 0x1000003D0]));
/// ```
#[inline]
pub fn modulo(&self, modulus: &U256) -> U256 {
#[cfg(feature = "ct-field")]
{ self.modulo_ct(modulus) }
#[cfg(not(feature = "ct-field"))]
{ self.modulo_vt(modulus) }
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
const P: U256 = U256::from_be_limbs([
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
]);
/// Dispatcher produces the same result as the VT variant.
#[test]
fn matches_vt() {
let cases = [
U256::ZERO,
U256::ONE,
P,
U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]),
];
for v in &cases {
assert_eq!(v.modulo(&P), v.modulo_vt(&P));
}
}
}
#[cfg(test)]
mod human_tests {
use super::*;
const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
/// All 0xFF bytes (2^256 - 1) mod P reduces to 2^32 + 976.
#[test]
fn all_ff_mod_p() {
let a = U256::from_be_bytes([0xFF; 32]);
assert_eq!(
a.modulo(&P),
U256::from_be_bytes([
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 3, 208,
])
);
}
/// All 0xAA bytes is already below P, returned unchanged.
#[test]
fn all_aa_below_p() {
let a = U256::from_be_bytes([0xAA; 32]);
assert_eq!(a.modulo(&P), a);
}
}