2

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?

Herohtar
  • 5,347
  • 4
  • 31
  • 41
Jakob W.
  • 288
  • 1
  • 10
  • 1
    I think as @JeremyMeadows points out, you might have to implement your own algorithm. I have an idea, though. It's based aroud the fact that `(x + a) % m == (x - (m - a)) % m`. By that, you can flip `a` to be always smaller than `m/2`. With this you can calculate the "offset" that happens if you add one `a` to a number. Then, we need to figure out how to add two of those offsets together without an overflow. If we can do that, we can split `b` down into its powers of two, figure out the offset for each power of two is, and add all of them together. – Finomnis Jul 29 '22 at 13:28
  • The solution in the duplicate is much faster than what I proposed, I think. – Finomnis Jul 29 '22 at 13:31

2 Answers2

1

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.

Jeremy Meadows
  • 2,314
  • 1
  • 6
  • 22
  • That's correct, but in my case `m` is also large (which I admittedly did not write in the question), so `(a % m) * (b % m)` might still overflow. – Jakob W. Jul 29 '22 at 13:08
  • 1
    @JakobW. if that's the case, you may have to implement your own modular multiplication function which keeps the values small enough – Jeremy Meadows Jul 29 '22 at 13:20
0

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.

Masklinn
  • 34,759
  • 3
  • 38
  • 57
  • That's exactly what his referenced [`modular arithmetic`](https://docs.rs/modular_arithmetic/latest/src/modular_arithmetic/arithmetic.rs.html#40-48) crate does, and it seems to be too slow for his usecase – Finomnis Jul 29 '22 at 13:23