https://hal-unilim.archives-ouvertes.fr/hal-01701861v1Giorgi, PascalPascalGiorgiECO - Exact Computing - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiqueNeiger, VincentVincentNeigerXLIM-MATHIS - Mathématiques & Sécurité de l'information - XLIM - XLIM - UNILIM - Université de Limoges - CNRS - Centre National de la Recherche ScientifiqueCertification of minimal approximant basesHAL CCSD2018Certificationminimal approximant basisorder basispolynomial matrixtruncated product[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Neiger, Vincent2018-02-06 11:34:022022-08-05 15:02:582018-02-06 15:51:13enPreprints, Working Papers, ...https://hal-unilim.archives-ouvertes.fr/hal-01701861v1application/pdf1Considering a given computational problem, a certificate is a piece ofadditional data that one attaches to the output in order to help verifying thatthis output is correct. Certificates are often used to make the verificationphase significantly more efficient than the whole (re-)computation of theoutput. Here, we consider the minimal approximant basis problem, for which thefastest known algorithms compute a polynomial matrix of dimensions $m\times m$and average degree $D/m$ using $O\tilde{~}(m^\omega \frac{D}{m})$ fieldoperations. In the usual setting where the matrix to approximate has $n$columns with $n\le m$, we provide a certificate of size $m n$, which can becomputed in $O(m^\omega \frac{D}{m})$ operations and which allows us to verifyan approximant basis by a Monte Carlo algorithm with cost bound $O(m^\omega +mD)$. 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.