Solve $a \equiv b^c \pmod {d}$ for $c$

Question

I'm trying to solve the following equation for $c$.

$$a \equiv b^c \pmod {d}$$

I'm given arbitrarily large numbers ($a$, $b$, and $d$ to solve for c, examples below), but it's just not feasible to iterate through every possible $c$ and check (using the GNU Multiple Precision Arithmetic Library) the congruency. Is it possible to solve the equation for $c$ or limit my search space?

$a = 4.557304... \times 10^{308}$

$b = 201527$

$c = 1.9 \times 10^{38}$

$d = 1.569203... \times 10^{309}$

Looks a lot like double/single precision floating point. If you use multi-precision integers it is a discrete_logarithm problem — gammatester, Sep 15 '17 at 21:33
@gammatester I shortened the numbers to floating point, but I'm actually given the entire 308 digit integer. Unless I'm misunderstanding what you're trying to say. — user10984587, Sep 15 '17 at 21:52

score 0 · Answer 1 · answered Sep 15 '17 at 21:52

This is called a discrete logarithm. Computationally, it isn't as easy as a standard logarithm, and is time-complexity wise likely similar to factorization. There's more information on the Wikipedia page about actually calculating it, but it's, generally speaking, computationally "hard".

Solve $a \equiv b^c \pmod {d}$ for $c$

1 Answers1