PSPierre-Jean Spaenlehauer

Pierre-Jean Spaenlehauer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Pierre-Jean Spaenlehauer has a total of 25 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Computing Isomorphisms between Products of Supersingular Elliptic Curves

    by Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer

    The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop $\ell$-adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. Under GRH, it is proved to run in expected polynomial time.

  • Open Access

    Dimension Results for Extremal-Generic Polynomial Systems over Complete Toric Varieties

    by Matías Bender, Pierre-Jean Spaenlehauer

    We study polynomial systems with prescribed monomial supports in the Cox rings of toric varieties built from complete polyhedral fans. We present combinatorial formulas for the dimensions of their associated subvarieties under genericity assumptions on the coefficients of the polynomials. Using these formulas, we identify at which degrees generic systems in polytopal algebras form regular sequences. Our motivation comes from sparse elimination theory, where knowing the expected dimension of these subvarieties leads to specialized algorithms and to large speed-ups for solving sparse polynomial systems. As a special case, we classify the degrees at which regular sequences defined by weighted homogeneous polynomials can be found, answering an open question in the Gröbner bases literature. We also show that deciding whether a sparse system is generically a regular sequence in a polytopal algebra is hard from the point of view of theoretical computational complexity.


  • Open Access

    A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces

    by Aude Le Gluher, Pierre-Jean Spaenlehauer

    We propose a probabilistic variant of Brill-Noether's algorithm for computing a basis of the Riemann-Roch space $L(D)$ associated to a divisor $D$ on a projective nodal plane curve $\mathcal C$ over a sufficiently large perfect field $k$. Our main result shows that this algorithm requires at most $O(\max(\mathrm{deg}(\mathcal C)^{2\omega}, \mathrm{deg}(D_+)^\omega))$ arithmetic operations in $k$, where $\omega$ is a feasible exponent for matrix multiplication and $D_+$ is the smallest effective divisor such that $D_+\geq D$. This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by $O(\max(\mathrm{deg}(\mathcal C)^4, \mathrm{deg}(D_+)^2)/\lvert \mathcal E\rvert)$, where $\mathcal E$ is a finite subset of $k$ in which we pick elements uniformly at random. We provide a freely available C++/NTL implementation of the proposed algorithm and we present experimental data. In particular, our implementation enjoys a speedup larger than 6 on many examples (and larger than 200 on some instances over large finite fields) compared to the reference implementation in the Magma computer algebra system. As a by-product, our algorithm also yields a method for computing the group law on the Jacobian of a smooth plane curve of genus $g$ within $O(g^\omega)$ operations in $k$, which equals the best known complexity for this problem.

  • A fast randomized geometric algorithm for computing Riemann-Roch spaces

    by Aude Le Gluher, Pierre-Jean Spaenlehauer

    We propose a probabilistic variant of Brill-Noether’s algorithm for computing a basis of the Riemann-Roch space L ( D ) L(D) associated to a divisor D D on a projective nodal plane curve C \mathbb {C} over a sufficiently large perfect field k k . Our main result shows that this algorithm requires at most O ( max ( deg ⁡ ( C ) 2 ω , deg ⁡ ( D + ) ω ) ) O(\max (\deg (\mathbb {C})^{2\omega }, \deg (D_+)^\omega )) arithmetic operations in k k , where ω \omega is a feasible exponent for matrix multiplication and D + D_+ is the smallest effective divisor such that D + ≥ D D_+\geq D . This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by O ( max ( deg ⁡ ( C ) 4 , deg ⁡ ( D + ) 2 ) / | E | ) O(\max (\deg (\mathbb {C})^4, \deg (D_+)^2)/\lvert \mathcal E\rvert ) , where E \mathcal E is a finite subset of k k in which we pick elements uniformly at random. We provide a freely available C++/NTL implementation of the proposed algorithm and we present experimental data. In particular, our implementation enjoys a speedup larger than 6 on many examples (and larger than 200 on some instances over large finite fields) compared to the reference implementation in the Magma computer algebra system. As a by-product, our algorithm also yields a method for computing the group law on the Jacobian of a smooth plane curve of genus g g within O ( g ω ) O(g^\omega ) operations in k k , which equals the best known complexity for this problem.


  • Open Access

    Counting points on genus-3 hyperelliptic curves with explicit real multiplication

    by Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer


  • Open Access

    A Polyhedral Method for Sparse Systems with many Positive Solutions

    by Frédéric Bihan, Francisco Santos, Pierre-Jean Spaenlehauer

    We investigate a version of Viro's method for constructing polynomial systems with many positive solutions, based on regular triangulations of the Newton polytope of the system. The number of positive solutions obtained with our method is governed by the size of the largest positively decorable subcomplex of the triangulation. Here, positive decorability is a property that we introduce and which is dual to being a subcomplex of some regular triangulation. Using this duality, we produce large positively decorable subcomplexes of the boundary complexes of cyclic polytopes. As a byproduct we get new lower bounds, some of them being the best currently known, for the maximal number of positive solutions of polynomial systems with prescribed numbers of monomials and variables. We also study the asymptotics of these numbers and observe a log-concavity property.

  • A Polyhedral Method for Sparse Systems with Many Positive Solutions

    by Frédéric Bihan, Francisco Santos, Pierre-Jean Spaenlehauer

    We investigate a version of Viro's method for constructing polynomial systems with many positive solutions, based on regular triangulations of the Newton polytope of the system. The number of positive solutions obtained with our method is governed by the size of the largest positively decorable subcomplex of the triangulation. Here, positive decorability is a property that we introduce and which is dual to being a subcomplex of some regular triangulation. Using this duality, we produce large positively decorable subcomplexes of the boundary complexes of cyclic polytopes. As a byproduct, we get new lower bounds, some of them being the best currently known, for the maximal number of positive solutions of polynomial systems with prescribed numbers of monomials and variables. We also study the asymptotics of these numbers and observe a log-concavity property.