# Is n! mod p doable in sub O(n) time?

I ask because I can use Lucas Theorem to find n choose k mod p but don't know of an equivalent for permutations (n permute k mod p).

-
For fixed $p$? $n! \equiv 0 \mod p$ if $n \ge p$. – Robert Israel Jan 7 '13 at 17:04
Sounds like what you want is actually $n(n-1)(n-2)\dotsm(n-k+1) \pmod{p}$. Is that right? – user3533 Jan 7 '13 at 17:05
well i know how to get combinations quickly and i know the only difference between combinations and permutations is a denominator factor of k! – user54089 Jan 7 '13 at 17:09
But working mod $p$ you should be careful, because this denominator might be zero (mod $p$). The expression I wrote it what you want then. Still, if $k\geq p$ it will be zero. – user3533 Jan 7 '13 at 17:10
Yeah, but you can't divide by $k!$ in general, $\pmod p$, if $k\geq p$. For example, in general, $\binom {2p}p\equiv 2 \pmod p$. If you instead compute $(2p)!\equiv 0\pmod p$ and $p!\equiv 0\pmod p$ how are you going to compute $$\frac{(2p)!}{p!p!}$$ mod $p$? – Thomas Andrews Jan 7 '13 at 17:11

If $k\geq p$ then the answer is zero and we're done. Otherwise:

Let $M=\lfloor \sqrt{k}\rfloor$.

1. Define a polynomial: $f(x)=x(x+1)\dotsm (x+M-1)$.
2. There is a divide and conquer algorithm to evaluate $f(x)$ simultaneously at $M$ points (see Modern Computer Algebra / Joachim von zur Gathen, Jürgen Gerhard).
3. We will evaluate it at $n-k+1, n-k+1+M,n-k+1+2M,\dotsc,n-k+1+(M-1)M$.
4. We will get the values of $f(n-k+1), f(n-k+1+M),f(n-k+1+2M),\dotsc,f(n-k+1+(M-1)M)$.
5. Now just multiply all of those values to get $f(n-k+1)\cdot f(n-k+1+M) \cdot f(n-k+1+2M)\dotsm f(n-k+1+(M-1)M)$.
6. If $\sqrt{k}$ is an integer then we're done. Otherwise, we need up to $M$ more multiplications.

The complexity is about $O(\sqrt{p})$ times some logarithmic factors, so it beats the $O(p)$ naive solution. (the botteleck with the logarithmic factors is in Step 3).

-
All numbers should be taken $\pmod{p}$. – user3533 Jan 7 '13 at 18:12
forgive my ignorance but explain p(x) please? – user54089 Jan 7 '13 at 18:26
You want to multiply $k$ numbers. So I divide them to $\sqrt{k}$ groups of $\sqrt{k}$ numbers. The polynomial $p(x)$ is used to evaluate the proudct of $k$ consecutive integers. That's one such block. Step 4 then calculates the product of each such block and step 5 multiplies the products of the blocks to get to product of all $k$ numbers. – user3533 Jan 7 '13 at 18:30
First, I think there is an error in your definition of $p(x) -$ an extra factor of $x$ seems to have snuck in there. Second, in your comment, I think "$k$ consecutive integers" should be "$M$ consecutive integers". Is that right? – TonyK Jan 7 '13 at 20:32
@TonyK: You are right. Edited the post. I can't edited the comment, but it really should be "$M$ consecutive integers". Thanks. – user3533 Jan 7 '13 at 22:07