2
$\begingroup$

What is the fastest known time complexity for computing central trinomial coefficients?

Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$.

It can be shown that, if $n$ is prime, then $C_n=1 \pmod n$, because by the binomial theorem

$$(x + y)^n=\sum_{k=0}^{n} \binom{n}{k}y^kx^{n-k}=x^n+y^n\pmod n$$ so that

$$(x^2+x+1)^n = x^2+x+1\pmod n$$

follows.

The computational complexity problem I am aiming on solving is, given a large integer $n$ (say, about RSA size), I would like to verify that the congruence

$C_n=1\pmod n$

in polynomial time analogous to how $x^n=x \pmod n$ can be computed using binary exponentiation.

Thanks for help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.