Panics when inputing unsigned numbers.

[MarcusTL12]

As the title states trying to run something like:

modinverse(10 as u32, 13 as u32);

panics with attempt to subtract with overflow.

[simon-andrews]

Hmm. I can reproduce this, but only when compiled with debug mode. Release mode seems to work fine. Will look into this. Thanks for bringing it up!

[BartMassey]

No, it doesn't work correctly.

fn main() {
    let a = 65537_u64;
    let m = 696807540_u64;
    let x = modinverse::modinverse(a, m).unwrap();
    println!("{}", (x * a) % m);
}

Panics on subtract with overflow when compiled and run in debug mode. Gives 203648133 when compiled and run in release mode. Using i64 instead of u64 gives correct operation (answer is 1 as expected).

[2br-2b]

I have the same problem with some u64s.

[aalekhpatel07]

Hi! I'm facing a similar subtract overflow. Wondering if there's any good workaround someone has come across:

Failing test:

fn test_egcd_overflows() {
    let (g, _, _) = egcd(4, 2058270774454069813_u64);
    assert!(b % g == 0);
    assert!(a % g == 0);
}

The following is my current hacky workaround that expands the space quite a bit but I'm not sure if this is the most performant way to go about it. This modification passes all tests generated by proptest as well as the one above.

pub fn egcd(a: i128, b: i128) -> (i128, i128, i128) {
    if a == 0 {
        (b, 0, 1)
    }
    else {
        let (g, x, y) = egcd(b % a, a);
        (g, y - (b / a) * x, x)
    }
}

pub fn modinverse(a: usize, m: usize) -> Option<usize> {
    let ai = a as i128;
    let mi = m as i128;
    let (g, x, _) = egcd(ai, mi);
    let g = g.rem_euclid(mi) as usize;

    match g {
        1 => Some((x % mi).rem_euclid(mi) as usize),
        _ => None
    }
}

[electraminer]

I had the same issue today trying to run this with usizes. Since I was compiling in release mode, the overflow would simply happen and the modular inverse function just returned the wrong number, even 0 in some cases.

It seems to me like the algorithm used here requires negative numbers in order to function - the requirement Ax + By = GCD fundamentally requires one of x and y to be negative, and the other positive. This is going to cause an overflow error with unsigned integers. It might be possible to calculate this in a slightly alternative way with unsigned integers, instead of returning a positive x and negative y, to return x and y such that Ax + By === 0 mod GCD? I would need to brush up on my number theory to know for sure if this is the same process but it intuitively seems right. Not sure if this could be done in the same function using such functions as .rem_euclid rather than %, my guess is it would need a different function egcd_unsigned in order to return the x and y in a different form. Looking at the num_integer crate which this create uses to generically implement all Integers, it has its own implementation of Extended GCD, with the same problems. It seems to me that if certain algorithms do not work with negative numbers, they should not be able to be used on unsigned types.

Would it be better to adopt an architecture with something like a SignedInteger and UnsignedInteger trait on top of the Integer trait? Algorithms which overflow like GCD could be defined only on SignedInteger, or an alternative which uses modulus to stay positive could be defined on UnsignedInteger (probably classified differently since the output would fundamentally be different, using modular arithmetic rather than normal arithmetic)