2
$\begingroup$

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 ?

  • 6
    No.${}{}{}{}{}$2012-01-20
  • 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.2012-01-20
  • 0
    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](http://stackoverflow.com/questions/4236673/sample-code-for-fast-primality-testing-in-c-sharp/4236870#4236870).2012-01-20
  • 0
    @Saeed,M.R. is probabilistic test...2012-01-20
  • 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.2012-01-20
  • 0
    @Saeed,you are right...there is similarity between AKS and this test...2012-01-20
  • 1
    It would help readers if you link to your [closely related question](http://math.stackexchange.com/q/100222/242) asked yesterday.2012-01-20

3 Answers 3