  We present algorithms and heuristics to compute the characteristic polynomial
of a matrix given its minimal polynomial. The matrix is represented as a
black-box, i.e., by a function to compute its matrix-vector product. The
methods apply to matrices either over the integers or over a large enough
finite field. Experiments show that these methods perform efficiently in
practice. Combined in an adaptive strategy, these algorithms reach significant
speedups in practice for some integer matrices arising in an application from
graph theory.
