Implement modular inverse

[dignifiedquire]

I had the need for this and have a variant that works well for positive numbers here, if there is interest: https://github.com/dignifiedquire/rust-rsa/blob/master/src/math.rs#L118

[dmhacker]

I second this. I would add that I also have a variant that uses the extended Euclidean algorithm, but it seems to be failing for large negative numbers.

[cuviper]

This will probably be met generically by rust-num/num-integer#10.

[dignifiedquire]

That would be nice, but this should be still implemented in here, as the properly optimized algorithms take into account the actual digits/limbs, which are not available on the generalized Integer as far as I understand.

[mikong]

@dignifiedquire, your link is currently redirecting then returning 404 for me. The RustCrypto/RSA repo doesn't have a src/math.rs, but I can see that it uses a ModInverse trait and that the trait is implemented in your fork of num-bigint. Is that where you'd like us to look at?

[dignifiedquire]

yes, that code moved out of the RSA library into my fork of num-bigint into: https://github.com/dignifiedquire/num-bigint/blob/master/src/algorithms/mod_inverse.rs