Hello, Codeforces! Today I've faced the following problem: is it possible to calculate N! modulo M (M is prime) in polynomial (relative to length of M) time? I thought it would be pretty popular problem, but I couldn't google anything useful. Does anybody know such algorithm or proofs that it does not exist?

You can try this algo, if M is not too large.

Thanks, but I'm just curious if the

polynomialalgorithm exists.Actually, you can calculate $$$n! \bmod p$$$ in $$$O(\sqrt{p} \log p)$$$.

See this paper Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator for more details.

wrong

а)

polynomial (relative to length of M) time.if $$$N>=M$$$ then $$$N!$$$ $$$mod$$$ $$$M$$$ $$$=$$$ $$$0$$$.

Else calculate it in $$$O(N)$$$ :P

Am I missing something?

Maybe your's is not in

Lengthof m complexity.Then my questions is what is length of m? Can you please define it?

Is this no of digits in M?

Maybe saying $$$O(logM) == O(logM/log10)$$$ would have been better.

I think so. He may want the solution to be in O(log m).biection can you confirm?

Yes, I want solution to be in O(log^k m) for some k.

This is the problem you are describing, maybe with few extra constraints: https://www.spoj.com/problems/BORING/en/

maybe with few extra constraintsExtra constraints sometimes make life easier.

Notice the constraint

Abs(N-P) < 10^4.My Soln with one unproven lemma.Lemma — $$$(P-1)! \% P = 1$$$.

If the only solns of $$$x^2\%P=1$$$ are $$$-1,1$$$ for prime $$$P$$$ then this lemma holds. $$$(P-D)! \% P = (-1)^{(D-1)}*(P-1)! / (D-1)! \% P$$$

If I'm not mistaken this shall be the problem (even though the constrains are solvable with approach suggested by zimpha ==> so not polynomial in length ^_^ )