Certification of minimal approximant bases

DOI10.1145/3208976.3208991MaRDI QIDQ5120192zbMATH OpenOpenAlexWikidataFDO

Authors Pascal Giorgi, Vincent Neiger

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.01920, https://hal-unilim.archives-ouvertes.fr/hal-01701861v2/file/approx_basis_certification.pdf

zbMATH Keywords

certificationminimal approximant basisorder basispolynomial matrixtruncated product

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Symbolic computation and algebraic computation (68W30)

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 $mimesm$ and average degree $D/m$ using $Oilde(m^{o}megafracDm)$ field operations. We propose a certificate which, for typical instances of the problem, is computed by the prover using $O(m^{o}megafracDm)$ additional field operations and allows verification of the approximant basis by a Monte Carlo algorithm with cost bound $O(m^{o}mega+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.

Recommendations

• Essentially optimal interactive certificates in linear algebra
• Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
• Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
• Quadratic-time certificates in linear algebra
• Certificates for triangular equivalence and rank profiles

Cited in

(4)

• Verification protocols with sub-linear communication for polynomial matrix operations
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Algorithms for linearly recurrent sequences of truncated polynomials
• Corrigimus, verificamus, vincimus: ensuring algorithmic accuracy in an age of uncertainty

This page was built for publication: Certification of minimal approximant bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120192)