hyper-u256 0.1.0

Arithmétique 256-bit ultra-rapide en no_std avec optimisation SIMD et zéro allocation pour les corps finis et la cryptographie.
Documentation
use crate::U256;

/// Contexte d'arithmétique modulaire de Montgomery, ultra-optimisé
/// (`no_std`, zéro allocation).
///
/// `modulus` est le module `N` (impair, comme l'exige Montgomery) et `k0`
/// est la constante `-N⁻¹ mod 2⁶⁴`, précalculée une seule fois par
/// l'appelant.
#[derive(Debug, Clone, Copy)]
pub struct MontgomeryContext {
    pub modulus: U256,
    /// `-N⁻¹ mod 2⁶⁴`
    pub k0: u64,
}

impl MontgomeryContext {
    #[inline(always)]
    pub const fn new(modulus: U256, k0: u64) -> Self {
        Self { modulus, k0 }
    }

    /// Réduction de Montgomery (REDC) : transforme un produit intermédiaire
    /// 512-bit (`low` + `high` * 2²⁵⁶) en un résultat 256-bit réduit mod
    /// `modulus`, en temps déterministe (pas de branche dépendant des
    /// données, à l'exception de la comparaison finale contre `modulus`
    /// qui est elle-même faite en temps constant sur les mots).
    ///
    /// Précondition standard de REDC : `low + high * 2²⁵⁶ < modulus * 2²⁵⁶`.
    #[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::*;

    // Modulus N = 97, k0 = -97^-1 mod 2^64, précalculés et vérifiés
    // indépendamment (arithmétique exacte en précision arbitraire), ainsi
    // que les 3 vecteurs de test ci-dessous.
    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])); // 95
    }

    #[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])); // 95
    }

    #[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])); // 9
    }

    #[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);
    }
}