4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You are looking for the Pohlig-Hellman algorithm. :) $\endgroup$ – fkraiem Dec 31 '14 at 20:55
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ding Jan 1 '15 at 18:09
  • $\begingroup$ @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. $\endgroup$ – poncho Jan 1 '15 at 18:17
  • $\begingroup$ 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$. $\endgroup$ – Ding Jan 1 '15 at 18:31
  • $\begingroup$ @Ding: just ignore it then; if it is true of every possible $x$, it needn't be a constraint for selecting an $x$ $\endgroup$ – poncho Jan 1 '15 at 19:31

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.