Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I ask because I can use Lucas Theorem to find n choose k mod p but don't know of an equivalent for permutations (n permute k mod p).

share|improve this question
5  
For fixed $p$? $n! \equiv 0 \mod p$ if $n \ge p$. –  Robert Israel Jan 7 '13 at 17:04
2  
Sounds like what you want is actually $n(n-1)(n-2)\dotsm(n-k+1) \pmod{p}$. Is that right? –  user3533 Jan 7 '13 at 17:05
    
well i know how to get combinations quickly and i know the only difference between combinations and permutations is a denominator factor of k! –  user54089 Jan 7 '13 at 17:09
    
But working mod $p$ you should be careful, because this denominator might be zero (mod $p$). The expression I wrote it what you want then. Still, if $k\geq p$ it will be zero. –  user3533 Jan 7 '13 at 17:10
    
Yeah, but you can't divide by $k!$ in general, $\pmod p$, if $k\geq p$. For example, in general, $\binom {2p}p\equiv 2 \pmod p$. If you instead compute $(2p)!\equiv 0\pmod p$ and $p!\equiv 0\pmod p$ how are you going to compute $$\frac{(2p)!}{p!p!}$$ mod $p$? –  Thomas Andrews Jan 7 '13 at 17:11
show 8 more comments

1 Answer

up vote 7 down vote accepted

If $k\geq p$ then the answer is zero and we're done. Otherwise:

Let $M=\lfloor \sqrt{k}\rfloor$.

  1. Define a polynomial: $f(x)=x(x+1)\dotsm (x+M-1)$.
  2. There is a divide and conquer algorithm to evaluate $f(x)$ simultaneously at $M$ points (see Modern Computer Algebra / Joachim von zur Gathen, Jürgen Gerhard).
  3. We will evaluate it at $n-k+1, n-k+1+M,n-k+1+2M,\dotsc,n-k+1+(M-1)M$.
  4. We will get the values of $f(n-k+1), f(n-k+1+M),f(n-k+1+2M),\dotsc,f(n-k+1+(M-1)M)$.
  5. Now just multiply all of those values to get $f(n-k+1)\cdot f(n-k+1+M) \cdot f(n-k+1+2M)\dotsm f(n-k+1+(M-1)M)$.
  6. If $\sqrt{k}$ is an integer then we're done. Otherwise, we need up to $M$ more multiplications.

The complexity is about $O(\sqrt{p})$ times some logarithmic factors, so it beats the $O(p)$ naive solution. (the botteleck with the logarithmic factors is in Step 3).

share|improve this answer
    
All numbers should be taken $\pmod{p}$. –  user3533 Jan 7 '13 at 18:12
    
forgive my ignorance but explain p(x) please? –  user54089 Jan 7 '13 at 18:26
    
You want to multiply $k$ numbers. So I divide them to $\sqrt{k}$ groups of $\sqrt{k}$ numbers. The polynomial $p(x)$ is used to evaluate the proudct of $k$ consecutive integers. That's one such block. Step 4 then calculates the product of each such block and step 5 multiplies the products of the blocks to get to product of all $k$ numbers. –  user3533 Jan 7 '13 at 18:30
    
First, I think there is an error in your definition of $p(x) -$ an extra factor of $x$ seems to have snuck in there. Second, in your comment, I think "$k$ consecutive integers" should be "$M$ consecutive integers". Is that right? –  TonyK Jan 7 '13 at 20:32
    
@TonyK: You are right. Edited the post. I can't edited the comment, but it really should be "$M$ consecutive integers". Thanks. –  user3533 Jan 7 '13 at 22:07
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.