Sparse FGLM algorithms

Journal of Symbolic Computation - Tập 80 - Trang 538-569 - 2017
Jean-Charles Faugère1, Chenqi Mou2,1
1Sorbonne Universités, UPMC Univ Paris 06, CNRS, INRIA, Laboratoire d'Informatique de Paris 6 (LIP6), Équipe PolSys, 4 place Jussieu, 75005 Paris, France
2LMIB & School of Mathematics and Systems Science, BeiHang University, Beijing, 100191, China

Tài liệu tham khảo

Bardet, 2004 Bardet, 2015, On the complexity of the F5 Gröbner basis algorithm, J. Symb. Comput., 70, 49, 10.1016/j.jsc.2014.09.025 Basiri, 2003, Changing the ordering of Gröbner bases with LLL: case of two variables, 23 Bayer, 1987, A theorem on refining division orders by the reverse lexicographic order, Duke Math. J., 55, 321, 10.1215/S0012-7094-87-05517-7 Becker, 1994, The shape of the shape lemma, 129 Becker, 1993, Gröbner Bases: a Computational Approach to Commutative Algebra Berthomieu, 2015, Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences, 61 Bras-Amorós, 2006, The correction capability of the Berlekamp–Massey–Sakata algorithm with majority voting, Appl. Algebra Eng. Commun. Comput., 17, 315, 10.1007/s00200-006-0015-8 Brent, 1980, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 259, 10.1016/0196-6774(80)90013-9 Buchberger, 1985, Gröbner bases: an algorithmic method in polynomial ideal theory, 184 Buchmann, 2006, A zero-dimensional Gröbner basis for AES-128, 78 Collart, 1997, Converting bases with the Gröbner walk, J. Symb. Comput., 24, 465, 10.1006/jsco.1996.0145 Cox, 1998 Dahan, 2008, Change of order for regular chains in positive dimension, Theor. Comput. Sci., 392, 37, 10.1016/j.tcs.2007.10.003 Eisenbud, 1995, Commutative Algebra: with a View Toward Algebraic Geometry, vol. 150 Faugère, 1999, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 61, 10.1016/S0022-4049(99)00005-5 Faugère, 2002, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), 75 Faugère, 2013, Using symmetries in the index calculus for elliptic curves discrete logarithm, J. Cryptol., 27, 595, 10.1007/s00145-013-9158-5 Faugère, 2014, Sub-cubic change of ordering for Gröbner basis: a probabilistic approach, 170 Faugère, 1993, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16, 329, 10.1006/jsco.1993.1051 Faugère, 2011, Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices, 115 Faugère, 2010, Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology, 257 Faugère, 2012, Critical points and Gröbner bases: the unmixed case, 162 Feng, 1993, Decoding algebraic-geometric codes up to the designed minimum distance, IEEE Trans. Inf. Theory, 39, 37, 10.1109/18.179340 Galligo, 1974 Høholdt, 1998 Jonckheere, 1989, A simple Hankel interpretation of the Berlekamp–Massey algorithm, Linear Algebra Appl., 125, 65, 10.1016/0024-3795(89)90032-3 Kaltofen, 1991, Processor efficient parallel solution of linear systems over an abstract field, 180 Lasserre, 2013, Moment matrices, border bases and real radical computation, J. Symb. Comput., 51, 63, 10.1016/j.jsc.2012.03.007 Lazard, 1983, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, 146 Lazard, 1992, Solving zero-dimensional algebraic systems, J. Symb. Comput., 13, 117, 10.1016/S0747-7171(08)80086-7 Loustaunau, 1997, On the decoding of cyclic codes using Gröbner bases, Appl. Algebra Eng. Commun. Comput., 8, 469, 10.1007/s002000050084 Miller, 2005, Combinatorial Commutative Algebra, vol. 227 Morgan, 1987 Mou, 2012, Design of termination criterion of BMS algorithm for lexicographical ordering, J. Comput. Appl., 32, 2977 Pardue, 1994 Pascal, 2006, Change of order for bivariate triangular sets, 277 Rouillier, 1999, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 433, 10.1007/s002000050114 Saints, 2002, Algebraic-geometric codes and multidimensional cyclic codes: a unified theory and algorithms for decoding using Gröbner bases, IEEE Trans. Inf. Theory, 41, 1733, 10.1109/18.476246 Sakata, 1988, Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array, J. Symb. Comput., 5, 321, 10.1016/S0747-7171(88)80033-6 Sakata, 1990, Extension of the Berlekamp–Massey algorithm to N dimensions, Inf. Comput., 84, 207, 10.1016/0890-5401(90)90039-K Von zur Gathen, 2003 Wang, 2001 Wiedemann, 1986, Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory, 32, 54, 10.1109/TIT.1986.1057137