# 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 ($> 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.

• You are looking for the Pohlig-Hellman algorithm. :) – fkraiem Dec 31 '14 at 20:55

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)$

• Thank you very much @poncho , your example is nice and was easy to understand. By the way, when I am counting the logarithm modulo each prime, in few cases $a (mod p) = 1$, so for $a = b^{y} (mod p)$ my $y = 0$. Does this mean any problem for me? I don't know if zero is the only true exponent in these cases or just my algorithm (Pohlig-Hellman) did not find better solution. Can be zero legitimate solution and be used in CRT normally? – Ding Jan 1 '15 at 18:09
• @Ding: $y=0$ is absolutely not a problem. If you are worried that there might not be any other solutions, well, $y=k(p-1)$ (for any integer $k$) will also be a solution. – poncho Jan 1 '15 at 18:17
• ok i understand, thanks. And the last (I hope) problem I am encountering right now: one of the factors of my $N$ is $p = 17$. And both $a$ and $b$ are divisible by $17$. So practically I am solving $0 = 0^{x}$. I can't even guess what to do with this, since it is true for every possible $x$. – Ding Jan 1 '15 at 18:31
• @Ding: just ignore it then; if it is true of every possible $x$, it needn't be a constraint for selecting an $x$ – poncho Jan 1 '15 at 19:31