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.

Pages: 1 2

Follow

Get every new post delivered to your Inbox.

Join 645 other followers