如何解决可能的乘法溢出以获得正确的模运算？

Question

我必须执行(a * b) % m，但是a、b、和 m都是128位无符号类型，并且乘法期间溢出的可能性很大。我怎样才能仍然得到正确答案（可能使用 % 更多）？

我正在尝试在 Rust 中实现模指数函数，其中最大的内置类型是 u128（这是我可以使用的最大值）。这三个变量都非常大，所以 (a * b) > 2^128 很容易。我可以用a.overflowing_mul(b)来检测是否发生溢出，但是我不知道如何从溢出的结果（可以认为是(a * b) % 2^128）返回得到(a * b) % m。

我的模指数代码如下所示（目前没有添加溢出支持）：

fn mod_exp(b: u128, e: u128, m: u128) {
    (0..e).fold(1, |x, _| (x * b) % m)
    //                    ^^^^^^^^^^^
}

从数学的角度来看：

(a * b) % m IS ACTUALLY (a * b) % B % m
| B = current base (2^128)

示例：

// Mathematical
(9 * 13) % 11 = 7
// Real (base 20):
(9 * 13) % (B = 20) % 11 = 6
         ^^^^^^^^^^        ^ should be 7

(8 * 4) % 14 = 4
(8 * 4) % (B = 16) % 14 = 0
        ^^^^^^^^^^        ^ should be 4

Answer 1

此实现基于将 128 位产品拆分为四个 64 位产品，速度是 num_bigint::BigUint, ten times as fast as uint::U256, and 2.3 times as fast as gmp::mpz::Mpz 的五倍：

fn mul_mod(a: u128, b: u128, m: u128) -> u128 {
    if m <= 1 << 64 {
        ((a % m) * (b % m)) % m
    } else {
        let add = |x: u128, y: u128| x.checked_sub(m - y).unwrap_or_else(|| x + y);
        let split = |x: u128| (x >> 64, x & !(!0 << 64));
        let (a_hi, a_lo) = split(a);
        let (b_hi, b_lo) = split(b);
        let mut c = a_hi * b_hi % m;
        let (d_hi, d_lo) = split(a_lo * b_hi);
        c = add(c, d_hi);
        let (e_hi, e_lo) = split(a_hi * b_lo);
        c = add(c, e_hi);
        for _ in 0..64 {
            c = add(c, c);
        }
        c = add(c, d_lo);
        c = add(c, e_lo);
        let (f_hi, f_lo) = split(a_lo * b_lo);
        c = add(c, f_hi);
        for _ in 0..64 {
            c = add(c, c);
        }
        add(c, f_lo)
    }
}

（警告： none 这些实现适用于加密代码，因为它们没有针对边信道攻击进行强化。）

如何解决可能的乘法溢出以获得正确的模运算？

How to resolve a possible multiplicative overflow to get correct modulus operation?

rust

modulo

integer-overflow

int128