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?
 A: 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:


*

*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$.

*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$.

*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.

*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.
