,
, , vol.1
mod R), X) Let us prove correctness. Since Q = Q A × Q B , we may assume without loss of generality that our multiplication matrices are block diagonal, with two blocks corresponding respectively References Alonso, vol.1, pp.1-15, 1996. ,
On the complexity of the F5 Gröbner basis algorithm, J. Symbolic Comput, vol.70, pp.49-70, 2015. ,
The shape of the Shape Lemma, ISSAC'94, ACM, pp.129-133, 1994. ,
Radical computations of zero-dimensional ideals and real root counting, Mathematics and Computers in Simulation, vol.42, pp.561-569, 1996. ,
A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994. ,
The Magma algebra system. I. The user language, J. Symbolic Comput, vol.24, pp.235-265, 1997. ,
Fast computation of special resultants, J. Symbolic Comput, vol.41, pp.1-29, 2006. ,
URL : https://hal.archives-ouvertes.fr/inria-00000960
Fast algorithms for zero-dimensional polynomial systems using duality, Appl. Algebra Engrg. Comm. Comput, vol.14, pp.239-272, 2003. ,
URL : https://hal.archives-ouvertes.fr/inria-00072296
Fast solution of Toeplitz systems of equations and computation of Padé approximants, Journal of Algorithms, vol.1, pp.259-295, 1980. ,
Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp, vol.62, pp.333-350, 1994. ,
A new efficient algorithm for computing Gröbner bases without reductions to zero (F5), in: ISSAC'02, ACM, pp.75-83, 2002. ,
Polynomial systems solving by fast linear algebra, 2013. ,
Sub-cubic change of ordering for Gröbner basis: a probabilistic approach, pp.170-177, 2014. ,
Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput, vol.16, pp.329-344, 1993. ,
, Sparse FGLM algorithms. J. Symbolic Comput, vol.80, pp.538-569, 2017.
On the complexity of the generalized MinRank problem, J. Symbolic Comput, pp.30-58, 2013. ,
Algebraic solution of systems of polynomial equations using Gröbner bases, pp.247-257, 1989. ,
On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 2003. ,
URL : https://hal.archives-ouvertes.fr/hal-02101878
Online order basis algorithm and its impact on the block Wiedemann algorithm, pp.202-209, 2014. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01232873
Linear Systems, 1980. ,
Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, vol.64, pp.777-806, 1995. ,
On the complexity of computing determinants, pp.13-27, 2001. ,
URL : https://hal.archives-ouvertes.fr/hal-02102099
On the complexity of computing determinants, Comput. Complexity, vol.13, pp.91-130, 2004. ,
URL : https://hal.archives-ouvertes.fr/hal-02102099
Fast algorithms for the characteristic polynomial, Theoret. Comput. Sci, vol.36, pp.309-317, 1985. ,
Solving large sparse linear systems over finite fields, Adv. in Cryptography, Crypto '90, pp.109-133, 1990. ,
The Algebraic Theory of Modular Systems, 1916. ,
On multiplicities in polynomial system solving, Trans. Amer. Math. Soc, vol.348, pp.3283-3321, 1996. ,
Autour de la fonction de Hilbert-Samuel (escaliers d'idéaux polynomiaux), 1991. ,
Solving Polynominal Systems Using Continuation for Engineering and Scientific Problems, 1988. ,
Isolated points, duality and residues, Journal of Pure and Applied Algebra, vol.117, pp.469-493, 1997. ,
URL : https://hal.archives-ouvertes.fr/inria-00125278
Bases of relations in one or several variables: fast algorithms and applications, vol.17, pp.313-328, 2016. ,
URL : https://hal.archives-ouvertes.fr/tel-01431413
On the complexity of computing with zero-dimensional triangular sets, J. Symbolic Comput, vol.50, pp.110-138, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00825847
Solving zero-dimensional systems through the Rational Univariate Representation, Appl. Algebra Engrg. Comm. Comput, vol.9, pp.433-461, 1999. ,
URL : https://hal.archives-ouvertes.fr/inria-00098872
Extension of the Berlekamp-Massey algorithm to N dimensions, Information and Computation, vol.84, pp.207-239, 1990. ,
Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput, vol.17, pp.371-391, 1994. ,
Efficient computation of minimal polynomials in algebraic extensions of finite fields, ISSAC'99, ACM, pp.53-58, 1999. ,
NTL: A library for doing number theory, 2018. ,
Direct solution of the (11,9,8)-MinRank problem by the block Wiedemann algorithm in Magma with a Tesla GPU, PASCO'15, ACM, pp.2-6, 2015. ,
High-order lifting and integrality certification, J. Symbolic Comput, vol.36, pp.613-648, 2003. ,
FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package, 2019. ,
, Linbox: Linear algebra over black-box matrices, 2018.
Black box linear algebra with the LINBOX library, p.31, 2002. ,
A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992. ,
Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems, ISSAC'97, ACM, pp.32-39, 1997. ,
A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, 1997. ,
Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory IT, vol.32, pp.54-62, 1986. ,
Linear Multivariable Systems, Applied Mathematical Sciences, vol.11, 1974. ,