<p>My understanding is that if $k = O (q)$, the algorithm has complexity $n^{O (\log n)}$ over finite fields $F_{q^k}$ assuming that $k = O (q)$. More generally, the algorithm has complexity $L_{q^k} (\alpha, O (1))$ in finite fields $F_{q_k}$ with $q \sim  L_{q^k} (\alpha)$. It beats previous classical algorithms for $\alpha &lt; 1 / 3$.</p>

<p>Shor's algorithm is still much faster, but the question about exponential speedup depends really on the definition of "exponential". (Also NFS/FFS were subexponential-time.)</p>

CC BY-SA 3.0
2013-06-25T12:03:30.340Z
2013-06-25T12:27:37.937Z
2013-06-25T12:27:37.937Z
cryptocat
<p>Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$.  The latter is the much more common setting that people talk about, both for cryptography and for Shor's algorithm, and the new algorithm doesn't threaten the quantum speedup there.  On the other hand, yes, unless I'm mistaken it does make the speedup much smaller in the $Z_{p^k}$ case.</p>

CC BY-SA 3.0
2013-06-25T11:26:34.447Z
2013-06-25T11:26:34.447Z
Scott Aaronson
<p>A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.
<a href="http://arxiv.org/abs/1306.4244">http://arxiv.org/abs/1306.4244</a></p>

<p>If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for the discrete logarithm problem? Does this have any implication for quantum complexity theory?</p>

<cc.complexity-theory>
New algorithm for Discrete log and its implications for Quantum computing
Turbo
# New algorithm for Discrete log and its implications for Quantum computing

(Asked by: username_0 on 2013-06-24)

A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.
<http://arxiv.org/abs/1306.4244>

If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for the discrete logarithm problem? Does this have any implication for quantum complexity theory?

**Tags:** cc.complexity-theory

---

## 2 answers

### Answer by username_2 on 2013-06-25. Score: 19 | Accepted answer

Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z\_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z\_p$. The latter is the much more common setting that people talk about, both for cryptography and for Shor's algorithm, and the new algorithm doesn't threaten the quantum speedup there. On the other hand, yes, unless I'm mistaken it does make the speedup much smaller in the $Z\_{p^k}$ case.


---

### Answer by username_1 on 2013-06-25. Score: 6

My understanding is that if $k = O (q)$, the algorithm has complexity $n^{O (\log n)}$ over finite fields $F\_{q^k}$ assuming that $k = O (q)$. More generally, the algorithm has complexity $L\_{q^k} (\alpha, O (1))$ in finite fields $F\_{q\_k}$ with $q \sim L\_{q^k} (\alpha)$. It beats previous classical algorithms for $\alpha < 1 / 3$.

Shor's algorithm is still much faster, but the question about exponential speedup depends really on the definition of "exponential". (Also NFS/FFS were subexponential-time.)


---

