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.

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.