Pierre-Jean Spaenlehauer
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
Research Subjects
Pierre-Jean Spaenlehauer has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
Jean-Charles Faugère
INRIA/Sorbonne Universités/Univ. Paris 6/CNRS, Equipe PolSys, Paris, France
9 shared publicationsMohab Safey El Din
Sorbonne Universités/UPMC/Univ. Paris 6, Paris, France
5 shared publicationsJules Svartz
Lycée Masséna/Min. Education Nationale, Nice, France
3 shared publications- Aude Le Gluher
Université de Lorraine CNRS Inria
2 shared publications - Pierrick Gaudry
Université de Lorraine
2 shared publications Simon Abelard
Université de Lorraine, CNRS, Inria, Nancy, France
2 shared publications
Latest Publications
- Open Access
Computing Isomorphisms between Products of Supersingular Elliptic Curves
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 AccessComputing Isomorphisms between Products of Supersingular Elliptic Curves
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.
- 1 March 2024
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 125
Computing a group action from the class field theory of imaginary hyperelliptic function fields
- 1 March 2024
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 125
Computing a group action from the class field theory of imaginary hyperelliptic function fields
- Open Access
Dimension Results for Extremal-Generic Polynomial Systems over Complete Toric Varieties
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 AccessDimension Results for Extremal-Generic Polynomial Systems over Complete Toric Varieties
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.
- 13 February 2024
- Published by Elsevier in Journal of Algebra
- Vol. 646, 156-182
Dimension results for extremal-generic polynomial systems over complete toric varieties
- 13 February 2024
- Published by Elsevier in Journal of Algebra
- Vol. 646, 156-182
Dimension results for extremal-generic polynomial systems over complete toric varieties
- Open Access
A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
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.Open AccessA Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
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. - 18 February 2020
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 89 (325) , 2399-2433
A fast randomized geometric algorithm for computing Riemann-Roch spaces
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.
- 18 February 2020
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 89 (325) , 2399-2433
A fast randomized geometric algorithm for computing Riemann-Roch spaces
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
- 28 January 2019
- Published by Mathematical Sciences Publishers in The Open Book Series
- Vol. 2 (1) , 1-19
Counting points on genus-3 hyperelliptic curves with explicit real multiplication
- 28 January 2019
- Published by Mathematical Sciences Publishers in The Open Book Series
- Vol. 2 (1) , 1-19
Open AccessCounting points on genus-3 hyperelliptic curves with explicit real multiplication
- Open Access
A Polyhedral Method for Sparse Systems with many Positive Solutions
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.
Open AccessA Polyhedral Method for Sparse Systems with many Positive Solutions
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.
- 6 July 2018
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 19 (3) , 591-621
Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
- 6 July 2018
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 19 (3) , 591-621
Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
- 1 January 2018
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Algebra and Geometry
- Vol. 2 (4) , 620-645
A Polyhedral Method for Sparse Systems with Many Positive Solutions
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.
- 1 January 2018
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Algebra and Geometry
- Vol. 2 (4) , 620-645
A Polyhedral Method for Sparse Systems with Many Positive Solutions
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.