Matthew J Ghio <mg5n+@andrew.cmu.edu> writes:
Nope. The ability to take fast modular factorials as you suggest implies the ability to factor large numbers in polynomial time.
If (n!)mod x = 0 then there is a factor of x which is less than n. If you can solve modular factorials, then you can solve for the largest factor of x in logarithmic time. Obviously, nobody has found a method to do either.
I should mention that I am interested in the case (2^n)! mod p where p is a prime and (2^n) << p. In this case no individual term of the factorial will be equal to zero mod p, and since the non-zero residues form a group under multiplication, the result can never be zero either. The ability to solve this special case may also imply the ability to factor large numbers in polynomial time, but in some less obvious way. -- Mike Duvos $ PGP 2.6 Public Key available $