Constructing elliptic curve isogenies in quantum subexponential time

Andrew M. Childs · David Jao · Vladimir Soukharev

Journal of Mathematical Cryptology 2014

Time bound

L_q[1/2, sqrt(3)/2]

Space bound

Subexponential quantum space; polynomial-quantum-space claim has an erratum

Source / version date

17 Dec 2010

Comparison variant

Quantum · GRH

Cost scale

L_q[1/2,c]

assumption

GRH

source-version

arXiv:1012.4019v3, 16 April 2018

L-notation

L_q[α,c]=exp((c+o(1))(ln q)^α(ln ln q)^{1−α})

Assumptions and source notes

The time bound assumes GRH for ordinary curves with a common endomorphism ring. The claimed polynomial-quantum-space variant has an acknowledged erratum; this entry makes no such space claim.

Source location

Introduction/main runtime statement; arXiv v3 erratum notice
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{cjs10,
  author = {Andrew M. Childs and David Jao and Vladimir Soukharev},
  title = {{Constructing elliptic curve isogenies in quantum subexponential time}},
  year = {2014},
  doi = {10.1515/jmc-2012-0016},
  url = {https://arxiv.org/abs/1012.4019},
  keywords = {ordinary isogenies, quantum hidden shift, GRH},
  cr_date = {2010-12-17},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Journal of Mathematical Cryptology 8(1):1–29},
  cr_author_ids = {andrew-m-childs; david-jao; vladimir-soukharev}
}