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

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 ?

• If there were a closed formula, a lot of cryptographers would be very upset.
– Sal
Dec 14 '14 at 7:38
• Are a, b, and p all given, or are we free to choose one or more of them? If they are given, I think a^x = 1 mod p should be a^x = b mod p? Dec 14 '14 at 7:47
• As already commented by Sal any closed formula would cause the collapse of lot of encryption scheme that rests on the computational difficulty of the "Discrete Logarithm Problem" Dec 14 '14 at 8:06
• @2012rcampion no it's correct. They are suggesting an algorithm for finding the smallest positive integer $x$ such that $a^x \equiv b\mod p$. To do this, they check all values of $x$ from 1 onwards, until they they find such an $x$. However the values of $a^x$ modulo $p$ repeat after $a^x$ is congruent to 1 modulo $p$, so if no solution is found before then, there are none. Dec 14 '14 at 8:07
• @PVa, not if the closed formula was computationally infeasible. Dec 14 '14 at 12:03

$$x=\log_a b=\sum\limits_{i=1}^{p-2} \frac{b^i}{1-a^{i}} \mod{p}.$$
• $7^3 \text{ mod } 11 = 2<> \sum_{i=1}^{11-2} \frac{2^i}{1-7^{i}} \text{ mod } 11 = 10,55$ ??? Aug 4 '17 at 7:14