1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – jvdh Feb 1 at 13:21
  • $\begingroup$ 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. $\endgroup$ – jvdh Feb 1 at 13:29
  • $\begingroup$ 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$ $\endgroup$ – jvdh Feb 1 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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