, Note that this only communicates O(n) field elements, and that the Verifier's cost at these steps amounts to the evaluation of A and B at ? as well as two scalar vector-matrix products, hence a total of O(mnd A + nd B ) operations. Then the Verifier and Prover's costs follow from Theorems 3.3 and 6.6. Note that rank( A) ? and
A) RowSp F(x) (B). Lemma 6.5. Now assume that the three items hold. Consider some left kernel basis K of A. Then, rank(K) = m ? rank( A) ? by the first item, while the second item implies that the row space of B is contained in the row space of K, hence = rank(B) ? rank(K); therefore rank(K) = . As a result, B = UK for some nonsingular U ? F, For Step 5, assume now that rank(A) ? and B is saturated, and in particular rank(B) = , but that RowSp F(x), p.1 ,
A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994. ,
Fraction-free computation of matrix rational interpolants and matrix gcds, SIAM J. Matrix Anal. Appl, vol.22, pp.114-144, 2000. ,
Normal forms for general polynomial matrices, J. Symbolic Comput, vol.41, pp.708-737, 2006. ,
URL : https://hal.archives-ouvertes.fr/hal-02101933
Polynomial and Matrix Computations, Progress in Theoretical Computer Science, Birkhäuser Basel, 1994. ,
Polynomial evaluation and interpolation on special sets of points, J. Complexity, vol.21, pp.420-446, 2005. ,
Commutative Algebra, Elements of Mathematics, 1972. ,
On fast multiplication of polynomials over arbitrary algebras, Acta Inform, vol.28, pp.693-701, 1991. ,
Matrix multiplication via arithmetic progressions, J. Symbolic Comput, vol.9, pp.251-280, 1990. ,
Geppetto: Versatile verifiable computation, 2015 IEEE Symposium on Security and Privacy, pp.253-270, 2015. ,
A probabilistic remark on algebraic program testing, Inform. Process. Lett, vol.7, pp.193-195, 1978. ,
Proof-of-work certificates that can be efficiently computed in the cloud, pp.1-17, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01825779
Essentially optimal interactive certificates in linear algebra, ISSAC '14, ACM, pp.146-153, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-00932846
Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix, vol.16, pp.199-206, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01266041
Certificates for triangular equivalence and rank profiles, vol.17, pp.133-140, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01466093
Computing the rank profile matrix, ISSAC '15, ACM, pp.149-156, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01107722
How to prove yourself: Practical solutions to identification and signature problems, CRYPTO '86, pp.186-194, 1987. ,
Fast probabilistic algorithms, Mathematical Foundations of Computer Science, pp.57-69, 1979. ,
On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 1959. ,
Certification of minimal approximant bases, ISSAC'18, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01701861
Delegating computation: Interactive proofs for muggles, STOC '08, pp.113-122, 2008. ,
The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computing, vol.18, pp.186-208, 1989. ,
Triangular x-basis decompositions and derandomization of linear algebra algorithms over, 2012. ,
, J. Symbolic Comput, vol.47, pp.422-453
Sur l'introduction des variables continues dans la théorie des nombres, Journal für die reine und angewandte Mathematik, vol.41, pp.191-216 ,
Rank-profile revealing gaussian elimination and the CUP matrix decomposition, J. Symbolic Comput, vol.56, pp.46-68, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00655543
Linear Systems, 1980. ,
Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symbolic Comput, vol.47, pp.1-15, 2012. ,
Quadratic-time certificates in linear algebra, ISSAC '11, pp.171-176, 2011. ,
Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, J. Complexity, vol.42, pp.44-71, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01345627
Powers of tensors and fast matrix multiplication, pp.296-303, 2014. ,
The Theory of Matrices, 1933. ,
Certified dense linear system solving, Journal of Symbolic Computation, vol.37, pp.485-510, 2004. ,
Computing Popov and Hermite forms of rectangular polynomial matrices, ISSAC '18, ACM, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01701867
Computing canonical bases of modules of univariate relations, ISSAC'17, ACM, pp.357-364, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01457979
Fast computation of Hermite normal forms of random integer matrices, Journal of Number Theory, vol.130, pp.1675-1683, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00798442
Invariant description of linear, time-invariant controllable systems, SIAM Journal on Control, vol.10, pp.252-264, 1972. ,
Fast probabilistic algorithms for verification of polynomial identities, J. ACM, vol.27, pp.701-717, 1980. ,
High-order lifting and integrality certification, J. Symbolic Comput, vol.36, p.97, 2003. ,
A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992. ,
Computing Popov and Hermite forms of polynomial matrices, ISSAC'96, ACM, pp.250-258, 1996. ,
Fast Order Basis and Kernel Basis Computation and Related Problems, 2012. ,
Computing column bases of polynomial matrices, ISSAC'13, pp.379-386, 2013. ,
Unimodular completion of polynomial matrices, ISSAC'14, ACM, pp.413-420, 2014. ,
Probabilistic algorithms for sparse polynomials, EUROSAM'79, pp.216-226, 1979. ,