1

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, when the multiplicative order of $x$ in $\mathbb{F}_p$ is relatively small compared with $(p-1)$, could we find a non-trivial upper bound on $f_p(x)$?

Plus, are there any notions/books/papers that might be relevant to this question?

Thanks!!

Module
  • 81
  • 2
    What does maximum mean here? There is no notion of ordering in finite fields and one cannot say that $a < b$ for elements $a,b$ of a finite field. – Dilip Sarwate Oct 25 '15 at 14:48
  • This is a duplicate of http://mathoverflow.net/questions/221702/how-to-evaluate-this-function-in-f-p-efficiently/221705#221705 –  Oct 25 '15 at 14:57
  • Yes. I posted this question on mathoverflow.net before, as I need to answer this question as soon as possible. Is it permitted to post a question both on mathoverflow.net and math.stackexchange.com simultaneously? I do not know. If not, this post would be deleted and sorry for any inconvenience!! – Module Oct 25 '15 at 16:11

0 Answers0