An explicit formula for the discrete logarithm

I guess, but i am not sure, many people don't know that there is an explicit formula for the discrete logarithm in finite fields $\mathbb{F}^*_p$. I remember that i was quite surprised when i learned the formula many years ago.

Theorem [Explicit DL Formula]

Let $p$ be a prime number $>2$ and $g$ be a primitive root in $\mathbb{F}^*_p$. Then the discrete logarithm of the element $a \in \mathbb{F}^*_p$ [i.e. the exponent $x$ from $g^x \equiv a\pmod{p}$] is equal to
\begin{equation} \mathsf{dlog}_{p,g}(a) = \sum^{p-2}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

Note: This is a finite-sum identity that still costs $\approx \mathcal{O}(p)$ field ops, so it’s not a practical attack on discrete log for large primes but it’s conceptually neat (character sums / interpolation flavor). Although the discrete logarithm is naturally defined modulo $p-1$, the above identity evaluates in $\mathbb{F}_p$ and yields the unique integer representative in ${0,\dots,p-2}$.

The proof is actually not that complicated and can be found in Niederreiter [1]. I will give here a new proof for you:

Proof:

To prove this, we rewrite the sum in the following way:

\[ \begin{align*} -\mathsf{dlog}_{p,g}(a) & = \sum^{p-2}_{k=1} \frac{a^k}{g^k-1}\pmod{p} \\ & \equiv \sum^{p-2}_{k=1}a^k(g^k-1)^{p-2} \pmod{p} \end{align*} \]

Next, we apply the Binomial Theorem:

\[ \begin{align*} -\mathsf{dlog}_{p,g}(a) \equiv \sum^{p-2}_{k=1}a^k\sum^{p-2}_{i=0}\binom{p-2}{i}g^{ki}(-1)^{p-2-i}\pmod{p} \end{align*} \]

As already shown in the post Agoh-Guiga Conjecture, it is $$\binom{p-2}{i} \equiv (-1)^i(i+1)\pmod{p}$$ hence

\[ \begin{align*} -\mathsf{dlog}_{p,g}(a) & \equiv \sum^{p-2}_{k=1}a^k\sum^{p-2}_{i=0}\binom{p-2}{i}g^{ki}(-1)^{p-2-i}\pmod{p}\\ & \equiv \sum^{p-2}_{k=1}a^k\sum^{p-2}_{i=0}(-1)^i(i+1)g^{ki}(-1)^{p-2-i}\pmod{p}\\ & \equiv -\sum^{p-2}_{k=1}a^k\sum^{p-2}_{i=0}(i+1)g^{ki}\pmod{p} \end{align*} \]

Removing the minus-sign and switching the sums

\[ \begin{align*}\mathsf{dlog}_{p,g}(a) & \equiv \sum^{p-2}_{k=1}a^k\sum^{p-2}_{i=0}(i+1)g^{ki}\pmod{p} \\ & \equiv \sum^{p-2}_{i=0}(i+1)\sum^{p-2}_{k=1}(ag^{i})^k\pmod{p} \end{align*} \]

It is easy to see that (Note, we do not apply the explicit power sum formula)

\[ \begin{equation} \sum^{p-2}_{k=1}(ag^i)^k \equiv \begin{cases} -2 & ag^i \equiv 1\pmod{p}\\ -1 & ag^i \not\equiv 1\pmod{p} \end{cases} \end{equation} \]

Note that $ag^i\equiv 1\pmod{p}$ is equivalent to $i = p-1-\mathsf{dlog}_{p,g}(a)$. And this $i$ value is counted twice, since it yields a $-2$ instead of a $-1$. So (using the indicator function $\mathsf{1}_S$ that is $1$ if $S$ is true and $0$ otherwise)

\[ \begin{align*} \mathsf{dlog}_{p,g}(a) & \equiv \sum^{p-2}_{i=0}(i+1)\left(-1 - \mathsf{1}_{i = p-1-\mathsf{dlog}_{p,g}(a)}\right) \\ & \equiv -\sum^{p-2}_{i=0}(i+1) - \sum^{p-2}_{i=0}(i+1)\mathsf{1}_{i = p-1-\mathsf{dlog}_{p,g}(a)}\\ & \equiv -\sum^{p-2}_{i=0}(i+1) - (p-1-\mathsf{dlog}_{p,g}(a)+1)\\ & \equiv -\frac{(p-2)(p-1)}{2}-(p-1) + \mathsf{dlog}_{p,g}(a)\\ & \equiv \mathsf{dlog}_{p,g}(a) \end{align*} \] Q.e.d.

Note that the requirement that $g$ is a primitive root is necessary therewith the denominator never gets zero for any $k$.

Example: p=11, g=2, a=3 (click to expand)

$$\frac{3^1}{1-2^1}+\frac{3^2}{1-2^2}+\frac{3^3}{1-2^3}+...+\frac{3^9}{1-2^9}$$ which is $$\frac{3}{10}+\frac{9}{8}+\frac{5}{4}+\frac{4}{7}+\frac{1}{2}+\frac{3}{3}+\frac{9}{5}+\frac{5}{9}+\frac{4}{6} \equiv 8 \pmod{11}$$ which is correct since $2^8 \equiv 3 \pmod{11}$.

All divisions are performed in $\mathbb{F}_{11}$, i.e., denominators are interpreted via multiplicative inverses modulo $11$.

Somewhere in my old notes, i found a generalisation of the above theorem to non primitive roots, that is:

Theorem [Explicit DL Formula - Subgroup]

Let $p$ be a prime number $>2$ and $g$ be an element in $\mathbb{F}^*_p$ with $\mathsf{ord}_p(g) = w$. Then the discrete logarithm of the element $a \in \mathbb{G}$ is equal to
\begin{equation} \mathsf{dlog}_{p,g}(a) =  1+ \frac{w-1}{2} + \sum^{w-1}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

Proof: Analogous.

For $w = p-1$ this turns into the original formula. I find this formula very interesting.
Could this formula perhaps be used, to show some non-trivial relationship between discrete logarithms in different fields $\mathbb{F}^*_p$ and $\mathbb{F}^*_q$ $$\sum^{p-2}_{k=1} \frac{a^k}{1-g^k} \leftrightarrow \sum^{q-2}_{k=1} \frac{a^k}{1-g^k}$$ for $g$ being primitive in both fields?

[1] Harald Niederreiter, A short proof for explicit formulas for discrete logarithms in finite fields, Applicable Algebra in Engineering, Communication and Computing 1990, Volume 1, Issue 1, pp 55-57