Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.