num-bigint
num-bigint copied to clipboard
rust-num
BigUint extended_gcd panics on underflow
repro: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=b18dc13a3c981c6351d3cdd6e24a8715
One quick fix for this would be to override the trait default, cast to signed, and then make sure the coefficients are the positive form after (e.g., by taking the mod), if it is difficult to make the generalized algorithm work.
We really should have just required Signed for that method, as we did for extended_gcd_lcm, but that will take a breaking change in num-integer. There are few edge cases where everything can be unsigned -- I think only when one input is a multiple of the other, then you get 0 and 1 coefficients.
cast to signed, and then make sure the coefficients are the positive form after (e.g., by taking the mod)
Using what modulus?
Makes sense. However, I would prefer not to have to convert between BigUint and BigInt back and forth.
I simply want to compute the modular inverse of a BigUint, modulo a BigUint. Is there a better way to do it than convert to BigInt, call extended_gcd, ensure that the outcome is not negative, and convert back? It's a lot of code for a simple, common operation...
You could wrap BigUint in a type that does modular Sub, so it never goes negative. The conversions are not so bad though - From<BigUint> for BigInt is very cheap, and going the other way can use BigInt::into_parts, then you can apply modular negation for Sign::Minus. I don't see how you expect these non-modular types to do that for you...
OK, sounds like a decent workaround. Thanks!
(With regards to the conversions: My concern there wasn't performance, but rather code readability.)