# Discrete Logarithm

If $p$ is a prime and $a,b$ are integers not divisible by $p$ such that $a^x \equiv b \pmod p$ with $0 ≤ x < o_p(a)$, then we define $x = L_a(b)$ and say $x$ is the discrete logarithm of $b$ with respect to $a$ (of course the discrete log also depends on $p$). Suppose $o_p(a)=r$. Prove that for any integer $b$ not divisible by $p$, the discrete log $L_a(b)$ exists if and only if $b^r \equiv 1 \pmod p$.

[ $o_p(a)$ is the (multiplicative) order or $a$ modulo $p$. ]

-
yea that was a typo. thanks! – Gabe Apr 16 '13 at 14:48

Observe the definition of Discrete Logarithm

$ord_pa=r\iff a^r\equiv1\pmod p$

$b^r\equiv(a^x)^r\equiv (a^r)^x\equiv 1^x\equiv1\pmod p$

Conversely, if $b^r\equiv1\pmod p\implies (a^x)^r\equiv1\implies a^{rx}\equiv1$

As $a,b$ are arbitrary so will be $x$ then $a^{rx}\equiv1\pmod p$ will be true iff $r=p-1$

-
No, the first $\iff$ is only true of $a$ is a primitive root, modulo $p$. For example, if $p=13,a=5,b=8$, then $a^x\equiv b\pmod p\iff x\equiv 3\pmod 4$ – Thomas Andrews Apr 16 '13 at 15:08
@ThomasAndrews, the concept of discrete logarithm is based on primitive root , right? – lab bhattacharjee Apr 16 '13 at 15:10
That's not how the OP defined it - it was defined over arbitrary $a$, otherwise there would be no need for $r$ - $r=p-1$ when $a$ is a primitive root. – Thomas Andrews Apr 16 '13 at 15:11
The point of the "conversely" is to show that such an $x$ exists. You've just assumed it. – Thomas Andrews Apr 16 '13 at 15:31