Is there an efficient way to calculate $a! \bmod b$ for arbitrarily large $a < b$?

Question

I am trying to find a way to calculate $a! \bmod b$ where $0<a<b$ for arbitrarily large $a$. Is there an efficient way to do this without calculating $a!$ explicitly?

Answer 1

n! becomes large already for small values of n so storage quickly becomes an issue if we were to calculate and store the whole number before doing modulus. The idea by Mose Wintner in the comments avoids having to store the whole number which is really nice, although we can also do it pairwise and in any order, say for instance $$(1 \cdot 2) (3 \cdot 4) (5 \cdot 6) (7 \cdot 8) (\text{mod 11})$$ Which is equal to $$(1 \cdot 2 (\text{mod 11})) (3 \cdot 4 (\text{mod 11})) (5 \cdot 6 (\text{mod 11})) (7 \cdot 8 (\text{mod 11}))$$

This way if $n$ is large and we have a many core computer we can do each multiply-modulus independently and then recurse on the previous products, halving the numbers of factors in each step.

---

Implementing Mose Wintner's idea in the C language with 4 pthreads on my 2 core computer for $$100000001 ! = 68124726 (\text{mod } 179425133)$$ takes about 2 seconds, but that is while I am doing a bunch of other batch jobs at the same time. I don't have any symbolic or big int precision software to compare against, but it should be within the 64 bit "long" margin ( I think ). I checked it for some smaller numbers and it gave me the same results as octave but I needed to increase the size to be able to measure the speed as it was too fast to measure speed reliably for the smaller numbers.

Answer 2

There are certain cases you can evaluate easily however for most cases you would need to evaluate it recursively. Apply the mod after each recursive step will help with the storage of the value.

Special cases:

The answer will be zero if there are sufficient terms to cover the prime factorization of $b$. E.g. If $b=72$ you need three factors of 2 and two factors of 3.

If $b$ is prime and $a=b-1$ then the answer is $a-1$.

If $b$ is prime and $a=b-2$ then the answer is 1.

Answer 3

With "arbitrarily large" I assume a >> $10^{12}$ or something like that? Which means that b is large as well?

I would start by factoring b; if b has a factor $p^k$ with p ≤ a then we may be able to prove that a! = 0 (modulo $p^k$). Even if that is not the case, calculating a! modulo x on a current computer will be a lot faster if x < $2^{64}$. Various results can then be combined.

We now assume that we want a! (modulo b) where a < b and b cannot be reasonably factored. We can obviously calculate a product of a huge number of integers (modulo b) by performing every single multiplication modulo b. If $a^2$ < b then we can multiply numbers in pairs.

When a is large, we would try to distribute the calculation over multiple processors, which is quite trivial. We would also perform multiple multiplications (modulo b) in parallel to use each processor's ability to perform multiple operations in parallel.

To calculate (ax) modulo b, we would need to calculate ax, divide by b, round down to an integer, and subtract that integer times b from the product. It will be faster to calculate 1/b once, and it may be faster not to round (ax / b) down, but to round (ax * (1/b)) to a nearby integer. We don't actually need (ax) modulo b, it is good enough if we have a small number z with z modulo b = (ax) modulo b.