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

Question

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

Answer 1

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