Modular multiplication

user_4322240 0
Viewed 55

Given a, b and m, all of type u64 (or u128), I want to calculate (a * b) % m. However, a and b may be large, so an overflow may occur.

While I could cast them to BigUInt, multiply them and then cast the result back, this seems a bit unelegant to me. (Since the casting to BigUInt is theoretically unnecessary.)

I also found the modular arithmetic crate, but it seems to be unmaintained, undocumented and the multiplication is very slow in case of an overflow. Also, there is the modular crate, but there an overflow can occur.

So, is there a more elegant way to do modular multiplication in Rust?

rust
2 Answers

If m * m is small enough to not overflow, you can use (a % m) * (b % m) % m to keep your multiplicands smaller, and it produces the same result as a * b % m because of neat modular properties.

user_138439350

So, is there a more elegant way to do modular multiplication in Rust?

Unroll the multiplication to a sequence of modular additions?

Even if the additions can overflow (e.g. 190u8 + 170u8 mod 200u8), you can probably handle the case with overflow_add and adjust backwards.

user_81821180
Related