Abstract We show how the Weil pairing can be used to evaluate the assigned characters of an imaginary quadratic order $${\mathcal {O}}$$ O in an unknown ideal class $$[{\mathfrak {a}}] \in {{\,\textrm{cl}\,}}({\mathcal {O}})$$ [ a ] ∈ cl ( O ) that connects two given $${\mathcal {O}}$$ O -oriented elliptic curves $$(E, \iota )$$ ( E , ι ) and $$(E', \iota ') = [{\mathfrak {a}}](E, \iota )$$ ( E ′ , ι ′ ) = [ a ] ( E , ι ) . When specialized to ordinary elliptic curves over finite fields, our method is conceptually simpler and often somewhat faster than a recent approach due to Castryck, Sotáková and Vercauteren, who rely on the Tate pairing instead. The main implication of our work is that it breaks the decisional Diffie–Hellman problem for practically all oriented elliptic curves that are acted upon by an even-order class group. It can also be used to better handle the worst cases in Wesolowski’s recent reduction from the vectorization problem for oriented elliptic curves to the endomorphism ring problem, leading to a method that always works in sub-exponential time.
more »
« less
Generalized class polynomials
Abstract The Hilbert class polynomial has as roots the j -invariants of elliptic curves whose endomorphism ring is a given imaginary quadratic order. It can be used to compute elliptic curves over finite fields with a prescribed number of points. Since its coefficients are typically rather large, there has been continued interest in finding alternative modular functions whose corresponding class polynomials are smaller. Best known are Weber’s functions, which reduce the size by a factor of 72 for a positive density subset of imaginary quadratic discriminants. On the other hand, Bröker and Stevenhagen showed that no modular function will ever do better than a factor of 100.83. We introduce a generalization of class polynomials, with reduction factors that are not limited by the Bröker–Stevenhagen bound. We provide examples matching Weber’s reduction factor. For an infinite family of discriminants, their reduction factors surpass those of all previously known modular functions by a factor at least 2.
more »
« less
- Award ID(s):
- 1946311
- NSF-PAR ID:
- 10420415
- Date Published:
- Journal Name:
- Research in Number Theory
- Volume:
- 8
- Issue:
- 4
- ISSN:
- 2522-0160
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
We investigate the phase diagram of the complex cubic unitary ensemble of random matrices with the potential [Formula: see text], where t is a complex parameter. As proven in our previous paper [Bleher et al., J. Stat. Phys. 166, 784–827 (2017)], the whole phase space of the model, [Formula: see text], is partitioned into two phase regions, [Formula: see text] and [Formula: see text], such that in [Formula: see text] the equilibrium measure is supported by one Jordan arc (cut) and in [Formula: see text] by two cuts. The regions [Formula: see text] and [Formula: see text] are separated by critical curves, which can be calculated in terms of critical trajectories of an auxiliary quadratic differential. In Bleher et al. [J. Stat. Phys. 166, 784–827 (2017)], the one-cut phase region was investigated in detail. In the present paper, we investigate the two-cut region. We prove that in the two-cut region, the endpoints of the cuts are analytic functions of the real and imaginary parts of the parameter t, but not of the parameter t itself (so that the Cauchy–Riemann equations are violated for the endpoints). We also obtain the semiclassical asymptotics of the orthogonal polynomials associated with the ensemble of random matrices and their recurrence coefficients. The proofs are based on the Riemann–Hilbert approach to semiclassical asymptotics of the orthogonal polynomials and the theory of S-curves and quadratic differentials.
-
more » « less
We describe how the quadratic Chabauty method may be applied to determine the set of rational points on modular curves of genus
$g>1$ $g$ $X_0^+(N)$ $N$ $X_{S_4}(13)$ $X_{\scriptstyle \mathrm { ns}} ^+ (17)$ -
more » « less
Abstract Here, we initiate a program to study relationships between finite groups and arithmetic–geometric invariants in a systematic way. To do this, we first introduce a notion of optimal module for a finite group in the setting of holomorphic mock Jacobi forms. Then, we classify optimal modules for the cyclic groups of prime order, in the special case of weight 2 and index 1, where class numbers of imaginary quadratic fields play an important role. Finally, we exhibit a connection between the classification we establish and the arithmetic geometry of imaginary quadratic twists of modular curves of prime level.
-
We propose a quantum algorithm for computing an isogeny between two elliptic curves E1,E2 defined over a finite field such that there is an imaginary quadratic order O satisfying O~End(Ei )for i=1,2. This concerns ordinary curves and supersingular curves defined over Fp (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time exp(O(√log(|Δ|))) and requires polynomial quantum memory and exp(O(√log(|Δ|))) quantumly accessible classical memory, where Δ is the discriminant of O. This asymptotic complexity outperforms all other available methods for computing isogenies.We also show that a variant of our method has asymptotic run time e exp(Õ(√log(|Δ|))) while requesting only polynomial memory (both quantum and classical).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s40993-022-00400-2
