Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms

Martin Roetteler · Michael Naehrig · Krysta M. Svore · Kristin Lauter

Asiacrypt 2017

Time bound

At most 448 n³ log₂(n) + 4090 n³ logical Toffoli gates

Space bound

At most 9n + 2 ceil(log₂ n) + 10 logical qubits

Source / version date

21 Jun 2017

Comparison variant

Prime fields · quantum resource bounds

Cost scale

Expression only

Assumptions and source notes

Resource estimate for a specific quantum circuit over an n-bit prime field. Counts logical gates and qubits; excludes physical error correction. This is a proved circuit bound rather than a measured quantum attack.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

@misc{rnsl17,
  author = {Martin Roetteler and Michael Naehrig and Krysta M. Svore and Kristin Lauter},
  title = {{Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms}},
  journal = {ASIACRYPT 2017},
  year = {2017},
  doi = {10.1007/978-3-319-70697-9_9},
  url = {https://eprint.iacr.org/2017/598},
  keywords = {quantum, elliptic curves, prime fields, logical resources},
  cr_date = {2017-06-21},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {ASIACRYPT 2017},
  cr_author_ids = {martin-roetteler; michael-naehrig; krysta-m-svore; kristin-lauter}
}