2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – minar Jul 23 '13 at 11:04
3
$\begingroup$

Here is a quick summary:

  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.

$\endgroup$
  • 3
    $\begingroup$ The Part 2 doesn't really show equivalence. Since it only shows that composite versions of discrete logarithm ultimately reduce to discrete logarithm mod p, BUT it does not show how to break this last problem through an Integer Factorization oracle. Can that be shown? $\endgroup$ – frogeyedpeas Apr 23 '15 at 22:22
  • $\begingroup$ on 2. this is called pohlig-hellman and it won't work if some of the factors are too large. $\endgroup$ – David 天宇 Wong Jul 16 '18 at 9:04
  • $\begingroup$ 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 ? $\endgroup$ – tyuil Feb 22 at 13:45

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.