Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves

Details Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves

2011-05-31

arxiv.org/abs/1105.6331v1

Mathematics

Number Theory

23 pages, 3 figures

Scientific paper

A low storage algorithm for constructing isogenies between ordinary elliptic curves was proposed by Galbraith, Hess and Smart (GHS). We give an improvement of this algorithm by modifying the pseudorandom walk so that lower-degree isogenies are used more frequently. This is motivated by the fact that high degree isogenies are slower to compute than low degree ones. We analyse the running time of the parallel collision search algorithm when the partitioning is uneven. We also give experimental results. We conclude that our algorithm is around 14 times faster than the GHS algorithm when constructing horizontal isogenies between random isogenous elliptic curves over a 160-bit prime field. The results apply to generic adding walks and the more general group action inverse problem; a speed-up is obtained whenever the cost of computing edges in the graph varies significantly.

Affiliated with

Also associated with

No associations

Rating

Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338935