A crucial ingredient for many cryptographic primitives such as key exchange protocols and advanced signature schemes is a commutative group action where the structure of the underlying group can be computed efficiently. SCALLOP provides such a group action, based on oriented supersingular elliptic curves. We present PEARL-SCALLOP (Parameter Extension Applicable in Real-Life SCALLOP), a variant of SCALLOP that changes several parameter and design choices, thereby improving on both efficiency and security and enabling feasible parameter generation for larger security levels. Within the SCALLOP framework, our parameters are essentially optimal; the orientation is provided by a 2^e-isogeny, where 2^e is roughly equal to the discriminant of the acting class group. As an important subroutine we present a practical algorithm for generating oriented supersingular elliptic curves. To demonstrate our improvements, we provide a proof-of-concept implementation which instantiates PEARL-SCALLOP at all relevant security levels. Our timings are more than an order of magnitude faster than any previous implementation.
We develop a new approach to the isospectrality of the orbifolds constructed by Vignéras. We give fine sufficient criteria for i-isospectrality in given degree i and for representation equivalence. These allow us to produce very small exotic examples of isospectral orbifolds: hyperbolic 3-orbifolds that are i-isospectral for all i but not representation equivalent, hyperbolic 3-orbifolds that are 0-isospectral but not 1-isospectral, and others. Using the same method, we also give sufficient criteria for rationality of regulator quotients Reg_i(Y_1)^2/Reg_i(Y_2)^2 for Vignéras orbifolds Y_1, Y_2, sometimes even when they are not isospectral. Moreover, we establish a link between the primes that enter in these regulator quotients and at which torsion homology of Y_1 and Y_2 can differ, and Galois representations.
In this note, we present a simplified (but slower) version Clapoti of Clapotis, whose full description will appear later. Let E/F_q be an elliptic curve with an effective primitive orientation by a quadratic imaginary order R in End(E). Let A be an invertible ideal in R. Clapoti is a randomised polynomial time algorithm in O(log Delta_R + log q)^O(1) operations to compute the class group action E→E_A = E/E[A]. This note will be superseded by the article in preparation.
The supersingular Endomorphism Ring problem is the following: given a supersingular elliptic curve, compute all of its endomorphisms. The presumed hardness of this problem is foundational for isogeny-based cryptography. The One Endomorphism problem only asks to find a single non-scalar endomorphism. We prove that these two problems are equivalent, under probabilistic polynomial time reductions. We prove a number of consequences. First, assuming the hardness of the Endomorphism Ring problem, the Charles-Goren-Lauter hash function is collision resistant, and the SQIsign identification protocol is sound. Second, the Endomorphism Ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves, a result previously known only for isogenies of smooth degree. Third, there exists an unconditional probabilistic algorithm to solve the Endomorphism Ring problem in time O~(sqrt(p)), a result that previously required to assume the generalized Riemann hypothesis. To prove our main result, we introduce a flexible framework for the study of isogeny graphs with additional information. We prove a general and easy-to-use rapid mixing theorem. The proof of this result goes via an augmented Deuring correspondence and the Jacquet-Langlands correspondence.
We describe algorithms to represent and compute groups of Hecke characters. We make use of an idèlic point of view and obtain the whole family of such characters, including transcendental ones. We also show how to isolate the algebraic characters, which are of particular interest in number theory. This work has been implemented in Pari/GP, and we illustrate our work with a variety of examples using our implementation.
For a finite group G, we introduce a generalization of norm relations in the group algebra Q[G]. We give necessary and sufficient criteria for the existence of such relations and apply them to obtain relations between the arithmetic invariants of the subfields of an algebraic number field with Galois group G. On the algorithm side this leads to subfield based algorithms for computing rings of integers, S-unit groups and class groups. For the S-unit group computation this yields a polynomial-time reduction to the corresponding problem in subfields. We compute class groups of large number fields under GRH, and new unconditional values of class numbers of cyclotomic fields. The GP script is available here.
Let k be a field of large enough characteristic. We present an algorithm solving the following problem: given two genus 2 curves over k with isogenous Jacobians, compute an isogeny between them explicitly. This isogeny can be either an l-isogeny or, in the real multiplication case, an isogeny with cyclic kernel. The algorithm uses modular equations for these isogeny types.
Lenstra and Guruswami described number field analogues of the algebraic geometry codes of Goppa. Recently, Maire and Oggier generalised these constructions to other arithmetic groups: unit groups in number fields and orders in division algebras; they suggested to use unit groups in quaternion algebras but could not completely analyse the resulting codes. We prove that the noncommutative unit group construction yields asymptotically good families of codes for the sum-rank metric from division algebras of any degree, and we estimate the size of the alphabet in terms of the degree.
If M is a manifold with an action of a group G, then the homology group H_1(M,Q) is naturally a Q[G]-module, where Q[G] denotes the rational group ring. We prove that for every finite group G, and for every Q[G]-module V, there exists a closed hyperbolic 3-manifold M with a free G-action such that the Q[G]-module H_1(M,Q) is isomorphic to V. We give an application to spectral geometry: for every finite set P of prime numbers, there exist hyperbolic 3-manifolds N and N' that are strongly isospectral such that for all p in P, the p-power torsion subgroups of H_1(N,Z) and of H_1(N',Z) have different orders. We also show that, in a certain precise sense, the rational homology of oriented Riemannian 3-manifolds with a G-action "knows" nothing about the fixed point structure under G, in contrast to the 2-dimensional case. The main geometric techniques are Dehn surgery and, for the spectral application, the Cheeger-Mueller formula, but we also make use of tools from different branches of algebra, most notably of regulator constants, a representation theoretic tool that was originally developed in the context of elliptic curves.
Given a finite group G, a G-covering of closed Riemannian manifolds, and a so-called G-relation, a construction of Sunada produces a pair of manifolds M_1 and M_2 that are strongly isospectral. Such manifolds have the same dimension and the same volume, and their rational homology groups are isomorphic. We investigate the relationship between their integral homology. The Cheeger-Mueller Theorem implies that a certain product of orders of torsion homology and of regulators for M_1 agrees with that for M_2. We exhibit a connection between the torsion in the integral homology of M_1 and M_2 on the one hand, and the G-module structure of integral homology of the covering manifold on the other, by interpreting the quotients Reg_i(M_1)/Reg_i(M_2) representation theoretically. Further, we prove that the p-primary torsion in the homology of M_1 is isomorphic to that of M_2 for all primes p not dividing #G. For p ≤ 71, we give examples of pairs of strongly isospectral arithmetic hyperbolic 3-manifolds for which the p-torsion homology differs.
Ethan and Alexander establish general dimension formulae for the second page of the equivariant spectral sequence of the action of the SL_2 groups over imaginary quadratic integers on their associated symmetric space. On the way, they extend the torsion subcomplex reduction technique to cases where the kernel of the group action is nontrivial. Using the equivariant and Lyndon-Hochschild-Serre spectral sequences, they investigate the second page differentials and show how to obtain the mod 2 cohomology rings of these groups from this information. In the appendix, I provide corresponding numerical results using my Kleinian Groups software.
Deciding whether an ideal of a number field is principal and finding a generator is a fundamental problem with many applications in computational number theory. For indefinite quaternion algebras, the decision problem reduces to that in the underlying number field. Finding a generator is hard, and we present a heuristically subexponential algorithm.
Arithmetic Kleinian groups are arithmetic lattices in PSL_2(C). We present an algorithm which, given such a group Γ, returns a fundamental domain and a finite presentation for Γ with a computable isomorphism. It is an improvement of the algorithm of my master's thesis. The Magma package is available here.
In this paper, Fabrice introduces a generalisation of norm relations in the group algebra Q[G], where G is a finite group. He gives some properties of these relations, and uses them to obtain relations between the S-unit groups of different subfields of the same Galois extension of Q, of Galois group G. Then he deduces an algorithm to compute the class groups of some number fields by reducing the problem to fields of lower degree. He computes the class groups of some large number fields.
Let F be a univariate polynomial or rational fraction of degree d defined over a number field. In this paper, Jean gives bounds from above on the absolute logarithmic Weil height of F in terms of the heights of its values at small integers: he reviews well-known bounds obtained from interpolation algorithms given values at d+1 (resp. 2d+1) points, and obtains tighter results when considering a larger number of evaluation points.
In this paper, Jean designs algorithms to efficiently evaluate genus 2 modular polynomials of Siegel and Hilbert type over number fields, using complex approximations. Under heuristics related to the computation of theta functions in quasi-linear time, the output is provably correct. His algorithms also apply to finite fields via lifting.
Existing algorithms to compute genus 2 theta constants in quasi-linear time use Borchardt sequences, an analogue of the arithmetic-geometric mean for four complex numbers. In this paper, Jean shows that these Borchardt sequences are given by good choices of square roots only, as in the genus 1 case. This removes the sign indeterminacies in the algorithm without relying on numerical integration.
In this paper, Jean defines modular equations in the setting of PEL Shimura varieties as equations describing Hecke correspondences, and proves degree and height bounds for them. This extends known results about classical modular polynomials. In particular, he obtains tight degree bounds for modular equations of Siegel and Hilbert type for abelian surfaces.
Méthodes explicites pour les groupes arithmétiques. [ HAL | thesis ]
This thesis was supervised by Karim Belabas and Andreas Enge. Here is the abstract of the thesis.
Computing fundamental domains for arithmetic Kleinian groups. [ HAL | thesis ]
This thesis was supervised by John Voight.
L'équation de Pell-Fermat non commutative. [ text (french) ]
Higher-dimensional modular equations, applications to isogeny computations and point counting, by Jean Kieffer. [ HAL ]
This thesis was co-supervised with Damien Robert.
We define a scheme for labelling and ordering integral ideals of number fields, including prime ideals as a special case. The order we define depends only on the choice of a monic irreducible integral defining polynomial for each field K, and we start by defining for each field its unique reduced defining polynomial, after Belabas. We define a total order on the set of prime ideals of K and then extend this to a total order on the set of all nonzero integral ideals of K. This order allows us to give a unique label of the form N.i, where N is its norm and i is the index of the ideal in the ordered list of all ideals of norm N. Our ideal labelling scheme has several nice properties: for a given norm, prime ideals always appear first, and given the factorisation of the norm, the bijection between ideals of norm N and labels is computable in polynomial time. Our motivation for this is to have a well-defined and concise way to sort and label ideals for use in databases such as the LMFDB. We have implemented algorithms which realise this scheme, in Sage, Magma and Pari. The code is available on Github.
Hardness of isogeny problems and equidistribution, at MPIM (Bonn, Germany) on 2024-12-05. [ notes ]
Equidistribution of curves with extra structure, at the CANARI seminar (Bordeaux, France) on 2024-10-01. [ notes ]
Isospectrality, regulators and torsion of Vignéras manifolds, at MFO (Oberwolfach, Germany) on 2024-09-02. [ slides ]
Computing class groups using norm relations, at CIRM (Luminy, France) on 2023-03-03. [ slides ]
Computing groups of Hecke characters, at ANTS XV (Bristol, United Kingdom) on 2022-08-08. [ slides | video ]
Algorithms for the cohomology of compact arithmetic manifolds, at the Cogent seminar (online) on 2022-05-30. [ slides ]
Torsion homology and regulators of Vignéras isospectral manifolds, at the Arithmetic Groups and 3-Manifolds conference (Bonn, Germany) on 2022-05-17. [ slides ]
Torsion dans l'homologie des variétés isospectrales de Vignéras et opérateurs de Hecke, at the Besançon (France) number theory seminar on 2022-04-12. [ notes (french) ]
Norm relations and class group computations, at the LFANT seminar (Bordeaux, France) on 2021-11-23. [ notes ]
Algorithms for the cohomology of compact arithmetic manifolds and Hecke operators, at MIT (Boston, US) on 2018-08-20 for the conference Arithmetic Geometry, Number Theory, and Computation. [ notes ]
Torsion homology of arithmetic Kleinian groups, in Amherst College (MA, US) on 2015-11-17, for the Five College Number Theory Seminar. [ slides ]
Isospectrality, regulators and special value formulas, in Brown University, Providence (RI, US) on 2015-11-16, for the ICERM peer-to-peer seminar. [ slides ]
An algorithm for the principal ideal problem in indefinite quaternion algebras in GyeongJu (Korea) on 2014-08-11, Algorithmic Number Theory Symposium XI. [ slides ]
Computing Kleinian modular forms, in the University of Warwick (Coventry, UK) on 2014-06-4, LMFDB Workshop. [ slides ]