Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
128
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Computing endomorphism rings of supersingular elliptic curves is an important problem in computational number theory, and it is also closely connected to the security of some of the recently proposed isogeny-based cryptosystems. In this paper we give a new algorithm for computing the endomorphism ring of a supersingular elliptic curve $E$ that runs, under certain heuristics, in time $O((log p)^2p^{1/2})$. The algorithm works by first finding two cycles of a certain form in the supersingular $ell$-isogeny graph $G(p,ell)$, generating an order $Lambda subseteq operatorname{End}(E)$. Then all maximal orders containing $Lambda$ are computed, extending work of Voight. The final step is to determine which of these maximal orders is the endomorphism ring. As part of the cycle finding algorithm, we give a lower bound on the set of all $j$-invariants $j$ that are adjacent to $j^p$ in $G(p,ell)$, answering a question in arXiv:1909.07779.
rate research
Read More
Let $E$ be an elliptic curve without CM that is defined over a number field $K$. For all but finitely many nonarchimedean places $v$ of $K$ there is the reduction $E(v)$ of $E$ at $v$ that is an elliptic curve over the residue field $k(v)$ at $v$. The set of $v$s with ordinary $E(v)$ has density 1 (Serre). For such $v$ the endomorphism ring $End(E(v))$ of $E(v)$ is an order in an imaginary quadratic field. We prove that for any pair of relatively prime positive integers $N$ and $M$ there are infinitely many nonarchimedean places $v$ of $K$ such that the discriminant $Delta(v)$ of $End(E(v))$ is divisible by $N$ and the ratio $Delta(v)/N$ is relatively prime to $NM$. We also discuss similar questions for reductions of abelian varieties. The subject of this paper was inspired by an exercise in Serres Abelian $ell$-adic representations and elliptic curves and questions of Mihran Papikian and Alina Cojocaru.
For a fixed $j$-invariant $j_0$ of an elliptic curve without complex multiplication we bound the number of $j$-invariants $j$ that are algebraic units and such that elliptic curves corresponding to $j$ and $j_0$ are isogenous. Our bounds are effective. We also modify the problem slightly by fixing a singular modulus $alpha$ and looking at all $j$ such that $j-alpha$ is an algebraic unit and such that elliptic curves corresponding to $j$ and $j_0$ are isogenous. The number of such $j$ can again be bounded effectively.
Let E be an elliptic curve without complex multiplication (CM) over a number field K, and let G_E(ell) be the image of the Galois representation induced by the action of the absolute Galois group of K on the ell-torsion subgroup of E. We present two probabilistic algorithms to simultaneously determine G_E(ell) up to local conjugacy for all primes ell by sampling images of Frobenius elements; one is of Las Vegas type and the other is a Monte Carlo algorithm. They determine G_E(ell) up to one of at most two isomorphic conjugacy classes of subgroups of GL_2(Z/ell Z) that have the same semisimplification, each of which occurs for an elliptic curve isogenous to E. Under the GRH, their running times are polynomial in the bit-size n of an integral Weierstrass equation for E, and for our Monte Carlo algorithm, quasi-linear in n. We have applied our algorithms to the non-CM elliptic curves in Cremonas tables and the Stein--Watkins database, some 140 million curves of conductor up to 10^10, thereby obtaining a conjecturally complete list of 63 exceptional Galois images G_E(ell) that arise for E/Q without CM. Under this conjecture we determine a complete list of 160 exceptional Galois images G_E(ell) the arise for non-CM elliptic curves over quadratic fields with rational j-invariants. We also give examples of exceptional Galois images that arise for non-CM elliptic curves over quadratic fields only when the j-invariant is irrational.
Fix a prime number $ell$. Graphs of isogenies of degree a power of $ell$ are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called $mathfrak l$-isogenies, resolving that they are (almost) volcanoes in any dimension. Specializing to the case of principally polarizable abelian surfaces, we then exploit this structure to describe graphs of a particular class of isogenies known as $(ell, ell)$-isogenies: those whose kernels are maximal isotropic subgroups of the $ell$-torsion for the Weil pairing. We use these two results to write an algorithm giving a path of computable isogenies from an arbitrary absolutely simple ordinary abelian surface towards one with maximal endomorphism ring, which has immediate consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.
We develop algorithms to turn quotients of rings of rings of integers into effective Euclidean rings by giving polynomial algorithms for all fundamental ring operations. In addition, we study normal forms for modules over such rings and their behavior under certain quotients. We illustrate the power of our ideas in a new modular normal form algorithm for modules over rings of integers, vastly outperforming classical algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
