December 13, 2013
This is a trick question. There is no better algorithm, regardless whether the modulus is prime or composite, than to calculate the modulus after each multiplication:
(define (mod-fact n m)
(let loop ((k 2) (p 1))
(if (< n k) p
(loop (+ k 1) (modulo (* p k) m)))))
If it was possible to compute n! (mod m) in polynomial time, then it would be simple to factor integers in polynomial time: Given an integer m, the smallest f such that gcd(f! (mod m), m) > 1 is the smallest prime factor of m. For every n > f, every gcd(n! (mod m), m) is greater than 1, so we can use binary search to find f, reducing the task of factoring integers to the task of computing n! (mod m). Of course, we don’t do that because there is no polynomial-time algorithm to compute modular factorizations.
> (mod-fact 1000000 1001001779)
You might be amused to search for this task on the internet and see the complicated solutions that people have developed in the name of efficiency. You can run the program at http://programmingpraxis.codepad.org/HZwVjALJ.
Pages: 1 2