Discrete log over a prime

Question

I have a prime $p$ such that $p-1=2 p_1p_2$ such that $p_1$ has $200$ digits in base $2$ and $p_2$ has 50. I want to find discrete logarithm of $a^b =c \pmod p$. That is I want to find $b$ given $a,c, p$. I know the remainder of $b \pmod{p_1}$. How can I use this information to find $b$? Of course I can check all possible options in $[0, p_2-1]$ and use Chinese Remainder Theorem (CRT) to find $b$. But can we do better than this?

Answer 1

There are various algorithms for finding discrete logarithms. For the bit sizes you specify, this is certainly possible to do quite efficiently, for example a few of the algorithms you can use to accomplish this are Pohlig–Hellman algorithm, Baby-step giant-step, Pollard's rho.

As you may know, finding discrete logarithms efficiently is known as the "Discrete logarithm problem", which is of significant interest in the field of Cryptography, owing to the fact that a lot of the common public encryption schemes in wide use today are based on the hardness of computing discrete logarithms (over prime integer fields with a $p$ that has a lot more bits than what you have here, or over elliptic curves which are a different beast).

If you want to see a bit more of "state of the art" results regarding this subject, this may be of interest.