Arrêt de service lundi 11 juillet de 12h30 à 13h : tous les sites du CCSD (HAL, Epiciences, SciencesConf, AureHAL) seront inaccessibles (branchement réseau à modifier)
Accéder directement au contenu Accéder directement à la navigation

# Certification of minimal approximant bases

1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 efficient verification (by the verifier) that this output is correct. Here, we consider the minimal approximant basis problem, for which the fastest known algorithms output a polynomial matrix of dimensions $m \times m$ and average degree $D/m$ using $O\tilde{~}(m^\omega \frac{D}{m})$ field operations. We propose a certificate which, for typical instances of the problem, is computed by the prover using $O(m^\omega \frac{D}{m})$ additional field operations and allows verification of the approximant basis by a Monte Carlo algorithm with cost bound $O(m^\omega + m D)$. 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.
Keywords :
Type de document :
Communication dans un congrès
Domaine :

Littérature citée [30 références]

https://hal-unilim.archives-ouvertes.fr/hal-01701861
Contributeur : Vincent Neiger Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 mai 2018 - 22:18:18
Dernière modification le : mardi 5 juillet 2022 - 10:04:42
Archivage à long terme le : : mardi 25 septembre 2018 - 18:31:46

### Fichier

approx_basis_certification.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Pascal Giorgi, Vincent Neiger. Certification of minimal approximant bases. ISSAC 2018 - 43rd International Symposium on Symbolic and Algebraic Computation, Jul 2018, New York, United States. pp.167-174, ⟨10.1145/3208976.3208991⟩. ⟨hal-01701861v2⟩

### Métriques

Consultations de la notice

## 890

Téléchargements de fichiers