# Reduction of Integer factorization to Discrete logarithm problem

I was reading Eric Bach paper entitles Discrete logarithms and factoring, in which he states the following reductions: solving the integer factorization problem suffices to solve the discrete logarithm problem and vice versa.

I could not completely understand the explanation. Could anyone explain it to me or refer me to another source.

• Your formulation of the statement is somewhat misleading. Bach proves: 1) If you can compute log. modulo $N$, you can factor $N$ 2) If you can factor $N$ and compute logs modulo each factor, then you can compute logs. modulo $N$. Jul 23 '13 at 11:04

1. First direction, from discrete logs modulo $N$ to factoring. Assume that there is a fixed basis $g$ for the method that computes logs. Choose a random $x$ modulo $2N$ and compute $y=g^x\pmod{N}$, then ask for the logarithm of $y$. Let $x'$ denotes the answer to the discrete log problem. If $x=x'$ restart, else $x'-x$ is a multiple of the order of $g$ modulo $N$. Once this is known, apply the randomized method described as answer to Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group? and factor $N$.
2. Second direction. If the factorization of $N$ is known, then $y=g^x\pmod{N}$ implies $y=g^x\pmod{p}$ for each prime factor $p$ of $N$. As a consequence, computing discrete logarithms modulo $p$ gives $x$ modulo the order of $g$ modulo $p$ (this is $p-1$ is $g$ is a multiplicative generator modulo $p$). Assuming for simplicity that $N$ is squarefree, it now suffices to paste together all the partial solution using the chinese remainder theorem and you get the logarithm modulo $N$. Note if the chinese remainder theorem does not give a solution because the logarithms modulo the various orders are incompatible, it means that the original problem does not have a solution.
On squarefreeness. Without the squarefree assumption on $N$, you need to compute logarithms modulo powers of $p$. This is not harder than computing logarithms modulo $p$ but requires some technicalities.
• About 1. If i understand well, we take $x$ mod $2N$ to hope that it will be different from $x'$ then. Why not taking $x$ between $N$ and $2N$ instead ? At the end, we get a multiple of the order of $g$ mod $N$. What happen if we do not get this order, but a strictly greater multiple of this order ? Feb 22 '19 at 13:45