11
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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/Primality_test#Fast_deterministic_tests $\endgroup$
    – Stopple
    Commented Aug 8, 2012 at 16:01
  • $\begingroup$ This is weaker than the notion of a Szekeres pseudoprime in the linked paper. $\endgroup$
    – Will Sawin
    Commented Aug 8, 2012 at 16:47
  • $\begingroup$ @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. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 8, 2012 at 16:52

1 Answer 1

Reset to default
9
$\begingroup$

I think this is weaker than the notion of Frobenius pseudoprime. The trace of a matrix is the sum of the roots of its characteristic polynomial, so you're testing whether the sum of the roots remains invariant upon raising to the pth power. The Frobenius test is stronger than that.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ In particular, you've made the polynomial arithmetic more complicated than it needs to be by embedding it in a matrix operation. $\endgroup$
    – Jon Grantham
    Commented Aug 8, 2012 at 17:15
  • $\begingroup$ Very good point! Sorry for the silly question. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 8, 2012 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .