An official website of the United States government
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
On the decisional Diffie–Hellman problem for class group actions on oriented elliptic curves
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
- Award ID(s):
- 1946311
- PAR ID:
- 10420418
- 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
-
-
We show that for certain non-CM elliptic curves E / Q E_{/\mathbb {Q}} such that 3 3 is an Eisenstein prime of good reduction, a positive proportion of the quadratic twists E ψ E_{\psi } of E E have Mordell–Weil rank one and the 3 3 -adic height pairing on E ψ ( Q ) E_{\psi }(\mathbb {Q}) is non-degenerate. We also show similar but weaker results for other Eisenstein primes. The method of proof also yields examples of middle codimensional algebraic cycles over number fields of arbitrarily large dimension (generalized Heegner cycles) that have non-zero p p -adic height. It is not known – though expected – that the archimedian height of these higher-codimensional cycles is non-zero.more » « less
-
In this short note we construct an embedding of the planar algebra for $$\overline{\Rep(U_q(\mathfrak{sl}_3))}$$ at $$q = e^{2\pi i \frac{1}{24}}$$ into the graph planar algebra of di Francesco and Zuber's candidate graph $$\mathcal{E}_4^{12}$$. Via the graph planar algebra embedding theorem we thus construct a rank 11 module category over $$\overline{\Rep(U_q(\mathfrak{sl}_3))}$$ whose graph for action by the vector representation is $$\mathcal{E}_4^{12}$$. This fills a small gap in the literature on the construction of $$\overline{\Rep(U_q(\mathfrak{sl}_3))}$$ module categories. As a consequence of our construction, we obtain the principal graphs of subfactors constructed abstractly by Evans and Pugh.more » « less
-
A bstract In a companion paper [1] we showed that the symmetry group $$ \mathfrak{G} $$ G of non-expanding horizons (NEHs) is a 1-dimensional extension of the Bondi-Metzner-Sachs group $$ \mathfrak{B} $$ B at $$ \mathcal{I} $$ I + . For each infinitesimal generator of $$ \mathfrak{G} $$ G , we now define a charge and a flux on NEHs as well as perturbed NEHs. The procedure uses the covariant phase space framework in presence of internal null boundaries $$ \mathcal{N} $$ N along the lines of [2–6]. However, $$ \mathcal{N} $$ N is required to be an NEH or a perturbed NEH. Consequently, charges and fluxes associated with generators of $$ \mathfrak{G} $$ G are free of physically unsatisfactory features that can arise if $$ \mathcal{N} $$ N is allowed to be a general null boundary. In particular, all fluxes vanish if $$ \mathcal{N} $$ N is an NEH, just as one would hope; and fluxes associated with symmetries representing ‘time-translations’ are positive definite on perturbed NEHs. These results hold for zero as well as non-zero cosmological constant. In the asymptotically flat case, as noted in [1], $$ \mathcal{I} $$ I ± are NEHs in the conformally completed space-time but with an extra structure that reduces $$ \mathfrak{G} $$ G to $$ \mathfrak{B} $$ B . The flux expressions at $$ \mathcal{N} $$ N reflect this synergy between NEHs and $$ \mathcal{I} $$ I + . In a forthcoming paper, this close relation between NEHs and $$ \mathcal{I} $$ I + will be used to develop gravitational wave tomography, enabling one to deduce horizon dynamics directly from the waveforms at $$ \mathcal{I} $$ I + .more » « less
-
In this paper, we revisit the bilevel optimization problem, in which the upper-level objective function is generally nonconvex and the lower-level objective function is strongly convex. Although this type of problem has been studied extensively, it still remains an open question how to achieve an $$\mathcal{O}(\epsilon^{-1.5})$$ sample complexity in Hessian/Jacobian-free stochastic bilevel optimization without any second-order derivative computation. To fill this gap, we propose a novel Hessian/Jacobian-free bilevel optimizer named FdeHBO, which features a simple fully single-loop structure, a projection-aided finite-difference Hessian/Jacobian-vector approximation, and momentum-based updates. Theoretically, we show that FdeHBO requires $$\mathcal{O}(\epsilon^{-1.5})$$ iterations (each using $$\mathcal{O}(1)$$ samples and only first-order gradient information) to find an $$\epsilon$$-accurate stationary point. As far as we know, this is the first Hessian/Jacobian-free method with an $$\mathcal{O}(\epsilon^{-1.5})$$ sample complexity for nonconvex-strongly-convex stochastic bilevel optimization.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s40993-022-00399-6
