模乘法逆在密码学中广泛使用。我有following program在 Rust 中使用扩展欧几里德算法计算模乘逆:
extern crate num;
use num::bigint::BigInt;
use num::Integer;
use num::One;
use num::Zero;
fn modinv(n: &BigInt, p: &BigInt) -> BigInt {
if p.is_one() { return BigInt::one() }
let (mut a, mut m, mut x, mut inv) = (n.clone(), 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
}
fn main() {
let n = BigInt::parse_bytes(b"-243772585612020160733370897338805215918303827399330592839196552441720391139", 10).unwrap();
let p = BigInt::parse_bytes(b"115792089237316195423570985008687907853269984665640564039457584007908834671663", 10).unwrap();
println!("modinv({0}, {1}) = {2}", n, p, modinv(&n, &p));
}
这对于正 n
和 p
效果很好,但是当 n
是负数(如上面的情况)时,我得到以下输出:
modinv(-243772585612020160733370897338805215918303827399330592839196552441720391139, 115792089237316195423570985008687907853269984665640564039457584007908834671663) = 1
输出 1
不正确,我想要以下输出(使用 python shell):
In [1]: n = -243772585612020160733370897338805215918303827399330592839196552441720391139
In [2]: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
In [3]: pow(n, -1, p)
Out[3]: 78090076461723887468177075808811701300309702327169440891599636163808855875538
有没有办法改变上面的 modinv
函数,以像 python 一样处理负数?
最佳答案
添加行 while a < BigInt::zero() { a += p }
就在 a
的定义下方, m
, x
,和inv
应该可以做到这一点,利用 a % m == a + m % m
的事实.
关于rust - 大(负)数的模乘反函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68338719/