blyat's blog

Polynomial calculation of N! modulo M

By blyat, history, 5 years ago, translation, In English

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?

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks, but I'm just curious if the polynomial algorithm exists.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

wrong

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe your's is not in Length of m complexity.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    maybe with few extra constraints
    Extra constraints sometimes make life easier.

    Notice the constraint Abs(N-P) < 10^4.

    My Soln with one unproven lemma.
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 ^_^ )

    → Reply