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

3

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.

0

it can be optimized to run in polynomial time

https://en.wikipedia.org/wiki/AKS_primality_test

-1

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.

  • 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.2012-01-20
  • 0
    @PeterTaylor pedja want : "Can it be optimized to runs in polynomial time ?" so it works because O(√n) is better that polynomial!2012-01-20
  • 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.2012-01-20
  • 0
    @GerryMyerson really you cant see the optimization? pedja's algorithm is is O(p!) and my algorithm is O(√n)! can you see the difference?2012-01-20
  • 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?2012-01-20
  • 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 :)2012-01-20
  • 0
    @Jyrki Lahtonen, The base idea are same, both on same theorem, just OP currently can't find the way to handle it in P. is there something wrong? do you think OP should solve it himself in $P$? to have same similarity?2012-01-20
  • 0
    @Saeed This is a continuation of the OPs [prior question](http://math.stackexchange.com/q/100222/242) where some of these topics were already discussed.2012-01-20