Ordinary isogeny search
Construct an isogeny between ordinary curves with the same endomorphism ring.
Quantum · GRH
Horizontally isogenous ordinary elliptic curves over F_q
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Constructing elliptic curve isogenies in quantum subexponential timeJournal of Mathematical Cryptology 2014SourceBibTeX / details | 17 Dec 2010 | Lq[1/2, sqrt(3)/2] | Subexponential quantum space; polynomial-quantum-space claim has an erratum | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Horizontally isogenous ordinary elliptic curves over F_q
- Computation
- Quantum
- Rigor
- Conditional on GRH
- Instances
- Same endomorphism ring
- Cost scale
- L_q[1/2,c]
- Parameter
- q
- Description
- Horizontally isogenous ordinary elliptic curves over F_q
- Comparison rules
- L_q[α,c]=exp((c+o(1))(ln q)^α(ln ln q)^{1−α}). Compare the leading constant at α=1/2 only. Account for the quantum evaluation of the hiding functions. CJS has an acknowledged erratum to its claimed polynomial-quantum-space variant.
- Tags
- ordinary curves, quantum, GRH