, 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

/. #s, 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

B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994.

B. Beckermann and G. Labahn, Fraction-free computation of matrix rational interpolants and matrix gcds, SIAM J. Matrix Anal. Appl, vol.22, pp.114-144, 2000.

B. Beckermann, G. Labahn, and G. Villard, Normal forms for general polynomial matrices, J. Symbolic Comput, vol.41, pp.708-737, 2006.
URL : https://hal.archives-ouvertes.fr/hal-02101933

D. A. Bini and V. Pan, Polynomial and Matrix Computations, Progress in Theoretical Computer Science, Birkhäuser Basel, 1994.

A. Bostan and É. Schost, Polynomial evaluation and interpolation on special sets of points, J. Complexity, vol.21, pp.420-446, 2005.

N. Bourbaki, Commutative Algebra, Elements of Mathematics, 1972.

D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform, vol.28, pp.693-701, 1991.

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput, vol.9, pp.251-280, 1990.

C. Costello, C. Fournet, J. Howell, M. Kohlweiss, B. Kreuter et al., Geppetto: Versatile verifiable computation, 2015 IEEE Symposium on Security and Privacy, pp.253-270, 2015.

R. A. Demillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Inform. Process. Lett, vol.7, pp.193-195, 1978.

J. G. Dumas, V. P. Gerdt, W. Koepf, W. M. Seiler, and . Vorozhtsov, Proof-of-work certificates that can be efficiently computed in the cloud, pp.1-17, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01825779

J. G. Dumas and E. Kaltofen, Essentially optimal interactive certificates in linear algebra, ISSAC '14, ACM, pp.146-153, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00932846

J. G. Dumas, E. Kaltofen, E. Thomé, and G. Villard, 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

J. G. Dumas, D. Lucas, and C. Pernet, Certificates for triangular equivalence and rank profiles, vol.17, pp.133-140, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01466093

J. G. Dumas, C. Pernet, and Z. Sultan, Computing the rank profile matrix, ISSAC '15, ACM, pp.149-156, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01107722

A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, CRYPTO '86, pp.186-194, 1987.

R. Freivalds, Fast probabilistic algorithms, Mathematical Foundations of Computer Science, pp.57-69, 1979.

F. R. Gantmacher, . Chelsea, J. Von-zur-gathen, J. Gerhard, . Cambridge et al., On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 1959.

P. Giorgi and V. Neiger, Certification of minimal approximant bases, ISSAC'18, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701861

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, Delegating computation: Interactive proofs for muggles, STOC '08, pp.113-122, 2008.

S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computing, vol.18, pp.186-208, 1989.

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote, Triangular x-basis decompositions and derandomization of linear algebra algorithms over, 2012.

, J. Symbolic Comput, vol.47, pp.422-453

C. Hermite, 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

C. P. Jeannerod, C. Pernet, and A. Storjohann, 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

T. Kailath, Linear Systems, 1980.

E. L. Kaltofen, B. Li, Z. Yang, and L. Zhi, 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.

E. L. Kaltofen, M. Nehring, and B. D. Saunders, Quadratic-time certificates in linear algebra, ISSAC '11, pp.171-176, 2011.

G. Labahn, V. Neiger, and W. Zhou, 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

L. Gall and F. , Powers of tensors and fast matrix multiplication, pp.296-303, 2014.

C. C. Macduffee, The Theory of Matrices, 1933.

T. Mulders and A. Storjohann, Certified dense linear system solving, Journal of Symbolic Computation, vol.37, pp.485-510, 2004.

V. Neiger, J. Rosenkilde, and G. Solomatov, Computing Popov and Hermite forms of rectangular polynomial matrices, ISSAC '18, ACM, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701867

V. Neiger and T. X. Vu, Computing canonical bases of modules of univariate relations, ISSAC'17, ACM, pp.357-364, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01457979

C. Pernet and W. Stein, 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

V. M. Popov, Invariant description of linear, time-invariant controllable systems, SIAM Journal on Control, vol.10, pp.252-264, 1972.

J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, vol.27, pp.701-717, 1980.

A. Storjohann, High-order lifting and integrality certification, J. Symbolic Comput, vol.36, p.97, 2003.

M. Van-barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992.

G. Villard, Computing Popov and Hermite forms of polynomial matrices, ISSAC'96, ACM, pp.250-258, 1996.

W. Zhou, Fast Order Basis and Kernel Basis Computation and Related Problems, 2012.

W. Zhou and G. Labahn, Computing column bases of polynomial matrices, ISSAC'13, pp.379-386, 2013.

W. Zhou and G. Labahn, Unimodular completion of polynomial matrices, ISSAC'14, ACM, pp.413-420, 2014.

R. Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM'79, pp.216-226, 1979.