Discrete logarithm - strange polynomials If $p$ is a prime number and $\omega$ is a fixed primitve root for $\mathbb{Z}/p\mathbb{Z}$, then we can define the discrete logarithm of $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ as the unique number $\log_{\omega} x$ between $1$ and $p-1$ such that $\omega^{\log_{\omega} x} = x$.
$\log_{\omega} x$ will be identified with its remainder class in $\mathbb{Z}/p\mathbb{Z}$.
I was interested in finding the interpolating polynomial in $\mathbb{Z}/p\mathbb{Z}[x]$ of minimal degree for this $\log_{\omega}$ function (for fun?) and looked at a few examples where $\omega = 3$ can be taken as a fixed primitive root. Some examples:
modulo $5$, $\log_3(x) = 4x^3 + 3x^2 + 2x$.
modulo $7$, $\log_3(x) = 5x^5 + 2x^4 + 4x^3 + 6x^2 + 3x$.
modulo $17$, $\log_3(x) = $
$$10x^{15} + 16x^{14} + 3x^{13} + 11x^{12} +14x^{11} + 12x^{10} + 13x^9 + 9x^8 + 5x^7 + 6x^6 + 4x^5 + 7x^4 + 15x^3 + 2x^2 + 8x.$$
I notice that the coefficients in each case are exactly the numbers $2$ to $p-1$ up to permutation. Is there something behind this? It seems highly improbable if it's a coincidence.
 A: This can be settled by an application of discrete Fourier analysis of functions on the group $\mathbb{F}_p^*$ with values in the same field. It is easy to see that monomial
functions form an "orthogonal" basis for functions from $\mathbb{F}_p^*$ to $\mathbb{F}_p$. The orthogonality relation is the following observation
$$
\sum_{x\in\mathbb{F}_p^*}x^i=
\begin{cases}p-1=-1,&\text{if $(p-1)\mid i$, and}\\
0,&\text{otherwise.}\end{cases}
$$
Here the exponent $i$ can be any integer.
This can be proven by using cyclicity of $\mathbb{F}_p^*$. The sum is a geometric sum of a full set of roots of unity unless it is a trivial sum of several ones.
The function $f:\mathbb{F}_p^*\to\mathbb{F}_p$ that interests OP is the following
$$
f(x)=\begin{cases}p-1,&\text{if $x=1$, and}\\ k,&\text{if $x=\omega^k$, $0<k<p-1$.}\end{cases}
$$
By Lagrange interpolation, we can write $f$ as a polynomial of degree $\le p-2$
$$
f(x)=\sum_{i=0}^{p-2}a_ix^i
$$
for some coefficients $a_i\in\mathbb{F}_p$.
We can determine the coefficients $a_i$ using the sums
$$
\begin{aligned}
\sum_{x\in\mathbb{F}_p^*}f(x)x^{-j}&=\sum_{x\in\mathbb{F}_p^*}\sum_{i=0}^{p-2}a_ix^{-j+i}\\
&=\sum_{i=0}^{p-2}a_i\sum_{x\in\mathbb{F}_p^*}x^{i-j}\\
&=-a_j
\end{aligned}
$$
for all $j$. Observe that, if $j=0$, then
$$
-a_0=\sum_{x\in\mathbb{F}_p^*}f(x)=\sum_{i=1}^{p-1}i=\frac{p(p-1)}2=0.
$$
Next we observe that $f(\omega x)=f(x)+1$ unless $x=1$ in which case $f(\omega \cdot1)=1=f(1)+2.$ Also we observe that as $x$ ranges over $\mathbb{F}_p^*$ so does $\omega x$. So with $0<j<p-1$ we get
$$
\begin{aligned}
-a_j&=\sum_{x\in\mathbb{F}_p^*}f(x)x^{-j}\\
&=\sum_{x\in\mathbb{F}_p^*}f(\omega x) (\omega x)^{-j}\\
&=\omega^{-j}\left(\sum_{x\in\mathbb{F}_p^*}[(f(x)+1)x^{-j}]+1\cdot1^{-j}\right)\\
&=\omega^{-j}\left(-a_j+\sum_{x\in\mathbb{F}_p^*}x^{-j} +1\right)\\
&=\omega^{-j}(1-a_j).
\end{aligned}
$$
From this equation we can solve
$$
a_j=\frac{\omega^{-j}}{\omega^{-j}-1}=\frac{1}{1-\omega^j}.
$$
As $j$ ranges over the interval $1\le j<p-1$, the quantity $\omega^j$ ranges over all the elements of the set $\mathbb{F}_p\setminus\{0,1\}$. Consequently so does $a_j$ confirming OP's conjecture.
