2 of 8 Added spaces, list for readability, used tex notation

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, the reduction is not known. I copied the following from this wikipedia page with minor edits.

Let $n = pq$ be RSA modulus.

  1. Generate random number $a$ co-prime to $n$ and random number $x < n$ but very close to $n$.

  2. Compute $b = a^x \text{ mod } n$ but don't tell $x$ to the 'discrete log oracle'.

  3. Instead ask it to find the discrete log of $b \text{ mod } n$ (to base $a$). Let the value returned by the oracle be $y$.

  4. There is a very high probability that $y \neq x$. If so $x-y$ will be a multiple of the order of $a$ which can easily be used to factor $n$. I will not go to the details of factoring once (a multiple of) the order of $a$ is known. (since this is a well known method, also used in Shor's algorithm). If we are unlucky and $x=y$, then we start over.