# Using Shor's algorithm to solve the discrete logarithm problem

I have read about Shor's algorithm and my understanding is that it can be used to factor large numbers efficiently. Can Shor's algorithm, though, be used to solve this problem:

Find the number $$n$$ given the following information (Assume that $$g$$, $$n$$, $$P$$ and $$a$$ are all large, say 2048-bit integers):

• the integers $$g$$ and $$P$$
• the integer $$a$$ where $$a = g^n \bmod P$$

If so, how does this algorithm work? Please explain it simply as I am not familiar with quantum mechanics.

• Actually, conventional computers can solve that problem reasonably easily if we're talking about 256 bit integers. Conventional wisdom says that N needs to be at least 2048 bits to be secure against conventional computers (and it's not at all secure against a quantum one - if no one else answers, I'll spell it out when I get some time) Jun 11, 2016 at 23:34
• Jun 12, 2016 at 13:35

Shor's method relies on a period finding routine on a quantum computer.

A function $$f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$$ is periodic, of period $$(\omega_1, \dots, \omega_n)$$, if $$f(x_1 + \omega_1, \dots, x_n + \omega_n) = f(x_1, \dots, x_n)$$ for all tuples $$(x_1, \dots, x_n)$$ in the domain of $$f$$.

Factorization problem Given an RSA modulus $$N = pq$$, find primes $$p$$ and $$q$$.

1. Choose a random integer $$a \in \mathbb{Z}_N$$ (without loss of generality, we assume $$\gcd(a,N) = 1$$ —otherwise, this yields the factorization of $$N$$ and the factorization problem is solved).

2. Consider the univariate function $$f: x \mapsto f(x) = a^x \bmod N$$.

3. The period finding routine finds an $$\omega$$ such that $$f(x + \omega) = f(x)$$. As a consequence, $$\omega$$ is a multiple of the order of $$a$$ modulo $$N$$. Indeed, one has $$f(x+\omega) = f(x) \iff a^\omega \equiv 1 \pmod N$$.

If $$\omega$$ is a multiple of $$\lambda(N)$$ —where $$\lambda(N)$$ denotes Carmichael's function, then Miller's algorithm yields the factorization of $$N$$. Otherwise, repeat the process with another $$a$$, get the period $$\omega_a$$, and update $$\omega$$ as $$\omega \gets \operatorname{lcm}(\omega, \omega_a)$$, until $$\omega$$ is a multiple of $$\lambda(N)$$.

[ A description of Miller's algorithm can be found in Cryptography: Theory and Practice by Douglas Stinson, http://cacr.uwaterloo.ca/~dstinson/CTAP.html ]

Discrete log problem Let $$g$$ be a generator of a group $$\mathbb{G}$$ of prime order $$q$$. Given $$y = g^k \in \mathbb{G}$$, find the value of $$k$$.

1. Consider the bivariate function $$f : (x_1, x_2) \mapsto g^{x_1} y^{x_2}$$.

2. The period finding routine finds a pair $$(\omega_1, \omega_2)$$ such that $$f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2)$$.

3. This implies: $$g^{\omega_1} y^{\omega_2} = 1_{\mathbb{G}} \iff g^{\omega_1 + k\omega_2} = 1_{\mathbb{G}}$$ and thus $$\omega_1 + k\omega_2 \equiv 0$$, or $$k\omega_2 \equiv -\omega_1\pmod q$$.

4. There are $$q$$ pairs $$(\omega_1,\omega_2)$$ which produce this result. If each result is equally likely, then there is only a $$1/q$$ probability that $$(\omega_1,\omega_2)\equiv (0,0)\pmod q$$. On the $$(q-1)/q$$ probability that it is not zero, the solution to the discrete logarithm problem is then given by $$k = -\omega_1/\omega_2 \bmod q$$.

• can you comment why $q \neq \omega_1$? To me it seems that if $g^{\omega_1} = 1 (\bmod p)$ then $\omega_1$ is the order of $\mathbb{G}_p$.
– jvdh
Feb 1, 2019 at 13:21
• Ah, I see, this is for $\mathbb{G}$. In my understanding Shor's algorithm solves the discrete log problem for $y=g^k\in \mathbb{Z}_p^*$ where $p$ is prime and therefore it's order $q=p-1$ cannot be prime as well.
– jvdh
Feb 1, 2019 at 13:29
• I think your solution for the discrete log problem is wrong: if $q$ prime, then $\omega_1 = \omega_2 = q$ and we cannot learn anything about $k$
– jvdh
Feb 1, 2019 at 14:42