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 $$ 8cdot (-24)^{-1} pmod p$$ And, voila, inverse modulus is more efficient than factorials.