# 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.

-
But the values of the discrete logarithm are in the group $\mathbb{Z}/(p-1)\mathbb{Z}$??! After all $\omega^{i+(p-1)n}=\omega^i$ for all $i,n$, so the discrete log can be identified with its residue calss in $\mathbb{Z}/(p-1)\mathbb{Z}$. And I don't see a natural way of viewing $\mathbb{Z}/(p-1)\mathbb{Z}$ as a subset of $\mathbb{Z}/p\mathbb{Z}$. – Jyrki Lahtonen Apr 10 '13 at 4:34
@JyrkiLahtonen Yes, I know. However I just take the integer value and reduce in mod $p$. For example, we have $3^x = 4x^3 + 3x^2 + 2x$ mod $5$ for all $x \ne 0$. Otherwise I think there would be no way to interpolate – user71811 Apr 10 '13 at 5:20
Ok. For fun, sure :-) – Jyrki Lahtonen Apr 10 '13 at 6:11
In that case harmonic (Fourier) analysis on the group may give you some answers... Got a lecture to deliver. Think about it later. – Jyrki Lahtonen Apr 10 '13 at 6:13
Yes. You're right. Sorry about forgetting to look into this for a long time. – Jyrki Lahtonen Jul 13 '13 at 15:24

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.