Let $p$ be a prime where $-1$ is not a quadratic residue, (no solutions to $m^2 = -1$ in $p$).
I want to find an easily computable expression for
$$\sum_{k=0}^n {n \choose 2k} (-x)^k$$
modulo $p$. With one caveat, all the computations must be done over the integers modulo $p$, no complex numbers.
That is, I'm ruling out the standard trick where you take $(1+xi)^n + (1-xi)^n$ to extract even terms.
I'm looking for any other alternate expressions for this sum. The final expression should not have a sum over $n$ terms and not involve any complex numbers implicitly or explicitly. For example, Chebyshev functions are ruled out, as they implicitly involve a complex power.
Other than that any interesting expressions for the sum over the integers or the integers modulo $p$ are allowed. Can anyone do it?
$\textbf{Rephrase}$
Any way of writing the real part of $(1+xi)^n$ modulo $p$, as $f(x,n)$ for some $f$ that only involves real numbers in the computation and no sum over $n$.
For example, $f(x,n)$ can not be a polynomial in $x^n$ because $f(x,n)$ would be periodic modulo $p-1$ in $n$, while $(1+xi)^n$ would be periodic modulo $p^2-1$ (and not $p-1$). So the function $f$ would have to be quite intricate.
