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


Choose a random integer $a \in \mathbb{Z}_N$ (without loss of generality, we assume $\gcd(a,N) = 1$ &mdash;otherwise, this yields the factorization of $N$ and the factorization problem is solved).
Consider the univariate function $f: x \mapsto f(x) = a^x \bmod N$.
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)$ &mdash;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$.


Consider the bivariate function $f : (x_1, x_2) \mapsto g^{x_1} y^{x_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)$.
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$.