Proof of $\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) $ for discrete logarithm?

1k Views Asked by At

If you have that $a$ is a primitive root mod $p$. How can you prove this discrete logarithm property?

$\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) \pmod{p-1}$

I see the proof for the regular product rule with out the modular arithmetic, but I don't see where the $p-1$ comes from. http://www.onlinemathlearning.com/logarithms-properties.html

1

There are 1 best solutions below

0
On

Note that $a^{\log_a(b_1) + \log_a(b_2)} \pmod p = a^{\log_a(b_1)}a^{\log_a(b_2)} \pmod p = b_1 b_2$ which means that, up to a multiple of $p-1$, $\log_a(b_1) + \log_a(b_2) = \log_a(b_1 b_2)$.

The fact that in the exponents we work modulo $p-1$ comes from Fermat's theorem that $a^{p-1} \equiv 1 \pmod p$. This means that if $x \equiv y \pmod {p-1}$, so $x = y + k(p-1)$ for some integer $k$, then $a^x = a^{y + k(p-1)} = a^y (a^{p-1})^k \equiv a^y 1^k \pmod p = a^y$. Hence just knowing that $a^x = b$ doesn't warrant the conclusion that $x = \log_a(b)$, only that it is one that differs from it by a multiple of $p-1$.

The $\log_a(b)$ is the unique $x \in \{0,\ldots,p-2\}$ such that $a^x = b \pmod p$. But adding or substracting any multiple of $(p-1)$ yields the same exponentation result, as we saw. So adding the two logarithms could give a value $> p-1$, and then this result is not the log of the product, because we substract $p-1$ first to get it in the right range.