Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

Certification of minimal approximant bases

Pascal Giorgi 1 Vincent Neiger 2 
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Considering a given computational problem, a certificate is a piece of additional data that one attaches to the output in order to help verifying that this output is correct. Certificates are often used to make the verification phase significantly more efficient than the whole (re-)computation of the output. Here, we consider the minimal approximant basis problem, for which the fastest known algorithms compute a polynomial matrix of dimensions $m\times m$ and average degree $D/m$ using $O\tilde{~}(m^\omega \frac{D}{m})$ field operations. 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 be computed in $O(m^\omega \frac{D}{m})$ operations and which allows us to verify an approximant basis by a Monte Carlo algorithm with cost bound $O(m^\omega + mD)$. Besides theoretical interest, our motivation also comes from the fact that approximant bases arise in most of the fastest known algorithms for linear algebra over the univariate polynomials; thus, this work may help in designing certificates for other polynomial matrix computations. Furthermore, cryptographic challenges such as breaking records for discrete logarithm computations or for integer factorization rely in particular on computing minimal approximant bases for large instances: certificates can then be used to provide reliable computation on outsourced and error-prone clusters.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : Vincent Neiger Connectez-vous pour contacter le contributeur
Soumis le : mardi 6 février 2018 - 11:34:02
Dernière modification le : vendredi 5 août 2022 - 15:02:58
Archivage à long terme le : : vendredi 4 mai 2018 - 15:53:35


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01701861, version 1


Pascal Giorgi, Vincent Neiger. Certification of minimal approximant bases. 2018. ⟨hal-01701861v1⟩