Résumé
For a given computational problem, a certificate is a piece of data that one(the prover) attaches to the output with the aim of allowing efficientverification (by the verifier) that this output is correct. Here, weconsider the minimal approximant basis problem, for which the fastest knownalgorithms output a polynomial matrix of dimensions $m \times m$ and averagedegree $D/m$ using $O\tilde{~}(m^\omega \frac{D}{m})$ field operations. Wepropose a certificate which, for typical instances of the problem, iscomputed by the prover using $O(m^\omega \frac{D}{m})$ additional fieldoperations and allows verification of the approximant basis by a Monte Carloalgorithm with cost bound $O(m^\omega + m D)$. Besides theoretical interest, our motivation also comes from the fact thatapproximant bases arise in most of the fastest known algorithms for linearalgebra over the univariate polynomials; thus, this work may help indesigning certificates for other polynomial matrix computations.Furthermore, cryptographic challenges such as breaking records for discretelogarithm computations or for integer factorization rely in particular oncomputing minimal approximant bases for large instances: certificates canthen be used to provide reliable computation on outsourced and error-proneclusters.