How to evaluate this function in F_p efficiently?

Question

For the positive prime integer $p$, Let $\mathbb{F}_p=\{0,1,\cdots, p-1\}$ be the finite field of order $p$.

For $x\in \mathbb{F}_p$, define $f_p(x)$ to be the maximum element in the set $\{ x^n+x^{-n}\in \mathbb{F}_p | n\in {\mathbb{Z}}\}$.

For instance, when $p=17$, for $x=2$, we have $f_{17}(x)=\max\{2^0+2^0=2, 2^1+2^7=11, 2^2+2^6=0, 2^3+2^5=6, 2^4+2^4=15\}=15$.

My question is: when $p$ is relatively small, we can compute every $f_p(x)$ in the brute-force manner. However, such strategy does not work when $p$ is very large; in such cases, is there some "efficient" way to compute every $f_p(x)$?

Or more broadly, could we find a non-trivial upper bound on $f_p(x)$ for some $\textit{special}$ $x$'s? For instance, when the multiplicative order of $x$ is some special factor of $(p-1)$?

Plus, could you suggest some materials that might be relevant to my question?

Thanks!!

Answer 1

Note that we can solve $x^n + x^{-n} = a \bmod p$ to get

$$ x^n \equiv \frac{a \pm \sqrt{a^2 - 4}}{2} \pmod p$$

For "most" $p$ and $x$, there is a relatively easy algorithm:

• For $a = p-1, p-2, \ldots $:
  • Check that $a^2 - 4$ is a square mod $p$
  • Compute $b_{\pm} \equiv \frac{a \pm \sqrt{a^2 - 4}}{2} \pmod p$
  • Check if each $b_\pm$ is a power of $x$ mod $p$ (e.g. computing the order $g$ of $x$ and testing if $b_{\pm}^g = 1 \bmod p$)

For large, "bad" $p$ and $x$, I mildly doubt that there is a computationally feasible algorithm.

Answer 2

I think it might be computationally hard to answer this question for all $x$ when $p$ is large as it might involve computing the order of $x$ which in turn depends on the factorization of $p-1$ or it might involve solving discrete logs. I have no proof but here are some partial results.

If $u=-1, u+u^{-1} = p-2$ and if $u$ has order $6, u+u^{-1} = p-1$. So, if $p \equiv 1 \pmod 3$ and $x$ has order divisible by $6$, $f_p(x)=p-1$ and, if the order of $x$ is even but not divisible by $3$, $f_p(x)=p-2$. When $p \equiv 2 \pmod 3$ and the order of $x$ is even, $f_p(x)=p-2$. Checking if you are on these cases is easy but as you eliminate these possibilities, you will be faced with finding $u$ with $u+u^{-1}$ large and computing the order of $u$ or deciding if $u$ is a power of $x$ (which then might involve the discrete log problem, also computationally hard).

Answer 3

To get a fair distance to $p-1$ we need a sparse set of powers of $x$. So working on the theme of your last question and restricting ourselves to elements of specific order, let me proffer the following.

Felipe already covered elements of orders two and three, so order five is next. For those to exist we need $p\equiv1\pmod5$. The law of quadratic reciprocity then tells us that $5$ has a square root in $\Bbb{F}_p$. Anyway, let $\zeta$ be a primitive root of unity of order five in $\Bbb{F}_p$. Then the list we need to study is $$ \begin{aligned} \zeta^0+\zeta^{-0}&=2,&\\ \zeta^1+\zeta^{-1}&=A,&\\ \zeta^2+\zeta^{-2}&=B. \end{aligned} $$ Here $A$ and $B$ are "the modular versions" of $2\cos(2\pi/5)$ and $2\cos(4\pi/5)$, i.e. $(\pm\sqrt5-1)/2$, so by the well known calculations they are the zeros of the quadratic $$x^2+x-1=0.$$ It follows that as real numbers constrained to $[0,p-1]$ we have $A^2+A\ge p+1$, $B^2+B\ge p+1$, so $$A,B\ge\sqrt{p+5/4}-\frac12.$$ Consequently we get an upper bound like $$ f_p(\zeta)\le p-\sqrt{p+5/4}-\frac12. $$

Some numerical data $$ f_{11}(\zeta)=7,\ f_{31}(\zeta)=18,\ f_{41}(\zeta)=34,\ f_{61}(\zeta)=43, \ f_{71}(\zeta)=62,\ldots $$

I have this nagging fear that the very limited set of choices for $x$ may render this bound useless to you.