Computing isogenies between supersingular elliptic

Authors: Christina Delfs Steven D Galbraith

Publish Date: 2014/09/21

Volume: 78, Issue: 2, Pages: 425-440

PDF Link

Abstract

Let p3 be a prime and let E E be supersingular elliptic curves over mathbb F p We want to construct an isogeny phi Erightarrow E The currently fastest algorithm for finding isogenies between supersingular elliptic curves solves this problem in the full supersingular isogeny graph over mathbb F p2 It takes an expected tildemathcal Op1/2 bit operations and also tildemathcal Op1/2 space by performing a “meetinthemiddle” breadthfirst search in the isogeny graph In this paper we consider the structure of the isogeny graph of supersingular elliptic curves over mathbb F p We give an algorithm to construct isogenies between supersingular curves over mathbb F p that works in tildemathcal Op1/4 bit operations We then discuss how this algorithm can be used to obtain an improved algorithm for the general supersingular isogeny problemWe thank David Kohel and Drew Sutherland for helpful conversations and Marco Streng for the idea of the proof of Proposition 26 Working on this paper started during a visit of the first author at the University of Auckland which was partially funded by a DAAD scholarship for PhD studentsWe present a few small examples of the irregular structure of the full supersingular isogeny graph Xbarmathbb F p ell After that we display for the same examples the graphs Xmathbb F p ell which have a much more regular structure For the examples we use the primes p = 83 101 and 103 one for each of the different cases that occur To demonstrate the two occurring structures we build the graphs for isogeny degrees ell =2 and the smallest prime ell 2 in each case for that isogenies existNote that for jE = 0 resp jE equiv 1728 pmod p there are three resp two nonequivalent isogenies mapping from E to another curve E but their dual isogenies are all equivalent This is due to the fact that mathrmAut E =6 resp mathrmAut E = 4 in these cases If phi Erightarrow E is an isogeny and rho in mathrmAut E then phi circ rho may not be equivalent ie have the same kernel as psi whereas the dual of phi circ rho is hatrho circ hatphi so this is equivalent to the dual of phi We denote these multiple isogenies in the graph using a single arrow together with an integer to indicate the multiplicityIt is notable that in this graph there are fewer connecting isogenies than in the full graph before For example in the first graph we have two isogenies going from the node 64 to the node 3 and two ones back which are all missing in the new graph This is due to the fact that those isogenies are not defined over mathbb F p so they are not computed as edges in Xmathbb F p 2 Likewise the two loops from 59 to itself are isogenies over mathbb F p2 that are dual to each other whereas the loop at 21 is a mathbb F prational isogeny that is its own dual

Keywords: