Source author record

Jérémy Berthomieu

Jérémy Berthomieu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Symbolic Computation math.AC Cryptography and Security

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Faster change of order algorithm for Gröbner bases under shape and stability assumptions

Solving zero-dimensional polynomial systems using Gröbner bases is usually done by, first, computing a Gröbner basis for the degree reverse lexicographic order, and next computing the lexicographic Gröbner basis with a change of order algorithm. Currently, the change of order now takes a significant part of the whole solving time for many generic instances. Like the fastest known change of order algorithms, this work focuses on the situation where the ideal defined by the system satisfies natural properties which can be recovered in generic coordinates. First, the ideal has a \emph{shape} lexicographic Gröbner basis. Second, the set of leading terms with respect to the degree reverse lexicographic order has a \emph{stability} property; in particular, the multiplication matrix can be read on the input Gröbner basis. The current fastest algorithms rely on the sparsity of this matrix. Actually, this sparsity is a consequence of an algebraic structure, which can be exploited to represent the matrix concisely as a univariate polynomial matrix. We show that the Hermite normal form of that matrix yields the sought lexicographic Gröbner basis, under assumptions which cover the shape position case. Under some mild assumption implying $n \le t$, the arithmetic complexity of our algorithm is $O\tilde{~}(t^{ω-1}D)$, where $n$ is the number of variables, $t$ is a sparsity indicator of the aforementioned matrix, $D$ is the degree of the zero-dimensional ideal under consideration, and $ω$ is the exponent of matrix multiplication. This improves upon both state-of-the-art complexity bounds $O\tilde{~}(tD^2)$ and $O\tilde{~}(D^ω)$, since $ω< 3$ and $t\le D$. Practical experiments, based on the libraries msolve and PML, confirm the high practical benefit.

preprint2022arXiv

Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems

We consider ideals involving the maximal minors of a polynomial matrix. For example, those arising in the computation of the critical values of a polynomial restricted to a variety for polynomial optimisation. Gröbner bases are a classical tool for solving polynomial systems. For practical computations, this consists of two stages. First, a Gröbner basis is computed with respect to a DRL (degree reverse lexicographic) ordering. Then, a change of ordering algorithm, such as \textsf{Sparse-FGLM}, designed by Faugère and Mou, is used to find a Gröbner basis of the same ideal but with respect to a lexicographic ordering. The complexity of this latter step, in terms of arithmetic operations, is $O(mD^2)$, where $D$ is the degree of the ideal and $m$ is the number of non-trivial columns of a certain $D \times D$ matrix. While asymptotic estimates are known for $m$ for generic polynomial systems, thus far, the complexity of \textsf{Sparse-FGLM} was unknown for determinantal systems. By assuming Fröberg's conjecture we expand the work of Moreno-Socías by detailing the structure of the DRL staircase in the determinantal setting. Then we study the asymptotics of the quantity $m$ by relating it to the coefficients of these Hilbert series. Consequently, we arrive at a new bound on the complexity of the \textsf{Sparse-FGLM} algorithm for generic determinantal systems and for generic critical point systems. We consider the ideal in the polynomial ring $\mathbb{K}[x_1, \dots, x_n]$, where $\mathbb{K}$ is some infinite field, generated by $p$ generic polynomials of degree $d$ and the maximal minors of a $p \times (n-1)$ polynomial matrix with generic entries of degree $d-1$. Then for the case $d=2$ and for $n \gg p$ we give an exact formula for $m$ in terms of $n$ and $p$. Moreover, for $d \geq 3$, we give an asymptotic formula, as $n \to \infty$, for $m$ in terms of $n,p$ and $d$.

preprint2015arXiv

Polynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case

Let $\mathbf{f}=(f\_1,\ldots,f\_m)$ and $\mathbf{g}=(g\_1,\ldots,g\_m)$ be two sets of $m\geq 1$ nonlinear polynomials over $\mathbb{K}[x\_1,\ldots,x\_n]$ ($\mathbb{K}$ being a field). We consider the computational problem of finding -- if any -- an invertible transformation on the variables mapping $\mathbf{f}$ to $\mathbf{g}$. The corresponding equivalence problem is known as {\tt Isomorphism of Polynomials with one Secret} ({\tt IP1S}) and is a fundamental problem in multivariate cryptography. The main result is a randomized polynomial-time algorithm for solving {\tt IP1S} for quadratic instances, a particular case of importance in cryptography and somewhat justifying {\it a posteriori} the fact that {\it Graph Isomorphism} reduces to only cubic instances of {\tt IP1S} (Agrawal and Saxena). To this end, we show that {\tt IP1S} for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory, which involves to test the orthogonal simultaneous conjugacy of symmetric matrices. We show that we can essentially {\it linearize} the problem by reducing quadratic-{\tt IP1S} to test the orthogonal simultaneous similarity of symmetric matrices; this latter problem was shown by Chistov, Ivanyos and Karpinski to be equivalent to finding an invertible matrix in the linear space $\mathbb{K}^{n \times n}$ of $n \times n$ matrices over $\mathbb{K}$ and to compute the square root in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing the square root in $\mathbb{K}^{n \times n}$ for various fields (including finite fields). We then consider \\#{\tt IP1S}, the counting version of {\tt IP1S} for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the more general {\it Isomorphism of Polynomials} ({\tt IP}) problem where we allow an invertible linear transformation on the variables \emph{and} on the set of polynomials. A randomized polynomial-time algorithm for solving {\tt IP} when $\mathbf{f}=(x\_1^d,\ldots,x\_n^d)$ is presented. From an algorithmic point of view, the problem boils down to factoring the determinant of a linear matrix (\emph{i.e.}\ a matrix whose components are linear polynomials). This extends to {\tt IP} a result of Kayal obtained for {\tt PolyProj}.