Let $M$ be a square matrix with integer entries. Then **Fermat's little theorem for matrices** holds:

$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$

This follows by an examination of the action of the Frobenius map on the roots of the characteristic polynomial of $M$ over a splitting field; there is also a combinatorial proof. (Incidentally, I have no idea who to credit for this result.)

This suggests the following definition generalizing the notion of Fermat pseudoprime, the notion of Fibonacci pseudoprime (it feels to me like the Wikipedia article has the names backwards), and the notion of Perrin pseudoprime: a **pseudoprime to base $M$** is a positive integer $n$ such that

$$\text{tr}(M^n) \equiv \text{tr}(M) \bmod n.$$

This definition appears to be related to Grantham's notion of Frobenius pseudoprime, although it might be weaker. For concreteness, let $M$ be the companion matrix of your favorite monic irreducible polynomial over $\mathbb{Z}$.

Anyway, this looks like a reasonable primality test to me (choose random matrices, exponentiate them, etc.), but I don't really know anything about the subject. Does this notion appear anywhere in the literature? How does it compare to other primality tests?