Grö bner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. We consider sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Grö bner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Grö bner basis in the standard algebra and solve sparse polynomials systems over the torus (\mathbbC ^*)^n. The complexity of the algorithm depends on the Newton polytopes.

At STOC 2012, Aaronson and Christiano proposed a noisy and a noiseless version of the first public‐key quantum money scheme endowed with a security proof. This paper addresses the so‐called noisy hidden subspaces problem , on which the noisy version of their scheme is based. The first contribution of this work is a non‐quantum cryptanalysis of the above‐mentioned noisy quantum money scheme extended to prime fields , with , that runs in randomised polynomial time. This finding is supported with experimental results showing that, in practice, the algorithm presented is efficient and succeeds with overwhelming probability. The second contribution is a non‐quantum randomised polynomial‐time cryptanalysis of the noisy quantum money scheme over succeeding with a certain probability for values of the noise lying within a certain range. This result disproves a conjecture made by Aaronson and Christiano about the non‐existence of an algorithm that solves the noisy hidden subspaces problem over and succeeds with such probability.

A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix whose elements are the coefficients of the input polynomials up-to sign. This problem is well understood for unmixed multihomogeneous systems, that is for systems consisting of multihomogeneous polynomials with the same support. However, little is known for mixed systems, that is for systems consisting of polynomials with different supports. We consider the computation of the multihomogeneous resultant of bilinear systems involving two different supports. We present a constructive approach that expresses the resultant as the exact determinant of a Koszul resultant matrix, that is a matrix constructed from maps in the Koszul complex. % We exploit the resultant matrix to propose an algorithm to solve such systems. In the process we extend the classical eigenvalues and eigenvectors criterion to a more general setting. Our extension of the eigenvalues criterion applies to a general class of matrices, including the Sylvester-type and the Koszul-type ones.

One of the biggest open problems in computational algebra is the design of efficient algorithms for Gröbner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faugère, Spaenlehauer, and Svartz [ISSAC'14]. We present two algorithms for sparse Gröbner bases computations for mixed systems. The first one computes with mixed sparse systems and exploits the supports of the polynomials. Under regularity assumptions, it performs no reductions to zero. For mixed, square, and 0-dimensional multihomogeneous polynomial systems, we present a dedicated, and potentially more efficient, algorithm that exploits different algebraic properties that performs no reduction to zero. We give an explicit bound for the maximal degree appearing in the computations.

Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp--Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence. Several algorithms solve this problem. The so-called Berlekamp--Massey--Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process. We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp--Massey--Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations. A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial. Finally, we give a partial solution to the transformation of this algorithm into an adaptive one.

Symmetric Tensor Decomposition is a major problem that arises in areas such as signal processing, statistics, data analysis and computational neuroscience. It is equivalent to write a homogeneous polynomial in $n$ variables of degree $D$ as a sum of $D$-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We consider the decomposition of binary forms, that corresponds to the decomposition of symmetric tensors of dimension $2$ and order $D$. This problem has its roots in Invariant Theory, where the decompositions are known as canonical forms. As part of that theory, different algorithms were proposed for the binary forms. In recent years, those algorithms were extended for the general symmetric tensor decomposition problem. We present a new randomized algorithm that enhances the previous approaches with results from structured linear algebra and techniques from linear recurrent sequences. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have quadratic complexity bounds. We compute a symbolic minimal decomposition in O(M(D) log(D)) arithmetic operations, where M(D) is the complexity of multiplying two polynomials of degree D. We approximate the terms of the decomposition with an error of 2-ε, in O(D log2(D) (log2(D) + log(ε))) arithmetic operations. To bound the size of the representation of the coefficients involved in the decomposition, we bound the algebraic degree of the problem by min(rank, D-rank+1). When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, OB(D l + D4 + D3 τ) bit operations, where τ is the maximum bitsize of the coefficients and 2-l is the relative error of the terms in the decomposition.

Given several n-dimensional sequences, we first present an algorithm for computing the Grobner basis of their module of linear recurrence relations.

Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures.

This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea [8] of Faugère and Lachartre (GB reduction). We further exploit underlying structures in matrices generated during Gröbner basis computations in algorithms like F4 or F5 taking advantage of block patterns by using a special data structure called multilines. Moreover, we discuss a new order of operations for the reduction process. In various different experimental results we show that GBLA performs better than GB reduction or Magma in sequential computations (up to 40% faster) and scales much better than GB reduction for a higher number of cores: On 32 cores we reach a scaling of up to 26. GBLA is up to 7 times faster than GB reduction. Further, we compare different parallel schedulers GBLA can be used with. We also developed a new advanced storage format that exploits the fact that our matrices are coming from Gröbner basis computations, shrinking storage by a factor of up to 4. A huge database of our matrices is freely avail- able with GBLA.

Bezout's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2n solutions over algebraically closed fields. When only a small subset M of monomials appear in the equations (fewnomial systems), the number of solutions may decrease dramatically. We focus in this work on subsets of quadratic monomials M such that generic systems with support M do not admit any solution at all. For these systems, Hilbert's Nullstellensatz ensures the existence of algebraic certificates of inconsistency. However, up to our knowledge all known bounds on the sizes of such certificates ---including those which take into account the Newton polytopes of the polynomials--- are exponential in n. Our main results show that if the inequality 2|M|-2n ≤ √{1+8ν}-1 holds for a quadratic fewnomial system -- where ν is the matching number of a graph associated with M, and |M| is the cardinality of M -- then there exists generically a certificate of inconsistency of linear size (measured as the number of coefficients in the ground field K). Moreover this certificate can be computed within a polynomial number of arithmetic operations. Next, we evaluate how often this inequality holds, and we give evidence that the probability that the inequality is satisfied depends strongly on the number of squares. More precisely, we show that if M is picked uniformly at random among the subsets of n+k+1 quadratic monomials containing at least Ω(n1/2+ε) squares, then the probability that the inequality holds tends to 1 as n grows. Interestingly, this phenomenon is related with the matching number of random graphs in the Erdos-Renyi model. Finally, we provide experimental results showing that certificates in inconsistency can be computed for systems with more than 10000 variables and equations.

The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non-trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has no symmetry anymore. This result is obtained thanks to an operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold. The reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (respectively, Goppa) code provides the dual of an alternant (respectively, Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of Berger and Dür). This enables not only to present a unified view but also to generalize the construction of QC, QD, and even quasi-monoidic Goppa codes. Finally, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.

Sakata generalized the Berlekamp--Massey algorithm to n dimensions in~1988. The Berlekamp--Massey--Sakata (BMS) algorithm can be used for finding a Grbner basis of a 0-dimensional ideal of relations verified by a table. We investigate this problem usingö linear algebra techniques, with motivations such as accelerating change of basis algorithms (FGLM) or improving their complexity.

The main practical limitation of the McEliece cryptosystem is probably the size of its public-key. To overcome this issue, a famous trend is to decrease the public-key size by focusing on subclasses of alternant/Goppa codes which admit a compact parity-check or generator matrix. For instance, a key-size reduction is obtained by taking alternant/Goppa codes which have quasi-cyclic (QC) or quasi-dyadic (QD) generator matrices. We show that the use of such compact alternant/Goppa codes introduced a fundamental weakness. It is possible to reduce the key-recovery on the original public-code C to the key-recovery on a (much) smaller code C'. To this end, we use a new operation on codes which exploits the automorphism group.

The usual algorithm to solve polynomial systems using Gröbner bases consists of two steps: first computing the DRL Gröbner basis using the F5 algorithm then computing the LEX Gröbner basis using a change of ordering algorithm. When the Bézout bound is reached, the bottleneck of the total solving process is the change of ordering step. For 20 years, thanks to the FGLM algorithm the complexity of change of ordering is known to be cubic in the number of solutions of the system to solve.

Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amounts to computing in a semigroup algebra, i.e. an algebra generated by a subset of Laurent monomials. In order to solve symbolically sparse systems, we introduce sparse Gröbner bases, an analog of classical Gröbner bases for semigroup algebras, and we propose sparse variants of the F5 and FGLM algorithms to compute them. Our prototype "proof-of-concept" implementation shows large speedups (more than 100 for some examples) compared to optimized (classical) Gröbner bases software. Moreover, in the case where the generating subset of monomials corresponds to the points with integer coordinates in a normal lattice polytope P ⊂ Rn and under regularity assumptions, we prove complexity bounds which depend on the combinatorial properties of P. These bounds yield new estimates on the complexity of solving 0-dim systems where all polynomials share the same Newton polytope (unmixed case). For instance, we generalize the bound min(n1, n2) + 1 on the maximal degree in a Gröbner basis of a 0-dim. bilinear system with blocks of variables of sizes (n1, n2) to the multilinear case: Σ ni - max(ni) + 1. We also propose a variant of Fröberg's conjecture which allows us to estimate the complexity of solving overdetermined sparse systems. Finally, our complexity results apply in the dense (usual) case and, as a surprising by-product, we prove that restrictive assumptions in usual complexity estimates of classical inhomogeneous Gröbner bases algorithms can be removed.

Let K be a field and (f1, ..., fn)\subset K[X1, ..., Xn] be a sequence of quasi-homogeneous polynomials of respective weighted degrees (d1, ..., dn) w.r.t a system of weights (w1,...,wn). Such systems are likely to arise from a lot of applications, including physics or cryptography.

We propose efficient algorithms to compute the Gröbner basis of an ideal I subset k[x1,...,xn] globally invariant under the action of a commutative matrix group G, in the non-modular case (where char(k) doesn't divide |G|). The idea is to simultaneously diagonalize the matrices in G, and apply a linear change of variables on I corresponding to the base-change matrix of this diagonalization. We can now suppose that the matrices acting on I are diagonal. This action induces a grading on the ring R=k[x1,...,xn], compatible with the degree, indexed by a group related to G, that we call G-degree. The next step is the observation that this grading is maintained during a Gröbner basis computation or even a change of ordering, which allows us to split the Macaulay matrices into |G| submatrices of roughly the same size. In the same way, we are able to split the canonical basis of R/I (the staircase) if I is a zero-dimensional ideal. Therefore, we derive abelian versions of the classical algorithms F4, F5 or FGLM. Moreover, this new variant of F4/ F5 allows complete parallelization of the linear algebra steps, which has been successfully implemented. On instances coming from applications (NTRU crypto-system or the Cyclic-n problem), a speed-up of more than 400 can be obtained. For example, a Gröbner basis of the Cyclic-11 problem can be solved in less than 8 hours with this variant of F4. Moreover, using this method, we can identify new classes of polynomial systems that can be solved in polynomial time.

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for “generic” random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.

The Polynomial System Solving (PoSSo) problem is a fundamental NP-Hard problem in computer algebra. Among others, PoSSo have applications in area such as coding theory and cryptology. Typically, the security of multivariate public-key schemes (MPKC) such as the UOV cryptosystem of Kipnis, Shamir and Patarin is directly related to the hardness of PoSSo over finite fields. The goal of this paper is to further understand the influence of finite fields on the hardness of PoSSo. To this end, we consider the so-called hybrid approach. This is a polynomial system solving method dedicated to finite fields proposed by Bettale, Faugère and Perret (Journal of Mathematical Cryptography, 2009). The idea is to combine exhaustive search with Gröbner bases. The efficiency of the hybrid approach is related to the choice of a trade-off between the two methods. We propose here an improved complexity analysis dedicated to quadratic systems. Whilst the principle of the hybrid approach is simple, its careful analysis leads to rather surprising and somehow unexpected results. We prove that the optimal trade-off (i.e. number of variables to be fixed) allowing to minimize the complexity is achieved by fixing a number of variables proportional to the number of variables of the system considered, denoted n. Under some natural algebraic assumption, we show that the asymptotic complexity of the hybrid approach is 2(3.31-3.62 log2(q)-1)n, where q is the size of the field (under the condition in particular that log(q) ≪ n). This is to date, the best complexity for solving PoSSo over finite fields (when q > 2). We have been able to quantify the gain provided by the hybrid approach compared to a direct Gröbner basis method. For quadratic systems, we show (assuming a natural algebraic assumption) that this gain is exponential in the number of variables. Asymptotically, the gain is 21.49n when both n and q grow to infinity and log(q) ≪ n.

We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...).

We propose an efficient algorithm to solve polynomial systems of which equations are globally invariant under an action of the symmetric group GN acting on the variable xi with σ(xi) = xσ(i) and the number of variables is a multiple of N. For instance, we can assume that swapping two variables (or two pairs of variables) in one equation gives rise to another equation of the system (perhaps changing the sign). The idea is to apply many times divided difference operators to the original system in order to obtain a new system of equations involving only the symmetric functions of a subset of the variables.

Let I in K[x1,...,xn] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Gröbner bases of I is crucial in polynomial system solving. Through the algorithm FGLM, this task is classically tackled by linear algebra operations in K[x1,...,n]/I. With recent progress on Gröbner bases computations, this step turns out to be the bottleneck of the whole solving process.

The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for “generic” random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.

Computing loci of rank defects of linear matrices (also called the MinRank problem) is a fundamental NP-hard problem of linear algebra which has applications in Cryptology, in Error Correcting Codes and in Geometry. Given a square linear matrix (i.e. a matrix whose entries are k-variate linear forms) of size n and an integer r, the problem is to find points such that the evaluation of the matrix has rank less than r+1. The aim of the paper is to obtain the most efficient algorithm to solve this problem. To this end, we give the theoretical and practical complexity of computing Gröbner bases of two algebraic formulations of the MinRank problem. Both modelings lead to structured algebraic systems. The first modeling, proposed by Kipnis and Shamir generates bihomogeneous equations of bi-degree (1,1). The second one is classically obtained by the vanishing of the (r+1)-minors of the given

International audience

The associated talk surveys how computer algebra techniques have been used to break several cryptosystems.

In this paper, we present an improved method for decomposing multivariate polynomials. This problem, also known as the Functional Decomposition Problem (FDP) [17, 9, 27], is classical in computer algebra (e.g. [17, 18, 19, 23, 24, 7, 25]). Here, we propose to use high order partial derivatives to improve the algorithm described in [14]. Our new approach is more simple, and in some sense more natural. From a practical point of view, this new approach will lead to more efficient algorithms. The complexity of our algorithms will depend of the degree of the input polynomials, and the ratio n/u between the number of variables/polynomials.

In this paper, we propose an efficient method to solve polynomial systems whose equations are left invariant by the action of a finite group G. The idea is to simultaneously compute a truncated SAGBI-Gröbner bases (a generalisation of Gröbner bases to ideals of subalgebras of polynomial ring) and a Gröbner basis in the invariant ring K[σ1,..., σn] where σi is the i-th elementary symmetric polynomial. To this end, we provide two algorithms: first, from the F5 algorithm we can derive an efficient and easy to implement algorithm for computing truncated SAGBI–Gröbner bases of the ideals in invariant rings. A first implementation of this algorithm in C enable us to estimate the practical efficiency: for instance, it takes only 92s to compute a SAGBI basis of Cyclic 9 modulo a small prime. The second algorithm is inspired by the FGLM algorithm: from a truncated SAGBI–Gröbner basis of a zero-dimensional ideal we can compute efficiently a Gröbner basis in some invariant rings K[h1,..., hn]. Finally, we will show how this two algorithms can be combined to find the complex roots of such invariant polynomial systems.

Classifying the Perspective-Three-Point problem (abbreviated by P3P in the sequel) consists in determining the number of possible positions of a camera with respect to the apparent position of three points. In the case where the three points form an isosceles triangle, we give a full classification of the P3P. This leads to consider a polynomial system of polynomial equations and inequalities with 4 parameters which is generically zero-dimensional. In the present situation, the parameters represent the apparent position of the three points so that solving the problem means determining all the possible numbers of real solutions with respect to the parameters' values and give a sample point for each of these possible numbers. One way for solving such systems consists first in computing a discriminant variety. Then, one has to compute at least one point in each connected component of its real complementary in the parameter's space. The last step consists in specializing the parameters appearing in the initial system by these sample points. Many computational tools may be used for implementing such a general method, starting with the well known Cylindrical Algebraic Decomposition (CAD in short), which provides more information than required. In a first stage, we propose a full algorithm based on the straightforward use of some sophisticated software such as FGb (Grobner bases computations) RS (real roots of zero-dimensional systems), DV (Discriminant varieties) and RAGlib (Critical point methods for semi-algebraic systems). We then improve the global algorithm by refining the required computable mathematical objects and related algorithms and finally provide the classification. Three full days of computation were necessary to get this classification which is obtained from more than 40000 points in the parameter's space.

We address the problem of the algebraic decoding of any cyclic code up to the true minimum distance. For this, we use the classical formulation of the problem, which is to find the error locator polynomial in terms of the syndromes of the received word. This is usually done with the Berlekamp-Massey algorithm in the case of BCH codes and related codes, but for the general case, there is no generic algorithm to decode cyclic codes. Even in the case of the quadratic residue codes, which are good codes with a very strong algebraic structure, there is no available general decoding algorithm. For this particular case of quadratic residue codes, several authors have worked out, by hand, formulas for the coefficients of the locator polynomial in terms of the syndromes, using the Newton identities. This work has to be done for each particular quadratic residue code, and is more and more difficult as the length is growing. Furthermore, it is error-prone. We propose to automate these computations, using elimination theory and Grobner bases. We prove that, by computing appropriate Grobner bases, one automatically recovers formulas for the coefficients of the locator polynomial, in terms of the syndromes.

We present an algorithm for the transformation of a Gröbner basis of an ideal with respect to any given ordering into a Gröbner basis with respect to any other ordering. This algorithm is based on a modified version of the LLL algorithm. The worst case theoretical complexity of this algorithm is not better than the complexity of the FGLM algorithm; but can also give the theoretical complexity with some parameters depending on the size of the output. When the output is small then algorithm is more efficient. We also present a first implementation of the algorithm in Maple. This algorithm is restricted to the case of two variables but works also in positive dimension.