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.


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.