# Product of odd integers in Mod M

Does anyone know of any formular or algorithm (that runs sub-linear time) for computing the product of all odd integers in an interval in (mod M), or a similar product?

-
That would depend on the interval (and of course on $M$). What kind of formula is going to give you the product of all the odd integers in the interval $10000\le n\le 10006$, modulo 123456? – Gerry Myerson May 24 '11 at 23:50
What do you really mean with "less than linear time"? – M.B. May 25 '11 at 1:21
– Brandon Carter May 25 '11 at 1:35
@M.B.: The obvious interpretation (to me, at least) is that the OP is looking for an algorithm which is sublinear in the length of the interval. – Brandon Carter May 25 '11 at 1:49
@Brandon Carter: I believe that is the correct interpretation as well. – M.B. May 25 '11 at 1:53

## 1 Answer

I also believe that in general there is no solution that has sublinear complexity. However, here are a few ideas and theorems which can prove useful:

1. It might be resonable to assume that $M$ is (a power of) a prime. Supposing that you know how to factor $M$ (for instance, the $M$ in the input is guaranteed to be prime or you have a number of different products to compute modulo a given $M$) you can get the answer for $M$ by using Chinese Remainder Theorem for the answers modulo powers of primes dividing $M$.

2. If $M$ is odd, you may just as well try to compute the product of all numbers in an interval, not just the odd ones. Indeed, working modulo $M$ you get: \begin{align} \prod_{k=a}^b (2k+1) = \prod_{k=a}^b (M+1 + 2k) = 2^{b-a+1} \prod_{k=a}^b (\frac{M+1}{2} + k) = 2^{b-a+1} \prod_{k=a + \frac{M+1}{2}}^{b+\frac{M+1}{2}} k \end{align} and it's easy to compute $2^x$ modulo $M$.

3. If $M$ is prime, then it suffices to be able to compute factorials. Indeed, you can always assume that the interval you want to multiply is in $[0,M]$ and then the product form of numbers from $a$ to $b$ is just $b! (a!)^{-1}$ and computing inverses is fast.

4. You can get a slight improvement using the identity $(p-1)! = -1 \pmod{p}$ for $p$ prime. In particular, if $a > \frac{p-1}{2}$ you get $$-1 = (p-1)! = a! (a+1)(a+2) \dots (p-1) =$$ $$a! (p - (p - a - 1)) (p - (p - a - 2)) \dots (p - 1) = a! (-1)^{p-a} (p-a-1)!$$ so you can easily compute $a!$ knowing $(p-a-1)!$. Thus, it's enough to know factorials from $1$ to $\frac{p-1}{2}$.

All in all, my suggestion is that it might be best to factor $M$, compute and store the factorials modulo prime factors of $M$ and then be able to give answers for any interval in a reasonably short time (but at the price of a lot preprocessing).

I know it's not much, but I'm afraid that there is no solution in the general case.

-