### biection's blog

By biection, history, 23 months ago, translation,

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?

• +15

 » 23 months ago, # |   +1 You can try this algo, if M is not too large.
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 Thanks, but I'm just curious if the polynomial algorithm exists.
 » 23 months ago, # | ← Rev. 2 →   +8 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.
 » 23 months ago, # | ← Rev. 3 →   0 wrong
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 а)
 » 23 months ago, # |   +31 polynomial (relative to length of M) time.if $N>=M$ then $N!$ $mod$ $M$ $=$ $0$.Else calculate it in $O(N)$ :PAm I missing something?
•  » » 23 months ago, # ^ |   +5 Maybe your's is not in Length of m complexity.
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 23 months ago, # ^ |   +5 I think so. He may want the solution to be in O(log m).biection can you confirm?
•  » » » » » 23 months ago, # ^ | ← Rev. 3 →   0 Yes, I want solution to be in O(log^k m) for some k.
 » 23 months ago, # |   0 This is the problem you are describing, maybe with few extra constraints: https://www.spoj.com/problems/BORING/en/
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 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$
•  » » 23 months ago, # ^ |   +13 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 ^_^ )