CODEWITHSUNDEEP
rustmoduloinverse
Kevin
Kevin

Reputation: 3348

Modular multiplicative inverse function for big (negative) numbers

Modular multiplicative inverse is used extensively in cryptology. I have the following program in rust for calculating the modular multiplicative inverse by using the extended euclidean algorithm:

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

Which works for fine for positive n and p, but when n is negative like the above case I get the following output:

modinv(-243772585612020160733370897338805215918303827399330592839196552441720391139, 115792089237316195423570985008687907853269984665640564039457584007908834671663) = 1

The output 1 is not correct, instead I want the following output (using a python shell):

In [1]: n = -243772585612020160733370897338805215918303827399330592839196552441720391139

In [2]: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

In [3]: pow(n, -1, p)
Out[3]: 78090076461723887468177075808811701300309702327169440891599636163808855875538

Is there a way to alter the modinv function above to also handle negative numbers in the same way as python does?

Upvotes: 2

Views: 1066

Answers (1)

isaactfa
isaactfa

Reputation: 6651

Adding the line while a < BigInt::zero() { a += p } right underneath the definition of a, m, x, and inv should do the trick, using the fact that a % m == a + m % m.

Upvotes: 4

Related Questions