Modular Factorial
December 13, 2013
This question appears from time to time as an interview question or on the coding-challenge web sites.
Write a function that calculates n! (mod p) when p is prime. Then extend the function to calculate n! (mod m) when m is not prime. Can you calculate the factorials using fewer than n−1 modular multiplications?
For instance, 1000000! (mod 1001001779) is 744950559.
Your task is to write the indicated functions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 