Calculate large multiplication and divide under modulus

Question

In C++, I have a problem need to calculate ((a * b * c) / n) % m with large a, b and c (0 < a, b, c <= 10^9 and n, m > 0). And the problem guaranteed that a * b * c is divisible by n.

I tried calc ((a * b) % m * c) % m) / n but it's not a right answer.

What are you using to do this "calc"? How "large" are these numbers? — Scott Hunter, Dec 28 '22 at 19:11
You can't pass the `% m` above a division bar like that. Consider for instance m = 6, n = 3, and numerator = 6k+3 for some k. Then (numerator / n) % m = (2k+1) % 6, but ((numerator % m) / n) % m = 1. — Stef, Dec 28 '22 at 19:17
However, if n is coprime with m, then there exists an integer q which is called "the inverse of n modulo m", and such that `(numerator / n) % m = (numerator * q) % m` for any numerator. In python, you can find `q` as `pow(n, -1, m)`. — Stef, Dec 28 '22 at 19:22
Actually, `((numerator % m) / n) % m = (numerator / n) % m` is true whenever n and m are coprime, and more-often-false-than-true when m and n are not coprime. See this related math question: [Division in modular arithmetic when multiplicative inverse does not exist](https://math.stackexchange.com/questions/3206669/division-in-modular-arithmetic-when-multiplicative-inverse-does-not-exist) — Stef, Dec 28 '22 at 19:29
You need to calculate the multiplicative inverse of n modulo m. See extended Euclid's algorithm for that, or find a library function that will do it for you. It should be noted that not all residues n will have inverses modulo m so you'll have to decide what to do about that. — Simon Goater, Dec 28 '22 at 19:30
Also, instead of `((a * b) % m * c) % m)` you could write `(((a%m) * (b%m)) % m * (c%m)) % m)` — Stef, Dec 28 '22 at 19:34
See [Modular Inverse Built-In, C++](https://stackoverflow.com/questions/65653209/modular-inverse-built-in-c) for a boost library function that computes the modular inverse. — Stef, Jan 17 '23 at 15:12

score 0 · Answer 1 · edited Jan 09 '23 at 06:05

Idea is to keep removing the common factors in numerator and denominator by calculating gcd and dividing it out. It is illustrated in following python code. In C++, gcd can be easily calculated using extended euclid's algorithm.

import math
def prod(a,b,c,n):
    num = [a,b,c]
    p = 1
    tmp = n
    for i in range(len(num)):
       g = math.gcd(num[i],tmp)
       num[i] /= g
       tmp /= g
       p = (p*num[i]) % n
    return p

Calculate large multiplication and divide under modulus

1 Answers1