Find smallest $x$ such that $a^x \equiv b \bmod p$

Question

Problem: How do we find smallest $x$ such that $a^x \equiv b \bmod p$, where $p$ is a prime and $1 \le b,a \le p$ and $a$, $b$, and $p$ are given and fixed. If there is no such $x$, how do we check it ?

Brute force approach is to iterate over all $x$ starting from $1$ up till when $a^x\equiv 1 \bmod p$ and return the smallest such $x$ if exists.

Is there some closed formula to solve these kinds of equations ?

Answer 1

There is an explicit formula for the discrete logarithm:

$$x=\log_a b=\sum\limits_{i=1}^{p-2} \frac{b^i}{1-a^{i}} \mod{p}.$$

See, the thesis , Theorem 3.2