Can this primality test be optimized to runs in polynomial time?

Question

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 :

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

Can it be optimized to runs in polynomial time ?

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