What is the most efficient way to compute factorials modulo a prime?

Question Detail: 

Do you know any algorithm that calculates the factorial after modulus efficiently?

For example, I want to program:

for(i=0; i<5; i++)   sum += factorial(p-i) % p; 

But, p is a big number (prime) for applying factorial directly $(p \leq 10^ 8)$.

In Python, this task is really easy, but i really want to know how to optimize.

Asked By : jonaprieto

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1495

Answered By : Gilles

(This answer was initially posted by the asker d555 inside the question.)

I remember Wilson's theorem, and I noticed little things:

In the above program, it is better if I write: $$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\ (p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\ \ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}} &\pmod p\\ \end{align}$$

And you can find $(p-i)^{-1}$ because $\operatorname{gcd}(p, p-i) = 1$, so with the extended Euclidian algorithm you can find the value of $(p-i)^{-1}$, that is the inverse modulus.

You can view the same congruences too, like to: $$\begin{align*} (p-5)! &\equiv (p-24)^{-1}&\pmod p\\ (p-4)! &\equiv (p+6)^{-1}&\pmod p\\ (p-3)! &\equiv (p-2)^{-1} &\pmod p\\ (p-2)! &\equiv 1&\pmod p\\ (p-1)! &\equiv -1&\pmod p\\ \end{align*} $$ so, the sum is equal: $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ and if you factorize in the beginning the factorials you get $$ 8\cdot (-24)^{-1} \pmod p$$ And, voila, inverse modulus is more efficient than factorials.