如何修改Rust大整数模乘法逆元函数以支持负数值输入

错误原因 #

现有modinv函数的实现默认输入的待求逆元为模p下的正剩余，传入负数时，div_rem返回的商和余数不符合扩展欧几里得算法的计算预期，最终得到错误结果。

修复方案 #

只需要在函数入口处先将输入的n归一化为模p的正剩余即可，使用num库Integer trait提供的mod_floor方法可以直接得到和除数（此处p为正数）同符号的余数，即正的模剩余值，和Python的取模行为一致。

修改后的modinv函数代码如下：

fn modinv(n: &BigInt, p: &BigInt) -> BigInt {
    if p.is_one() { 
        return BigInt::one();
    }

    // 新增行：将n转换为模p的正剩余，兼容负数输入
    let (mut a, mut m, mut x, mut inv) = (n.mod_floor(p), p.clone(), BigInt::zero(), BigInt::one());

    while a > BigInt::one() {
        let (div, rem) = a.div_rem(&m);
        inv -= div * &x;
        a = rem;
        std::mem::swap(&mut a, &mut m);
        std::mem::swap(&mut x, &mut inv);
    }
 
    if inv < BigInt::zero() { 
        inv += p;
    }

    inv
}

验证结果 #

修改后运行测试用例，输出结果和Pythonpow(n, -1, p)返回的78090076461723887468177075808811701300309702327169440891599636163808855875538完全一致。

内容的提问来源于stack exchange，提问作者Kevin