# How can Shor's Algorithm be applied to ECC?

Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$.

This is done by creating an equal superposition over all pairs of $a_i$ and $f(x)=x^{a_i}$ for a random $x$, then measuring $f(x)$ causing the superposition to collapse into all $a_i$ for which $f(x)$ is our measures value. Using "Fourier sampling" (I have not fully understood this part) we can then obtain the period of $\ f$ and with .5 probability this yields a non-trivial square root of $N$ which leads to a prime factor.

(Plase correct me if my understanding of the above is flawed)

Now how can this algorithm be applied to Elliptic Curve schemes like ECDSA? I struggle to find an explanation for how the discrete log problem for groups over elliptic curves could be solved using Shor's.

EDIT: I would just as well appreciate a reference to other papers except Shor's, that explain the case of Shor's algorithm on DLPs.

• Do you understand how the discrete logarithm problem is solved over $\mathbb Z^*_p$ using Shor's algorithm? – SEJPM Nov 2 '17 at 20:20
• I read Shor's paper but did not understand the DLP part. From what I learned, if our $\mathbb{Z}_p^\ast$ DLP is find $r$ so that $g^r \equiv x$ mod $p$, we create superpositions over all $\ket{a}$ and $\ket{b}$ and calculate $g^ax^{-b}$ mod $p$. What is this good for to find the order of the group we are looking for? – indiscreteLogarithm Nov 2 '17 at 20:46
• You may find this reference arxiv.org/abs/quant-ph/0301141 , interesting (found via the always useful quantum algorithm zoo math.nist.gov/quantum/zoo) – Frédéric Grosshans Nov 3 '17 at 10:02
• @Frédéric Grosshans thanks for the reference, I read this paper but could you maybe give a few sentences describing what is done, like I did for integer factorization in the initial post? I can read the formulas in the paper, but I'm uncertain what they actually do. – indiscreteLogarithm Nov 4 '17 at 11:50