B. Beckermann and G. Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pad?? Approximants, SIAM Journal on Matrix Analysis and Applications, vol.15, issue.3, pp.804-823, 1994.
DOI : 10.1137/S0895479892230031

B. Beckermann, G. Labahn, and G. Villard, Shifted normal forms of polynomial matrices, Proceedings of the 1999 international symposium on Symbolic and algebraic computation , ISSAC '99, pp.189-196, 1999.
DOI : 10.1145/309831.309929

B. Boyer and J. Dumas, Matrix Multiplication Over Word-Size Modular Rings Using Approximate Formulas, ACM Transactions on Mathematical Software, vol.42, issue.3, pp.1-2012, 2016.
DOI : 10.1016/0024-3795(71)90009-7

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, vol.9, issue.3, pp.251-280, 1990.
DOI : 10.1016/S0747-7171(08)80013-2

R. A. Demillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Information Processing Letters, vol.7, issue.4, pp.193-195, 1978.
DOI : 10.1016/0020-0190(78)90067-4

URL : http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA050745&Location=U2&doc=GetTRDoc.pdf

J. Dumas, P. Giorgi, and C. Pernet, Dense Linear Algebra over Word-Size Prime Fields, ACM Transactions on Mathematical Software, vol.35, issue.3, pp.1-1942, 2008.
DOI : 10.1145/1391989.1391992

URL : https://hal.archives-ouvertes.fr/hal-00018223

J. Dumas and E. Kaltofen, Essentially optimal interactive certificates in linear algebra, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.146-153, 2014.
DOI : 10.1145/2608628.2608644

URL : https://hal.archives-ouvertes.fr/hal-00932846

J. Dumas, E. Kaltofen, E. Thomé, and G. Villard, Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pp.199-206, 2016.
DOI : 10.1007/3-540-09519-5_73

URL : https://hal.archives-ouvertes.fr/hal-01266041

J. Dumas, D. Lucas, and C. Pernet, Certificates for Triangular Equivalence and Rank Profiles, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , ISSAC '17, pp.133-140, 2017.
DOI : 10.1145/2755996.2756672

URL : https://hal.archives-ouvertes.fr/hal-01466093

R. Freivalds, Fast probabilistic algorithms, In Mathematical Foundations of Computer Science, vol.74, pp.57-69, 1979.
DOI : 10.1007/3-540-09526-8_5

J. Zur-gathen and J. Gerhard, Modern Computer Algebra (third edition), 2013.

P. Giorgi, Certification of polynomial middle product Available online at https, 2017.

P. Giorgi, C. Jeannerod, and G. Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on Symbolic and algebraic computation , ISSAC '03, pp.135-142, 2003.
DOI : 10.1145/860854.860889

C. Jeannerod, V. Neiger, É. Schost, and G. Villard, Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pp.295-302, 2016.
DOI : 10.1016/j.jsc.2011.12.009

URL : https://hal.archives-ouvertes.fr/hal-01265983

T. Kailath, Linear Systems, 1980.

E. Kaltofen, B. Li, Z. Yang, and L. Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, Journal of Symbolic Computation, vol.47, issue.1, pp.1-15, 2012.
DOI : 10.1016/j.jsc.2011.08.002

E. Kaltofen, M. Nehring, and B. D. Saunders, Quadratic-time certificates in linear algebra, Proceedings of the 36th international symposium on Symbolic and algebraic computation, ISSAC '11, pp.171-176, 2011.
DOI : 10.1145/1993886.1993915

URL : http://www.math.ncsu.edu/%7Ekaltofen/bibliography/11/KNS11.pdf

T. Kimbrel and R. K. Sinha, A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits, Information Processing Letters, vol.45, issue.2, pp.107-110, 1993.
DOI : 10.1016/0020-0190(93)90224-W

T. Kleinjung, C. Diem, A. K. Lenstra, C. Priplata, and C. Stahlke, Computation of a 768-Bit Prime Field Discrete Logarithm, Eurocrypt 2017, pp.185-201
DOI : 10.1109/TIT.1986.1057137

F. and L. Gall, Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.296-303, 2014.
DOI : 10.1145/2608628.2608664

R. Motwani and P. Raghavan, Randomized Algorithms, 1995.

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices, Journal of Symbolic Computation, vol.35, issue.4, pp.377-401, 2003.
DOI : 10.1016/S0747-7171(02)00139-6

URL : https://doi.org/10.1016/s0747-7171(02)00139-6

V. Neiger, Bases of relations in one or several variables: fast algorithms and applications, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01431413

J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM, vol.27, issue.4, pp.701-717, 1980.
DOI : 10.1145/322217.322225

A. Storjohann, Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software, Dagstuhl Seminar Proceedings, 2006.

M. , V. 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.

W. Zhou and G. Labahn, Efficient algorithms for order basis computation, Journal of Symbolic Computation, vol.47, issue.7, pp.793-819, 2012.
DOI : 10.1016/j.jsc.2011.12.009

URL : https://doi.org/10.1016/j.jsc.2011.12.009

W. Zhou and G. Labahn, Computing column bases of polynomial matrices, Proceedings of the 38th international symposium on International symposium on symbolic and algebraic computation, ISSAC '13, pp.379-386, 2013.
DOI : 10.1145/2465506.2465947

W. Zhou and G. Labahn, Unimodular completion of polynomial matrices, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.413-420, 2014.
DOI : 10.1145/2608628.2608640

W. Zhou, G. Labahn, and A. Storjohann, Computing minimal nullspace bases, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC '12, pp.366-373, 2012.
DOI : 10.1145/2442829.2442881