I'm studying the Index Calculus method for Discrete Logarithm. In the book "Introduction to Cryptography with Coding Theory" by Trappe it's told that, if $$\alpha^k\equiv \prod p_i^{a^i} \mod p$$ holds, then $$k\equiv \sum a_i L_\alpha(p_i) \mod (p-1).$$ However, it doesn't show why. Can you explain to me?
1 Answer
Given $$\alpha ^{k}\equiv \prod p_{i}^{a^{i}} \mod p$$
take $\log$ of both sides to base $\alpha$
\begin{align} \log_\alpha(\alpha ^{k}) &\equiv \log_\alpha(\prod p_{i}^{a^{i}}) \mod p\\ k &\equiv \sum \log_\alpha(p_{i}^{a^{i}}) \mod p-1 \quad\text{;by Little Fermat}\\ k &\equiv \sum a_i \log_\alpha(p_{i}) \mod p-1\\ \end{align}
Here $\log_{\alpha} = L_{\alpha}$.