Extending Regev's factoring algorithm to compute discrete logarithms

Martin Ekerå · Joel Gärtner

PQCrypto 2024

Time bound

Regev-type polynomial-time quantum circuits and polynomial classical post-processing

Space bound

Not extracted from the source

Source / version date

9 Nov 2023

Comparison variant

Prime fields · quantum

Cost scale

Expression only

Assumptions and source notes

Extension of Regev’s method to prime-field discrete logarithms. Circuit size per run, repetitions, arithmetic implementation and post-processing are separate resources. The original construction uses number-theoretic heuristic assumptions; later unconditional variants are analysed by Pilatte.

Source location

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

Primary source ↗

@misc{eg23,
  author = {Martin Ekerå and Joel Gärtner},
  title = {{Extending Regev's factoring algorithm to compute discrete logarithms}},
  journal = {PQCrypto 2024, LNCS 14772, 211–242},
  year = {2024},
  doi = {10.1007/978-3-031-62746-0_10},
  url = {https://arxiv.org/abs/2311.05545},
  keywords = {quantum, discrete logarithms, prime fields},
  cr_date = {2023-11-09},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {PQCrypto 2024, LNCS 14772, 211–242},
  cr_author_ids = {martin-ekera; joel-gartner}
}