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.

Theorem :

Let $k$ be positive integer such that : $k \in [1,\lfloor \sqrt p \rfloor ]$

$\binom{p}{k} \equiv 0 \pmod p$ for all $k$ iff $p$ is a prime number .

Test written in Maple :

enter image description here

Test is general , unconditional , deterministic but it runs in exponential time .

Can it be optimized to runs in polynomial time ?

share|improve this question
6  
No.${}{}{}{}{}$ –  TonyK Jan 20 '12 at 10:36
2  
Given how long it took to prove that primality testing was in P, and how much more complicated AKS primality testing is than this, I highly doubt it. –  Peter Taylor Jan 20 '12 at 10:56
    
What's the usage of this wired primality testing? You can use fast primality testing with miller rabin, and have a good chance. you can see my sample C# code in SO. –  Saeed Jan 20 '12 at 11:34
1  
Currently I see AKS theorem, if you want exact algorithm they solve it in their paper, and is not easy as miller rabin test. In fact you tryed first part of their algorithm, but still it's slower than miller rabin. –  Saeed Jan 20 '12 at 12:43
1  
It would help readers if you link to your closely related question asked yesterday. –  Bill Dubuque Jan 20 '12 at 13:42

2 Answers 2

As a first optimization you could keep the current value of the binomial each time and update it with a multiplication and a division rather than recomputing at each step.

As a next optimization you might realize that each division is exact, so you can use Jebelean-Krandick bidirectional division.

Then you might realize that each step essentially tests if k divides p, and so replace the binomial calculation with a modulus test.

Then you could run the test over only the primes k up to $\sqrt p$.

So after all these optimizations, you are left with trial division, which runs in exponential time.

share|improve this answer

You can use dynamic programming I mean instead of compute binomial(p,k) in each loop use this one : temp := temp * (p - k+1) / k;. and at the start of the program set temp to 1

I used this fact : binomial(p,k) = binomial(p,k-1) * (p-k+1) / k.

share|improve this answer
3  
But that doesn't help, because performing $O(1)$ work for each of $\sqrt{n}$ candidates is already exponential time, as $\sqrt{n}$ is exponential in $\log(n)$, which is the input size. –  Peter Taylor Jan 20 '12 at 10:54
    
@PeterTaylor pedja want : "Can it be optimized to runs in polynomial time ?" so it works because O(√n) is better that polynomial! –  Ali Amiri Jan 20 '12 at 10:57
7  
No, Ali, as Peter said, $\sqrt n$ is exponential in the input size, which is $\log n$. Otherwise, you could just do trial division up to $\sqrt n$ and tell everyone you have a polynomial time factorization algorithm and become fabulously wealthy. –  Gerry Myerson Jan 20 '12 at 11:03
1  
@Ali, yes, I can see the difference between $p!$ and $\sqrt n$. Can you see that $\sqrt n$ is not better than polynomial time, but much, much worse than polynomial time? –  Gerry Myerson Jan 20 '12 at 11:54
6  
Since the discussion got a bit off topic and more agressive, lets get back to the original point: The optimization proposed in the answer optimizes the runtime from $k!$ to $\sqrt{k}$, which is awesome! But: time and space complexity are measured in input length, and input length $n = \log k$, so the time complexity of the algorithm is $\sqrt{k} = \sqrt{2^n}$. Therefore the optimized version has the time complexity $O(\sqrt{2^n})$ which is not polynomial. Now please be nice to eachother :) –  Mike B. Jan 20 '12 at 14:17

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.