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 ?

  • 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.

  • 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