# 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 $e$ given the following information (Assume that $P$, $C$, $N$ and $e$ are all large, say 2048-bit integers):

• the integers $P$ and $N$
• the integer $C$ where $C = P^e \bmod N$

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) – poncho Jun 11 '16 at 23:34
• – SEJPM Jun 12 '16 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. The solution to the discrete logarithm problem is then given by $k = -\omega_1/\omega_2 \bmod q$. Indeed, one has $f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2) \iff 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 \pmod 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 '19 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 '19 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 '19 at 14:42