For what irreducible $f\in\mathbb{Q}[X]$ is this sequence periodic modulo $f$? This is just an interesting problem I found in an old notebook of mine:

Given an irreducible $f\in\mathbb{Q}[X]$, is there a way to determine whether
  the sequence $(p_n)_{n=0}^{\infty}\subset \mathbb{Q}[X]$ given by:
  $$p_0=X$$ $$p_{n+1}=p_n^2-2$$ is periodic modulo $f$, without first having to determine the roots of $f$?

I've only found a way which involves finding the exact roots and that's nearly impossible for $\deg f\ge 5$.
The direct formula for $p_n$ might be useful:
$$p_n=\left(\frac X2+\frac12\sqrt{X^2-4}\right)^{2^n}+\left(\frac{X}{2}-\frac12\sqrt{X^2-4}\right)^{2^n}$$

My method using the roots
For anyone interested, here's my method, which relies on finding the exact roots of $f$.
Given an irreducible polynomial $f\in\mathbb{Q}[X]$ with $f\neq X$ such that $(p_n)_{n=1}^{\infty}$ is periodic with period $d$, let $\alpha$ be a root of $f$ and define $(a_{n})_{n=1}^{\infty}$ by:
$$a_n=p_n(\alpha)$$
We can also define $(a_{n})_{n=1}^{\infty}$ by:
$$a_0=\alpha$$
$$a_{n+1}=a_n^2-2$$
and if we take $\beta$ with $\alpha=\beta+\beta^{-1}$, then it can easily be shown via induction that 
$$a_n=\beta^{2^n}+\beta^{-2^n}$$
Suppose $|\beta|\neq 1$. If $|\beta|<1$, exchange $\beta$ and $\beta^{-1}$, so we can be sure that $|\beta|>1$ and $|\beta^{-1}|<1$. It follows that:
$$|\alpha|=\lim_{k\to\infty} |a_{kd}|=\lim_{k\to\infty}|\beta^{2^{kd}}+\beta^{-2^{kd}}|=\infty$$
Which is a contradiction. Therefore, $\beta=e^{i\gamma}$ for some $\gamma\in\mathbb{R}$ and:
$$a_n=e^{i\gamma n}+e^{-i\gamma n}=2\cos(\gamma n)$$
Which is only periodic if $\gamma$ is a rational multiple of $2\pi$. The only $f$ we have't checked is $f=X$, but it is easily seen that $p_n\equiv 2\pmod X$ for all $n$. So $(p_n)_{n=1}^{\infty}$ can only be periodic modulo $f$ when all the roots of $f$ are of the form:
$$2\cos\left(\frac{2\pi p}{q}\right)$$
for some $p/q\in\mathbb{Q}$.

On the other hand, if for some $p/q\in\mathbb{Q}$ we take
$$\alpha:=2\cos\left(\frac{2\pi p}{q}\right)$$
Then we can define $(a_n)_{n=1}^{\infty}$ as before and show it's periodic, say with period $d$. For all $k,m$, we now have:
$$p_k(\alpha)=p_{k+md}(\alpha)\implies (p_{k+md}-p_k)(\alpha)=0$$
and since for $m\neq 0$, we have $\deg p_k\neq \deg p_{k+md}$, it follows that $f^{\alpha}_{\mathbb{Q}}\mid p_{k+md}-p_k$.
This implies that all such $\alpha$ are algebraïc over $\mathbb{Q}$ and if a monic irreducible $f\in\mathbb{Q}[X]$ has just one root of the form
$$2\cos\left(\frac{2\pi p}{q}\right)$$
then all of its roots are of this form (because it's a unity times $f^{\alpha}_{\mathbb{Q}}$, the sequence is periodic modulo $f^\alpha_{\mathbb{Q}}$ and can only be periodic if all roots are of this form.
 A: Well, using the criterion you have found, you can just check whether $f$ is the minimal polynomial of $2\cos\left(\frac{2\pi p}{q}\right)$ for any $p/q\in\mathbb{Q}$.  If $p/q$ is in lowest terms, then the Galois conjugates of $2\cos\left(\frac{2\pi p}{q}\right)$ are all the numbers of the form $2\cos\left(\frac{2\pi p'}{q}\right)$ where $p'/q$ is in lowest terms.  Note that $x+1/x=2\cos\left(\frac{2\pi p}{q}\right)$ iff $x=e^{\pm 2\pi i p/q}$, so if $f$ is the minimal polynomial of $2\cos\left(\frac{2\pi p}{q}\right)$, then  $g(x)=x^{\deg f}f(x+1/x)$ has exactly the primitive $q$th roots of unity as its roots, so it is the $q$th cyclotomic polynomial.  Conversely, if $g$ is the $q$th cyclotomic polynomial, then we see that $2\cos\left(\frac{2\pi p}{q}\right)$ is a root of $f$.
So, a necessary and sufficient condition for your sequence to be periodic mod $f$ is for $g$ to be a cyclotomic polynomial.  To test this, you can just compute the cyclotomic polynomials $\Phi_q$ for all the finitely many values of $q$ such that $\varphi(q)=\deg g=2\deg f$ (see Only finitely many $n$ such that $\phi(n) = m$ for how to find those finitely many values of $q$) and see whether any of them are equal to $g$.
