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
//! Fast 512-bit modular reduction for sparse primes where `2^256 - modulus` fits in a `u64`.
//!
//! Dispatches to `sparse_reduce_ct` (constant-time) when the `ct-field`
//! feature is enabled, or `sparse_reduce_vt` (variable-time) by default.
use super::U512;
use crate::u256::U256;
impl U512 {
/// Reduces this 512-bit value modulo a sparse prime where the complement
/// `2^256 - modulus` fits in a single `u64`.
///
/// With the `ct-field` feature enabled, this is constant-time (branchless).
/// Without the feature, uses early-return optimizations.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
/// use cnfy_uint::u512::U512;
/// let P = U256::from_be_limbs([
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
/// ]);
///
/// let a = U256::from_be_limbs([0, 0, 0, 7]);
/// let product = a * a;
/// assert_eq!(product.sparse_reduce(&P, 0x1000003D1), U256::from_be_limbs([0, 0, 0, 49]));
/// ```
#[inline]
pub fn sparse_reduce(&self, modulus: &U256, comp: u64) -> U256 {
#[cfg(feature = "ct-field")]
{ self.sparse_reduce_ct(modulus, comp) }
#[cfg(not(feature = "ct-field"))]
{ self.sparse_reduce_vt(modulus, comp) }
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
/// Dispatcher matches VT variant.
#[test]
fn matches_vt() {
let a = U256::from_be_limbs([0, 0, 0, 7]);
let product = a * a;
assert_eq!(
product.sparse_reduce(&P, 0x1000003D1),
product.sparse_reduce_vt(&P, 0x1000003D1),
);
}
}