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.
