Computing Minimal Polynomials of Matrices

Max Neunhoeffer, Cheryl E. Praeger

We present and analyse a Monte-Carlo algorithm to compute the minimal polynomial of an $n\times n$ matrix over a finite field that requires $O(n^3)$ field operations and O(n) rando…