1
$\begingroup$

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?

  • 0
    So let us interpret the problem this way; compute efficiently the product of the odd integers between $\sqrt M$ and $2\sqrt M$, mod $M$. I have no reason to think there's a better way than the direct approach of doing $O(\sqrt M)$ multiplications and reductions.2011-05-25

1 Answers 1

2

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.