Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
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$. –  minar Jul 23 '13 at 11:04

1 Answer 1

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.

share|improve this answer
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? –  frogeyedpeas Apr 23 at 22:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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