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).

2 added 175 characters in body

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?

1

# 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.

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?