MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Does this notion of pseudoprime relative to a matrix appear in the literature?

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?

-
 An example would be a nice addition to this question. The problem with new primality tests is that under reasonable practical hypotheses (such as the Generalized Riemann Hypothesis), existing tests are already as good as one can hope for, see en.wikipedia.org/wiki/… – Stopple Aug 8 at 16:01 This is weaker than the notion of a Szekeres pseudoprime in the linked paper. – Will Sawin Aug 8 at 16:47 @Will: good point! But it's not much weaker. It suffices to replace the computation of the trace by the computation of the characteristic polynomial, and to do this it suffices to test the bases $M, M+1, M+2, ... M + (d-1)$ (where $M$ is a $d \times d$ matrix), at least if $n$ is sufficiently large compared to $d$. @Stopple: I'm not hoping that this will be an improvement over existing algorithms; it just seems like a nice example for pedagogical purposes and I am wondering whether people already use it this way. – Qiaochu Yuan Aug 8 at 16:52