Let $f(x) \in \mathbb{Z}[x]$ be a monic irreducible polynomial with roots $\alpha_1, ... \alpha_k$, and let $\Delta$ be the discriminant of $f$. For any prime $p \nmid \Delta$, the Frobenius morphism permutes the roots of $f$ in $\mathbb{F}_p$, hence in particular
$$\alpha_1^p + ... + \alpha_k^p \equiv \alpha_1 + ... + \alpha_k \bmod p.$$
(This result is also true for primes dividing the discriminant, but I don't know an algebraic argument, just a combinatorial one.) A positive integer $p \ge 2$ with this property is a kind of pseudoprime with respect to $f$, which I'll call an $f$-pseudoprime. (This is related to but weaker than the notion of a Szekeres pseudoprime or a Frobenius pseudoprime with respect to $f$.) In particular, a Fermat pseudoprime with base $a$ is an $(x-a)$-pseudoprime. If $f$ is quadratic one gets a notion of pseudoprime related to (equivalent to?) the Lucas / Fibonacci pseudoprimes.
A Perrin pseudoprime is an $(x^3 - x - 1)$-pseudoprime, and the smallest Perrin pseudoprime which is not prime is $271441 = 521^2$. In another MO thread Kevin O'Bryant mentioned that Freeman Dyson and others consider the size of this pseudoprime surprising and suspect there might be a good explanation of why it is larger than one might naively expect (akin to the explanation of why $e^{\pi \sqrt{163} }$ is close to an integer).
I'm not convinced this is a phenomenon requiring a deep explanation. Hence what I would like to see is
- A heuristic relating the size of the smallest $f$-pseudoprime which is not prime to the "complexity" of $f$ (to be defined freely)
and either
A computation showing that the result for $f = x^3 - x - 1$ is consistent with the heuristic, or
A computation showing that the result for $f = x^3 - x - 1$ is not consistent with the heuristic, and some speculation about why this should be the case.