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$$


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.


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.