Discrete logarithm modulo a smooth number I am solving the discrete logarithm problem modulo $N$. $N$ is a composite number, I found its factors — lots of small primes and two big primes ($&gt; 2^{50}$).
Does the factorization of $N$ somehow help me? I think I could compute the logarithm modulo each prime and then combine it, but I do not know how to do this exactly. It seems similar to problems for the chinese remainder theorem, but I cannot find the way to do it.
Does the factorization of N somehow help me?


It sure does.


  I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it.


You're real close; you do recombine them using the Chinese Remainder Theorem; however the modulus you use aren't the prime factors, but one less (unless a prime factor is repeated; that gets handled slightly differently).

I suspect the easiest way to explain this might be to write up an example; suppose we have $N = p\cdot q\cdot r$, where $p$, $q$ and $r$ are the distinct prime factors, and we want to solve:

$$a = b^x \pmod{N}$$

So, what we do is to find the three values $y$, $z$ and $w$ with:

$$a = b^y \pmod{p}$$
$$a = b^z \pmod{q}$$
$$a = b^w \pmod{r}$$

and then use the CRT to find the $x$ with:

$$x = y \pmod{p-1}$$
$$x = z \pmod{q-1}$$
$$x = w \pmod{r-1}$$

We do it modulo $p-1$, and not modulo $p$, because $p-1$ is the order of the group $Z^*_p$

Note that there might not be any such $x$ (because $p-1$, $q-1$ and $r-1$ are not relatively prime); if that is the case, then original equation is unsolvable.

If there is a repeated factor (for sample, $p^k$ is a factor of $N$), you do the same, however when you use the CRT, you do that one modulo $p^{k-1}(p-1)$